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.