I’ve made it through the Qualifying Round and Round 1 of this years Google Code Jam. You get three chances at Round 1, and this is the first year for me to advance after only one try. This was also the first time I used C++ instead of Java for the contest.
The most interesting problem to me in the qualifying round was Infinite House of Pancakes, where you essentially have to reduce a set of integers to 0 over a sequence of turns with two options at each turn: reduce every number by 1 or split any single number into two numbers (with the same sum). I correctly figured out you could do all the splitting up front, and coded an algorithm that would split the biggest number in half at each turn until the gain wasn’t worth it.
Seemed reasonable, but it failed to pass the small test set for the single number {9}. My algorithm would split it into {5, 4} and then reduce them down in 5 more steps, but it would be better to split it into {6, 3} followed by {3, 3, 3} and then reduce down in 3 more steps. So my halving algorithm had to be rethought. Fortunately there’s no real time pressure in the qualifying round, and I was able to work out a better algorithm that passed the small and the large test cases.
For round 1, the first problem, Mushroom Madness, was straightforward, and I had it completely done in under 15 minutes. I also figured out how to do the third problem, Logging, pretty quickly, but coding it was tricky and took most of my time. The problem involved convex hulls over point sets and I didn’t have any geometry routines handy to speed up the process. I had to get lucky that my code worked without too much debugging.
The second problem, Haircut, was the most interesting for me even though I couldn’t figure it out completely during the contest time limit (150 minutes). Given B barbers operating at different constant speeds and a queue of N customers, you had to figure out which barber the Nth customer would get. Seemed like a straightforward use of a priority queue to simulate all N haircuts. However, just as I was starting to code I noticed the problem said that N could be up to 1 billion, even for the small problem. A priority queue simulation would be about O(N * log(B)) — great for lots of barbers but not for lots of customers.
I coded the simulation anyway hoping it would either trigger a better idea or would be fast enough for the 4 minute time limit (after all, my Mac Pro can do billions of operations every second). It wasn’t fast enough, but I thought of looking for a cycle and noticed the limits for the small problem were 5 barbers taking at most 25 minutes each. That meant I could afford to simulate the least common multiple (LCM) of all the barber times after which the pattern would repeat, and that worked for the small test case.
The large test case allowed 10,000 barbers, and I knew the LCM would be way to big to simulate and didn’t even attempt it. Not having any better ideas, I moved on the the last problem which was fortunate because I needed almost all of the remaining time for the Logging code.
After sleeping on it (did I mention the contest started at 9pm local time on a Friday night?), I worked out a solution to the large Haircut problem the next day. Though I couldn’t compute b(n) in time, I could compute the inverse, n(b), fairly quickly. Since n(b) is monotonic, I could use a binary search to find where n(b) became the n I was looking for.
Implementing the binary search was a different story because part of my reason for using C++ was to force myself to learn more of the STL and idiomatic C++11. STL has a binary search function called lower_bound which expects to operate on iterators over a container. I couldn’t find a good way for it to operate on an indirect evaluation of a function. I tried defining a custom iterator, but it felt wrong, partly because each iterator needs its own reference to the function. I’ve since discovered Boost ranges which might do the job.
Instead I wrote my own indirect version of lower_bound that took an integer range and a function object to call.
// returns lowest number, n, for which f(n) >= value
// f must be non-decreasing
template<typename I, class T, class F>
I lower_bound_eval(I first, I last, const T& value, F f) {
I count = last - first;
while (count > 0) {
I i = first;
I step = count / 2;
i += step;
if (f(i) < value) {
first = ++i;
count -= step + 1;
}
else
count = step;
}
return first;
}
That worked, though it took me many hours more than the problem allowed. Without the 22 points for that problem, my final score was 78/100 which put me at #337 out of about 6000 in that round with the top 1000 advancing.
