Like last year, it took me three attempts to get through Round 1 of the Google Code Jam, having to get compete at 5am Sunday. For the first two attempts, I essentially skipped the easy (small) problems and went straight into solving the large versions of each problem, which would simultaneously solve the small problem, too. But that strategy didn’t make the cut (top 1000 scores), so I focused on solving the small problems first for Round 1C and finished in the top 300 to move on to Round 2.
I did get the large version of Problem A, Consonants, after working out a dynamic programming solution. And almost finished the large version of Problem C, The Great Wall, but it took me an extra 20 minutes after the contest ended to get it right. It’s nice that Google let’s you keep trying for practice even when the context is over.
In finishing the problem, I learned about a Java API I didn’t know about, NavigableMap. I was looking for something like C++’s std::map::lower_bound/upper_bound for iteration through a subrange of an ordered map, but I didn’t see anything in the Java Map API. Fortunately I found NavigableMap, whose floorEntry and higherEntry provide similar functionality. The problem called for keeping track of repeated attacks/fortifications to a wall. For the small solution I stored the wall as an array using an element for each unit-length segment, but that wasn’t efficient enough for the large solution. I needed each stored element to represent a run of similar segments and support splitting of segments as new attacks occurred while staying ordered for fast look-up. The balanced binary tree implementation of NavigableMap fit the bill.
A great feature of Code Jam is being able to examine other competitors’ entries after the contest is over. I checked one top scorer’s solution and he didn’t use such a data structure. Instead, he made two passes through all the wall attacks. On the first pass he recorded where all the splits might occur. Then he could allocate an array for those segments without needing to split elements on the second pass.