Another year, another Google Code Jam. Similar result this year: made it through qualification and Round 1, but got stymied in Round 2. The competition seemed tougher this year both in quantity and quality. Though the bar for qualification was raised this year, 22,000 coders made it to Round 1, up from 12,000 last year. There are three time slots for Round 1 with 1000 advancing from each slot. In the first slot, over 1000 coders had a perfect score (not me), and as a result 40+ perfect scores didn’t advance from that slot (time was the tie breaker).
Fortunately, the second slot was a little more forgiving and I was able to advance with a score of 56/100, good for position 933. The problem I missed, Technobabble needed a Maximum Flow algorithm for an efficient solution, and I’ve since added one to my toolbox.
In Round 2, I got stuck on the first problem which involved a giant rock-paper-scissors tournament. I did the small version with brute force, and tried multiple algorithms to increase efficiency for the large problem, mostly relying on memoization and symmetry. However, I needed to step back and rethink the problem instead of blasting ahead with code. I eventually did figure out the efficient solution just after time expired. The time pressure of the competition has an effect on thinking that needs to be overcome.
I’ve been using a C++ parallel processing harness for these problems, and that may have made me less concerned about finding the very best algorithm. When you have the right solution, it usually takes less than a second to execute even though you’re given eight minutes to submit results. If a subpar algorithm takes, say, 30 minutes, for all the test cases, there is a chance it could still finish in time with parallel solving of the test cases. But this time, my subpar algorithm would take many hours to execute, so the parallelization couldn’t save.
With that ringing endorsement, I’ve put my parallel solver harness on Github as parallelcodejam. I’ve used it a few years, and I think it was only beneficial once.
The parallel code does have one nice idea, I think, which is to use an atomic integer as an index into a work queue. That way, the queue itself doesn’t need to be thread-safe, and the synchronization overhead is minimal.