Recursive Rendezvous

What if I wanted to erase
Reality given in forever
What if I wanted to dive down until the end was gone?
Imaginations crawled up until nothing was wrong?

Who am I believing what you savor as a being?
When all you know is how you've been faking?
Do I wonder what you fear when I am right?
Or was the grass never greener on the other side?

How could this possibly be the transition?
Or is this part of the long premonition?
Am I half way down the stair looking up?
Or am I half way away from the light taking back the dark?

Questions keep dawning and the answers are haunting
In this cold morning both the ends are fainting
The mirror's truth trapped in the senses
I wish truth had come by now, reality is so endless

[UVa] 469 - Florida Wetlands

I'm so used to this now. :)

9 Hours. I can take on anything now. :D
The fault was in my queue. Not because it's operations were wrong. But due to the vertex structure that I was using, the memory somehow got overlapped with the bigger arrays I guess I don't know. A simple debugging brought that in front and I knew what I had to do. Just kicked my queue away and put STL. This is the only BFS implementation of this that I've seen so far. Rank 18, not bad for all this. =]

If your code isn't working with the I/O given by forum users then try the extreme cases. 100x100 Ws and 100x100 Ls. Mine got caught on the first.

What I did was when a node is first found with a W and color[] as White, I set it as the root of that whole Water area. Every node I visited after queuing the root had the root's address. The area is increased by 1 on every node the queue opens. And when a root finishes it's queue operation it gets the area saved in it's Area Matrix position. So whenever a root or it subnodes are inquired for area, you get the address of the root from that node in O(1) and then print the address from Area[root] Matrix.

I knew it was easy with DFS and counting but I just love the customizable nature of BFS.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define XMC 100
using namespace std;

char grid[XMC][XMC], input[XMC];
int a[XMC][XMC];

typedef struct v
{
    int x, y;
} vertex;

vertex r[XMC][XMC];

void bfs(int rows, int cols)
{

    //printf("BFS %d %d\n",rows,cols);

    bool c[XMC][XMC];

    int i, j, k, l, area, areacount=0, prootx, prooty;
    vertex proot, u, v, root;

    for (i=0 ; i<=rows ; i++)
    {
        for (j=0 ; j<=cols ; j++)
        {
            c[i][j] = false;
        }
    }

    for (i=0 ; i<rows ; i++)
    {
        for (j=0 ; j<cols ; j++)
        {
            if (c[i][j]==true || grid[i][j]!='W')
                continue;

            proot = {i,j};

            root = proot;

            c[i][j] = true;
            r[i][j] = root;

            //printf("BFS: Rooting for %d %d\n",r[i][j].x,r[i][j].y);

            area = 1;

            queue<vertex> q;
            q.push(root);
            while (!q.empty())
            {
                u = q.front();
                q.pop();
                for (k=u.x-1 ; k<=u.x+1 && k<rows ; k++)
                {
                    if (k<0) k++;
                    for (l=u.y-1 ; l<=u.y+1 && l<cols ; l++)
                    {
                        if (l<0) l++;
                        if (c[k][l]==false && grid[k][l]=='W')
                        {
                            //printf("BFS: \t%d %d - %d %d\n",k,l,r[i][j].x,r[i][j].y);
                            c[k][l] = true;
                            r[k][l] = root;
                            area = area + 1;
                            v = {k,l};
                            q.push(v);
                            //if (r[i][j].x!=prootx) r[i][j].x = prootx;
                            //if (r[i][j].y!=prooty) r[i][j].y = prooty;
                        }
                    }
                }
            }
            a[i][j] = area;
            r[i][j] = proot;
            //printf("Found area %d in %d-%d\n",++areacount,r[i][j].x,r[i][j].y);
        }
    }

}

