7 May 2011

strategic jamming (how I just played in the Google code jam)

First, thanks to Stefan Schubert for alerting me to the contest. (Also, many thanks to all people who formed ICPC teams with me back in the good old times. What I did today was based on what I learned with and from you.)

I was surprised that the contest should only take two hours, since I know that in the past, I spent many hours working on problems like those from the code jam. But I actually like that it's so short: it encourages to be prepared for it and allows people who don't have much time to compete without much disadvantage. (Others can spend more time on preparation, but not more time during the contest.) After all, the smartest people often have a lot of different interests and are less likely to spend much time just on one thing, especially when they can produce a good-enuf solution in a rather short time.

So keeping this spirit in mind, I first found out, how many points I would need to advance to the next round and then solve the simplest problem which gets me enuf points. In this case, it was Problem C.

As usually, I solved the problem on paper first, then I wrote the code. Also as usually, I struggled with the input parsing part since Java has so many classes and methods for IO I always forget which one to use. Luckily, I remembered correctly which one to use. (I also tried googling "icpc java parse input" and "code jam java parse input", but none of each gave me any usable hints.)

Finally, I initially found two bugs in my program, the first was actually a bug in my test data, since I had produced an inconsistent input. The other bugs was forgetting two lines of code because I got distracted while writing. I found that bug by adding some debugging output, added the two lines and it the program worked on the sample input given in the problem statement. It also worked on the "small" data set of the contest and then I immediately went ahead and processed the "large" input. Let's see if I made it into the next round ^_^.

Overall it took me about 90 minutes to submit this one problem, not counting the time to log in and find the number of points needed to advance (I just didn't see it on the scoreboard initially) and find the problem that I want to solve. (Although that was pretty easy: I just took a problem that was worth enuf points and had the highest percentage of people who already solved it.)

If I do the next round, I will prepare myself a little by collecting some source code for the IO overhead that I can reuse. Also maybe let myself inspire by some contest-specific programming techniques to be found in example solutions.

Before starting I briefly thought about programming in Haskell, but since I have the some IO troubles there and less online resources to detrouble myself, I stayed with Java. Sure, Haskell is way more fun, but the real fun is solving the problem in one's head and on paper.

There are already more than 10,000 participants (still enuf time for more people to join) over 1,400 of which have solved all four problems. The fastest one used only 40 minutes for all four problems!! So I guess when the contest becomes serious and only the 1,000 best participants advance, it won't be for me any more.

Update: I did indeed make it into the next round. In fact, I am among the best 11,000 participants out of 18,000, which means I left 7,000 other very smart participants behind! In case you want to follow me in the next round, my handle is bob406.


Post a Comment