Google codejam round 3: good bye

No surprises here, I did not advance. Even though I knew my chances and that at best I would have to battle for a good position for honor and thus. I kinda harbored the fantasy of advancing. Mind you, I really think that with the right random shuffle and combination of problems I could end in top 25. But it was unlikely. Nevertheless, I am kind of proud of my 133-th place.

Problem A: The breather

statement

This problem was one to reward intuition. I guess. It was much easier than anything else in the round.

Let us say you know the order you picked. Then, the expected time after you solve 0 levels is: f(0) = L0 + p0*f(0) + (1-p0)*f(1). Where f(1) is the expected time after solving 1 level. After some magic: f(0) = L0/(1-p0) + f(1)

Now f(1) = L1 + p1*f(0) + (1-p1)*f(2). f(1) = L1 + p1*( L0/(1-p0) + f(1)) + (1-p1)*f(2).

f(1) = L1 + p1*L0/(1-p0) + p1*f(1) + (1-p1)*f(2)
(1 - p1) * f(1) = L1 + p1*L0/(1-p0) + (1-p1)*f(2)

f(1) = ( L1 + p1*L0/(1-p0) )  / (1 - p1) + f(2)
f(1) = L1 / (1-p1) + p1*L0/(1 - p0)

After some iterations, you will find a very messy formula. But it should become clear that it is best to pick the levels in non-decreasing order of L/p. It is actually something that can happen by intuition. At least for A-small, what I did was to think that it is best to get rid of the harder levels first, so that the probability to repeat a lot of levels goes smaller with time. Then when factoring the variable Li it is also guessable that a division can occur. But after getting correct in A-small I did not want to risk it (I didn't have a proof). So I skipped to B.

If two L/p values are equal, pick the one with the smallest index, to make sure the lex first order is picked.

Problem B: The implementation hell

statement

This problem was a sand trap. I knew it was a sand trap. But I sort of thought that I could do it decently fast, and in fact I had hops to solve the large version.

I think most of the top 500 would not get scared of the hexagonal grid. Yet in this case, the grid was the least of the implementation issues. The three cases each have their complications.

You need to turn the hexagonal grid into a 2d grid. It is possible with T=2*S-1. Then you can have a TxT grid. Some of the elements in the TxT grid are invalid (don't exist in the hexagonal grid)., you have to mark them as such.

Then you need to analyze what rules involve connecting two hex cells. (x,y) is adjacent to (x-1,y-1), (x-1,y) , (x,y-1), (x,y+1), (x+1,y) and (x+1,y+1).

We need to differentiate between normal cells, edges and corners. In fact, each edge needs a different id for the cells in that edge (Forks are a pain to detect, see below). More implementation weight.

Rings: The statement help us here. We need to detect an empty cell that is not reachable to the boundary with any path of empty cells. Thus we can do a dfs starting from each of the boundary cells (borders or corners). Then if we try each empty cell, if it was not reached by the DFS, we have found a ring. A BFS also works, I used a BFS for no reason.

Bridges: Another use for a DFS, count the number of connected components of (non-empty) cells. If the number of components is less than 6, we got a bridge.

Forks: These were a pain to debug. Once I understood what was needed to detect forks, I was no longer hopeful that I could solve B-large. From each non-empty cell in an edge, do a DFS of non-empty cells. Then verify if there are two or more cells from different borders that have been visited. If there are two, we got a bridge. If you only find one of such cells, make sure to mark it out so that you don't count it as visited by a dfs from another edge...

Once I debugged my B-small, I already spent over an hour in it (fork mistakes). And it was still wrong (WA). I spent another good half an hour finding the bug (the forks again) and got a correct answer. But there were less than 30 minutes left...

The rest

I was shocked. Although I spent ages solving B-small, I somehow was still in a high position (150-th-ish). It seems that a lot of people had issues. So, I tried more problems. I could not understand what D asks for, and I did not understand what the difference between c-small and C-large was. Then I decided to take back A-large. This time, I decided to prove my intuition - it was correct. So I submitted it. It took me a while to code it because I did not have precision errors (We are sorting by (L/p, id), if we used floating points to calculate L/p, there is a risk that two different expressions L/p that give the same result are not considered the same in floating point arithmetic). So I decided to implement it only in integers (It is easy, just compare p2*L1 and p1*L2 instead of L1/p1 and L2/p2). I wonder if this was necessary.

Then I spent my last minutes watching the score boards. Many interesting surprises there. rng_58 was not in the qualifying top 25. But then the match ended, and results were updated. rng_58 got 25-th place!