int main()
{

    //freopen("469_in.txt","r+",stdin);
    //freopen("469_out.txt","w+",stdout);

    int test, i, j, rows, cols, rp, cp;
    vertex root;
    bool blanker=false, run;

    scanf("%d",&test);
    getchar(); getchar();
    while (test--)
    {
        if (blanker)
            printf("\n");
        else
            blanker=true;

        run = false;
        i = 0;

        while (gets(input) && strlen(input) > 0)
        {
            if (input[0] == 'L' || input[0] == 'W')
            {
                strcpy(grid[i++],input);
                cols = strlen(input);
                rows = i;
            } else
            {
                if (!run)
                {
                    bfs(rows,cols);
                    run = true;
                }
                sscanf(input,"%d %d",&rp, &cp);
                rp--; cp--;
                if (grid[rp][cp]!='W')
                    printf("0\n");
                else if (rp>=rows || cp >=cols || rp<0 || cp<0)
                    printf("0\n");
                else
                {
                    root = {r[rp][cp].x,r[rp][cp].y};
                    //printf("Accessing %d//%d %d//%d\n",root.x,r[rp][cp].x, root.y,r[rp][cp].y);
                    printf("%d\n",a[root.x][root.y]);
                }
            }
        }
    }
    return 0;
}

[UVa] 10611 - The Playboy Chimp

All you need is some knowledge of speeding up searching and some tricks to keep things in limits.

First of all, make the heights of the lady monkeys distinct and store them. You can use a map and store in it each height's position in the vector. That helps later.
Now you can make some decisions easily during the querries, if a querry has an index to it in the map then just go there. Check for the index to be boundary or not and print based on that. If however a height is not found, just browse you collection through linear search and make the same decision there. If a height is bigger than the biggest woman height or smaller than the smallest woman height you have a given advantage on it.

I think the vector is slowing it down. Gonna try an array.

#include <cstdio>
#include <map>
#include <iostream>
#include <climits>
#include <vector>


using namespace std;

map<int,int> ver;

vector<int>line;

int main()
{
    int i, j, k, wc, hc, minwh, maxwh, maxk, temp, x, y;

    line.push_back(-1);

    minwh = INT_MAX;
    maxwh = -1;
    scanf("%d",&wc);
    for (i=0, k=1 ; i<wc ; i++)
    {
        scanf("%d",&temp);
        if (ver[temp]==0)
        {
            line.push_back(temp);
            ver[temp]=k;
            k++;

            if (temp>maxwh)
                maxwh = temp;
            if (temp<minwh)
                minwh = temp;
        }
    }


    maxk = k;
    scanf("%d",&hc);

    for (i=0 ; i<hc ; i++)
    {
        scanf("%d",&temp);

        if (temp<minwh)
        {
            printf("X %d\n",line[0]);
            continue;
        } else if (temp>maxwh)
        {
            printf("%d X\n",line[maxk-1]);
            continue;
        }


        if (ver[temp])
        {
            k = ver[temp];
            if (k-1 < 0)
                x = -1;
            else
                x = line[k-1];

            if (k+1>=maxk)
                y = -1;
            else
                y = line[k+1];
        } else {
            for (j=1 ; j<maxk ; j++)
            {
                if (line[j]<temp && line[j+1]>temp)
                {
                    x = line[j];
                    y = line[j+1];
                }
            }
        }
        if (x<0) printf("X ");
        else printf("%d ",x);
        if (y<0) printf("X\n");
        else printf("%d\n",y);

    }

    return 0;
}

[UVa] 11247 - Income Tax Hazard

Simplification of the theorem solves the problem with a few glitches to overlook.
First of all v-(vx)/100 < m-1. Let q = m-1. Play with it for a while and you get => v < q/(100-x)/100 => v < 100q / (100-x) Don't ignore the < sign it will drag you by the nose for a while. So you generate a v from this. But realize if 100q is completely dividable by (100-x) then v must be smaller. So check if that happens. If it does, just decrease v by 1. And some other gotchas are x being m being 1 because you use m-1 and x being 0 or 100.

#include <cstdio>

#include <iostream>

#include <cmath>

#include <cstdlib>

#include <iostream>

using namespace std;



int main()

