Google Codejam round 2 - yay!

I am just glad I managed to advance to round 3. Round 3 is going to be quite brutal for a guy that barely got the 467-th position, but still.

Problem A - Swinging Wild

Problem statement

The first degree of difficulty was in understanding the statement. Let us simplify imagining there is a vine of length 0 at position D. We want to know if we can reach this last vine.

Let us say we just reached vine i. There is a maximum length we can use in that vine. For Vine 0, it is d[0]. For the later vines, this length depends on the position of the previous vine. So, if we used vine j to reach vine i, the maximum length we can use for vine i is min(length i, d[i] - d[j]).

The first idea is a dynamic programming one. f(i, j) returns whether it is possible to reach the last vine if you have just reached vine i and the previous one was j. Then you can get the maximum length you can use for vine i. This is the maximum distance between i and the next vine you use. Thus you can pick any of those vines within reach, and continue the recursion until i = the last one. This is enough to solve A-small.

But we want to solve A-large, which would not allow such a O(n^3) complexity. Let us instead define maxlength[i], the maximum length possible at which we can reach the i-th vine. You can see that this maximum depends only on the vines before i. Once we know this maximum length, we can use i to find possible lengths for later vines.

For example, for vine 0, the maximum length is d[0]. Pick each vine j within d[0] distance of vine 0, then a possible length for vine j is min( d[j] - d[0], length[j] ). After this step, the maximum length for vine 1 and vine 0 is already know, and we can use vine 1's maximum length to update more vines. This approach is O(n^2) in time complexity and needs only O(n) memory.

int N; 
int d[10001]; 
int l[10001]; 
int D; 
 
int maxlen[10002]; 
 
bool solve() { 
    d[N] = D; 
    l[N] = 0; 
    for (int i=0; i<=N; i++) { 
        maxlen[i] = -1; 
    } 
    maxlen[0] = d[0]; 
    for (int i=0; i<N; i++) { 
        if (maxlen[i] > -1) { 
            for (int j=i+1; j<=N; j++) { 
                if (d[j] - d[i] <= maxlen[i]) { 
                    maxlen[j] = std::max( maxlen[j], std::min(d[j] - d[i], l[j]) ); 
                } else { 
                    break; 
                } 
            } 
        } 
    } 
    return (maxlen[N] > -1); 
} 
 

This problem made me feel confident, because I solved it rather quickly. I was not expecting the next problems to each be very complicated :).

Problem C - Mountain view

Problem statement

It seemed like C-small was less tricky than B-small, because of the accuracy rate from other competitors. So I first tried to solve this one. I actually barely got a integer programming solution, and I am still not sure I actually know how to code an integer programming solver.

After the match, I found solutions that merely pick random numbers for the (at most 10) heights and verify that the answer is correct. Then you can output the correct answer. If after enough random attempts, no answer is found , it is impossible. The small number of peaks makes the probability to find a correct answer (if it exists) quite large.

I feel so lame for not thinking of this.

Problem B - Aerobics

Problem statement

So, my initial idea was to consider the circles as squares. And then the problem is just to place those squares. Somewhere in the rectangle. My theory was that if you sort the square lengths in non-ascending order, and then always placed each square in the closest valid position to the bottom-left, you would find a solution (The area is at least 5 times larger than the area of the circles, so it is quite unlikely this solution won't work). Indeed, even in cases where your circles have quite large radius, but the rectangle has only 1 as width, this is possible.

You can also verify that this approach needs only integral coordinates. Somehow, during the match I thought that it was possible to have 0.5 coordinates, and thus I multiply everything by 2 and other unnecessary things.

I was pretty sure that would work, the issue is how to get the best location. With W,L <= 10⁹, we cannot just try each coordinate for the center until we find one that does not intersect. So much that I even tried thinking of a different strategy. For a second, I thought of random (ironic as random would have helped in the other problem, but not this one).

I wish I noticed the obvious solution to this predicament in less time than a whole hour: mundane binary search. For each square you want to place, binary search for the minimum x at which there is enough space to place it. How do you know if there is enough space at a given x? Simply use another binary search, but this time for y. Since you place the squares in order, and the previous squares are all together in the bottom-left position, both situations are binary search friendly.

int N; 
int W, L; 
int x[1000]; 
int y[1000]; 
int r[1000]; 
 
pair<int,int> ri[1000]; 
 
 
// If the center of "square" i was (px,py), would it intersect with the 
// previously placed squares? 
bool intersect(int px, int py, int i) 
{ 
    for (int j=0; j<i; j++) { 
        if ( (x[j] + r[ri[j].second] > px - r[ri[i].second]) 
            && (y[j] + r[ri[j].second] > py - r[ri[i].second]) 
        ) { 
            return true; 
        } 
    } 
    return false; 
} 
 
int gety(int px, int i) 
{ 
    int loy = -1; 
    int hiy = L; 
     
    while (loy+1 < hiy) { 
        int hay = loy + (hiy - loy)/2; 
        if (intersect(px,hay,i)) { 
            loy = hay; 
        } else { 
            hiy = hay; 
        } 
    } 
    return hiy; 
 
} 
 
void solve() { 
    for (int i=0; i<N; i++) { 
        ri[i] = make_pair(-r[i],i); 
    } 
    sort(ri, ri+N); 
    x[0] = 0; 
    y[0] = 0; 
    for (int i=1; i<N; i++) { 
        // Binary search for x 
        int lox = -1; 
        int hix = W; 
        int picky; 
        while (lox+1 < hix) { 
            int hax = lox + (hix - lox)/2; 
            int py = gety(hax, i); 
            if (intersect(hax, py, i)) { 
                lox = hax; 
            } else { 
                hix = hax; 
            } 
        } 
        int py = gety(hix, i); 
        // I used this assert, because maybe the strategy did not work, this 
        // assert would alert me when running the large input... 
        assert(! intersect(hix, py, i) ); 
        x[i] = hix; 
        y[i] = py; 
         
    } 
    for (int j=0; j<N; j++) { 
        for (int i=0; i<N; i++) { 
            if (ri[i].second == j) { 
                cout << x[i] << " "<<y[i]; 
                if (j < N - 1) { 
                    cout << " "; 
                } 
 
            } 
      
        } 
    } 
    cout << endl; 
} 

Then I noticed that this approach works for B-large as well. So I just submitted it.

The last minutes

By the time I finished B, I had around 50 minutes left. But I had no idea what to do. Kept trying to think of something for C. Read D and then got baffled and tried to think of something too. There was a time at which I thought to solve D-small with a random solution. I just wish I was so creative with C...

As time progressed, my ranking got closer and closer to 500. The very last minute it eached 508 and then 520... Some people failed the large inputs in some problems (not lucky for them, but lucky for me). And I advanced to round 3.

To be honest I was not even expecting to be in the top 1000 today.

I really liked this match. B , C and D were all really heavy weight problems in "interesting-ness" and difficulty and A was a good distraction.