FORTH GO

I competed in the Google Code Jam this week, but failed to make it through the qualification round. It looks like there were five divisions containing about 1000 competitors each and 200 from each division qualifying for the next round. Each division had different but similar problems, one worth at most 250 points and the other worth at most 750 points, with scores depending on how long it took you to submit a solution. Contestants were given an hour total to submit solutions.

The first problem was fairly easy, and was basically to minimize K + N/K for a given N ≤ 1,000,000. I probably wasted too much time being careful and double-checking things and solved it in 15 minutes or so. Instinct told me to set K to sqrt(N), but I took the time to take the derivate with respect to K and solve for zero. The only trick, I think, was to check nearby values in case of integer rounding weirdness.

The 750-point problem was pretty hard and was to count the number of ways to place K bishops on an NxN chess board, N ≤ 8, given a set of disallowed squares. A number of errors derailed my effort, but I almost got my brute-force solution working before the rest of my hour was up, but even then it wasn’t fast enough on larger boards. Solutions had to run in under 2 seconds for each invocation.

I later sped up my solution off-line. First I used bitboards throughout, getting the 7×7 case under a seconds and the 8×8 case down to 35 seconds. Then I changed from iterating over rows to iterating over diagonals and got the 8×8 time down to 8 seconds. Other tricks shaved off another second or so, but I found the real trick only by looking at successful solutions: memoization.

The other divisions’ 750-point problems I looked at also required memoization, but maybe it was more obvious in their non-chess problems. Only 31 coders succeeded at that problem in my division, whereas over 100 got it in each other division.

I was #221 in my division — guess I should have done less testing for the easy problem. Actually, the best strategy in general would be to do the hard problem first, and save 10 minutes for the easy problem as a back-up. If you only solve one problem, you have to solve the hard one or solve the easy one very quickly to qualify.

I thought the TopCoder contest framework was pretty good, though the primitive online IDE was biased against Mac users by supporting only the Control key for shortcuts like Copy and Paste. I really should have just done all my initial work offline and pasted it in when ready to run the built-in unit tests, but I wasn’t thinking it would matter that much. And it didn’t matter in this case, since I never did get a good solution, even afterwards off-line.

It was fun trying though, maybe I’ll try a few other TopCode contests.

This entry was posted on Thursday, September 7th, 2006 at 6:11 pm and is filed under Code. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.