So, its been a couple of years since I last entered the google code jam. Back in 05 I came ~120th, and after a few cancelations it almost looked like I was going to go to the finals.
This year however the google code jam has been run in a dramatically different format. No longer powered by top coder, everyone runs their code on their own machines. This lets google’s site scale alot better, although it does add to the overhead of cheat detection.
Also new this year are regional finals. The top 500 competing at a ‘nearby’ google office before the real finals in the US.
So in a couple of weeks I will be at Google Sydney competing to be in the top 20% in APAC, so I can go to the US. I am unsure if this will be tougher then top 100 world wide, but at least the competition won’t be at 2am like the last two rounds before it. Still, there are alot of tough competitors in the APAC region.
I do have an incentive though, a friend of mine recently had his internet company bought by Google and he is working for YouTube now. He has offered a game of frisbee golf if I make it over there.
They offer job interviews to a subset of the people going. I was offered one but I turned it down. Several people have already commented that I am crazy for doing so. Maybe I am crazy because I personally can’t think what I would do at Google.
Finally however, GCJ 08 terms and conditions allow for the downloading of publically available libraries to assist in the writing of solutions during the competition. Specifically any library used must be available to all other contestants as well.
I have started work on such a library tailor made for algorithm competitions, and over the next couple of weeks intend to release it under a BSD or equivelent license via this website. The library will be for .Net and I am going to target .Net 3.5 as VS2008 is available at the competition.
For starters, any data structure in CLR’s Introduction To Algorithms, which is not in the .Net base libraries, I intend to implement. Additionally any specific algorithm which can be generalized from this book I also intend to provide. I am going to see if extension methods can be applied to delegates, because I think that would be a nice way to write ternary/binary searches for minimum/thresholds.
I currently have an implementation of IList which is backed by a red-black tree for log(n) indexed inserts. I also have another one which tracks the sum of all elements of the list prior to the current one efficiently (Specifically, it is actually generalized based on delegates for ‘addition’ and ‘subtraction’, so as long as the operator in question can be ‘undone’ it can be any accumulating operation).
If I have time, I am going to investigate implementing ‘flattened’ versions of these data structures, which store indexes into an array of nodes and maintain a free list, rather than allocating the nodes directly on the heap and using pointers. This technique usually results in a performance improvement, especialy in a garbage collected runtime. Additionally, if the array is expanded using the standard List expansion logic, the amortized additional costs on inserts are O(1). There is a memory penalty, although on a 64bit OS, with a limitation of 2^32 nodes in the collection, the memory penalty is significantly lower due to using ints instead of 64bit pointers. I am interested to see how a flattened linked list compares to the .Net runtimes built-in linked list.