{

long long v, p, q;

long long m, x, orig_m;

while (cin >> m >> x)

{

if (!m && !x)

return 0;



if (m==1 || x==0 || x==100)

{

printf("Not found\n");

continue;

}



v = (100*(m-1)) / (100-x);



if (( (100*(m-1)) % (100-x) ) == 0)

v--;



if (v<m)

{

printf("Not found\n");



} else

{

cout << v << endl;

}

}

return 0;

}

[UVa] 138 - Street Numbers

I encountered this problem at the very beginning of my ACM days and was totally noobish. I played with the ratios a lot that I got from the outputs using doubles but the result never quite reached the points. I googled and found precalculations and theorems in Algorithmist. I just wanted to do it on my own.

Method:
1. Analyze for the first input:
SUM[X-Y] means summation of all the numbers from X to Y.
It's clear that
SUM[1-5] = SUM[1-8] - SUM[1-6]
So, 5*(5+1)/2 = 8*(8+1)/2 - 6*(6+1)/2
Now, think of 6 as Y, 5 as Y-1 and 8 as X.
So, we get
==> (Y-1)*(Y-1+1)/2 = X*(X+1)/2 - Y*(Y+1)/2
==> (Y-1)*Y/2 = X*(X+1)/2 - Y*(Y+1)/2
==> Y(Y-1) = X(X+1) - Y(Y+1)
==> Y(Y-1) + Y(Y+1) = X(X+1)
==> Y(Y-1+Y+1) = X(X+1)
==> Y(2Y) = X(X+1)
==> 2Y^2 = X(X+1)
==> 2Y^2 - X(X+1) = 0

So, we are simply looping from 1->INT_MAX so we have all the Ys. Just find if there is such an X that solves the equation. I coincidentally hit the theory that FLOORING of SQRT(2Y^2)is the only possible number.

#include <cstdio>
#include <iostream>
#include <cmath>
#include <climits>
using namespace std;

int output[20][2]={0,0};

int main()
{

    freopen("out.txt","w+",stdout);
    double rupper, rlower;
    long long i, count, upper, lower;

    for (i=1, count=0 ; i<=INT_MAX && count<=10 ; i++)
    {
        upper = 2 * i * i;
        lower = sqrt(upper);

        if ((upper - (lower*lower) - lower)==0)
        {
            cout << "{" << i << "," << lower << "}," << endl;
            count++;
        }
    }

    return 0;

}

The output is generated in a file, named out.txt. Just make a program and initialize the array with the output. And print it.

World itself is horrific enough, cut the digital crapheads

The era when I had started gaming the arena had all kinds of games that we see these days, no innovations till now. I ain't complaining, lovin' what it's already got. But not just all of it. I recently have found that I have an itch with horror, particularly zombie based games. Why, don't know. I hate to keep on killing stuff that is already so gone. Movies were enough with zombies and dead four legged human bellies/heads that come wanna mate with your head. But why games? I couldn't even start playing the popular zombie title "Resident Evil" 5 years back from now. I hated "The Thing". Not because of how damn thrilling some of its scenes were, but how aimless and pointless it is to kill four legged minis jumping at you. I can take four legged grenades anytime. I love the electro-magnets that come at you in Half-Life 2. They are so fun because of the technicality probably. But armies of the same old boring biological quadropods? Come on!!!. I completed the whole "Ravenholm" part in Half Life 2 that solely features on zombies. Though they were fun because of the blades that I could use with the Gravity gun. I even have finished Doom 3 two times because of the thrills I got from shadows caused by monsters walking overhead or corpses hanging in front of lights. I liked to kill the huge half zombie spiders but not all of them.

I think because of their walking abilities that game developers give them, these (>2)pods or multipods, if I may call them, are overused in every section right after the one they were first uncovered. It's sometimes a huge waste of your favorite Shotgun ammo or Chaingun ammo on these things, while you really wanna kill that howling boss with them. The problem with these overused elements in gaming is amplified when they make some irritating sounds. I remember swarms of spiders attacking in a game while make some ultra high frequency sound everytime they attack you. It was so painful I had to turn off my speakers. Millions of them around you, you need some time to kill them right? And I hated those Scorpion Kings in Serious Sam games. God those sounds. Whenever I heard them calling out, I wanted to just skip everything else and kill them.

