Google Code Jam 2011 Round 1

Round 1 of the Google Code Jam 2011 contest was last week-end. I stayed up Friday night for the first of three sessions for round 1 qualification. The top 1000 in each two-and-a-half-hour session advance to round 2. I was fortunate to end up around 200th, so I didn’t have to try the other sessions after all. I don’t know how many competitors there were, but there were 3100 who solved at least one problem correctly.

There were three problems, each with a small and large challenge test cases. The first problem was relatively easy, and basically boiled down to computing greatest common denominators to reduce fractions. I used a fraction class I had from Project Euler work, which made things even simpler. That got me 20 points in under 20 minutes, which turns out was already good enough to place around #640 in the final scores. Time is used for tie-breaking, and there were about 1500 partipants with 20 points.

The second problem was worth 30 points but had a very long description, so I skipped it. It looked interesting reading it later, but I wasn’t confident about boiling down all that prose correctly under time pressure. The problem was basically to find the hardest word(s) for someone to guess in hangman, given the guesser’s letter-picking order.

The third problem was the hardest and worth 50 points. You had to basically find the maximum score for a solitaire card game, given the order of cards in the deck. I thought it would be a simple dynamic programming solution, but the parameterization I chose was obviously not optimal. I included the current cards in the hand as part of the state, but with up to 80 cards in play, there could be a disastrous 280 possible states. After several tries, I was able to add enough tree-pruning to my code to solve the small test cases and get 15 points, but I never solved the large test case which included more pathological card sequences, defeating my pruning logic.

As a consolation prize, my code did trigger an internal JVM error at one point:

*** java.lang.instrument ASSERTION FAILED ***: "!errorOutstanding" with message can't create name string at ../../../src/share/instrument/JPLISAgent.c line: 769

Update: Turns out my parameterization was OK, but I had bugs in the pruning logic.