Google Code Jam Round 2

Links:
Google Code Jam Statistics: http://www.go-hero.net/jam/
Google Code Jam Scoreboard: http://code.google.com/codejam/contest/scoreboard?c=204113

Overview
Round 2 proved to be a bit trickier than Round 1, especially in terms of advancement as only the top 500 go through. The time setting didn't help either for many contestants. Unfortunately I didn't make it through but congratulations to everyone who did! It has been a major blast of fun :)

So what happened? There are several key points I've learnt from participating this round.

1. Don't focus too much on constraints!

For problem A, my first instinct was a greedy based algorithm which was rather close to the correct algorithm. However, I quickly convinced myself (wrongly) that it would fail for cases in which you would possibly make a move which turns the remaining subproblem infeasible. This does not happen though as the strictly increasing ordering of the final output prevents this from happening. This was further misled by looking at the large constraint which had a maximum of 40. Surely a greedy algorithm can't work right? Wrong! :)

Although it is always good to look at constraints (and perhaps I've relied too heavily on it) to dictate what algorithm the problem setter is expecting don't let it "blind" (i.e. let it confirm your incorrect doubts of an algorithm without fully going through it) you though as it did to me.

2. Don't get too focused on a particular methodology and learn to back out of an idea if you can't get anywhere with it!

After solving A-small and D-small, the only way I would advance is to solve both C-small and C-large (or B but fewer people tried to solve it so I also tried C). Instead of wasting time on finding the correct solution to A-large, I proceeded with problem C.

First thought was bipartite matching (and that hunch was correct) as it felt natural (because I've actually solved a very similar problem). I couldn't reduce the graph properly with the correct edge labelling criteria so I completely abandoned this idea (bad move as I did in fact at one point have the correct algorithm but made a false assumption which would of made it incorrect). I eventually deduced it to finding the minimum number of complete induced subgraphs (clique problem). However this is NP-complete, so I really should of backed out of this reduction but I was persistent as this was the only "correct" (although it would time out) solution I had. Sometimes it pays off to let go of an idea if you can't get anywhere with it which is easier said than done!

Despite being slightly disappointed I had a fun time. Unfortunately no Australians (unofficially at this point) have made it through to Round 3. Good luck for all those participating in Round 3 though :)

Official Contest Analysis is available: http://code.google.com/codejam/contest/dashboard?c=204113#s=a