Maybe that's what the Game developers want, to make them so irritating that you wanna kill 'em. But it also makes some levels disgusting to play. I always feel tired when I think about finishing them. I know how badly I waited for the Ravenholm episode to end before I could get back some fun. I even checked walkthroughs to find out if the game had any other practical levels later, or else I would have considered Half Life 2 an end right there.

Just pass it around the table, you ain't drinkin' it anyway

Do we really know who we are?
I mean is it really possible to know what person you are?
I once had a friend who said that he didn't like to use DSP Plugins that come with computer applications like DFX. Why? I asked. And he said it was because the sound gets processed, he didn't like processed sound. I felt that something was wrong with his statement but due to my nature, I couldn't find it in the logic streams. Today, about 1 year later, when I somehow remembered that incident, it dawned to me. How does he know which is the real sound? How do you? How do I? Come to think of it.
If you're considering listening to some unprocessed music on your computer or on your mp3 player, what do you do? Simply use the player without DSP Plugins or any equalizer. Now, we all know that all these multimedia accessories come coded with sound engines of some kind that decode that sound data or the mp3 files that you give it. There is not only a single decoder for this task. Chinese, Japanese, American, Russian. Even if some of us techies come up with the counter argument that "All use LAME Decoder" or "Standard decoder is Fraunhofer IIS dude!" I'd say, even then it's not totally untouched. Some programmers might use extra commands available to them through those decoders. Like command line switches. Which should differ sounds
between players. Now imagine discovering that Sony devices sound crap compared to iPods. Why? Just because of the Headphones? We know Apple doesn't focus on headphones, Sony does. The clarity comes with a price then? Does it mean the real sound came with a price? I mean, think about your artist who availed you with that sound. Did he/she make several copies based on price? No!! Even if some of us use same decoders, the files themselves can sound different even on the same bitrates and all, due to the encoders used by different users when ripping the Sources.
This wasn't and still is not only about sounds. It's about reality itself. How do you know who you are? You've lived all these years, refined yourself through your experiences every second. Your mother tongue, your beliefs, your outlook to people who are not from your country all this was refined through society's interaction with you. Based on some of your instincts you chose what you wanted to be in your personality. Some of it you grabbed, some of it you just spit out, some of it you stood against and some of it you supported and wanted to be in others too. I don't know about you or your friends or your family or your president or our prime minister or my family or my friends. But what I feel like, after all this, that reality or who you are
is not what others tell you, what others want. It's what you want. No matter what, no matter how hard you try or how fast you run. You will ultimately come to the grounds of your own choices selecting what you want. Reality is inside you, how you want things defined around you. Remember those moments when no matter what you can't accept others? Why? And you never knew what you wanted before you were born. You were born to want these things. You were born with these wants, these essentialities, these needs.
How do you erase them? If you are a self defier, you'd try to defeat yourself and do everything opposite to what you want right? But that's you again. You the defier, it's what the defier wants. That reality taking over inside you. Defining you as the defier. So it's again what you want, that's defining reality for you than what anyone else in this world wants. If you are
a society defined person you are just doing what others want because that's what you want. To see that people like you. If you're a rebel then so be it. You fight society. Ultimately, that hard coded want in your self is something that no one can change. It's us that we can't change. It's us to live the way we were born to live, because of our wants.
Doesn't it sound like a control over us? Of course you should have seen it coming, the control of God? God has defined you, before you came here. He has already chosen what is going to happen and everything is happening just the way God has wanted. Through us. We say we change the future, but it's been already changed. The story of the universe has already been written. We are
the pen. Everybody, every single element is the pen. And these pens themeselves are the part of the story. This sounds so confusing to imagine but so clear if just gulped down. Just the way you accept yourself. You don't know why you want certain things but you just want it. You don't know why you can't forget or to stop thinking, it's just there and unchangeable.