My luck ran out in Round 2 of the Google Code Jam 2011. I placed 626th but needed to be in the top 500 to advance. At least I qualified for a T-shirt for being in the top 1000.
There were four problems this time, with less variation in difficulty than usual. I solved the first problem, Airport Walkways, completely and got partial credit for my correct-but-inefficient solutions to two other problems. Of course, I figured out how to make my solutions efficient shortly after the contest ended. I didn’t get to the fourth problem, A. I. War, but it looks more straightforward than I expected from a title alluding to artificial intelligence. Maybe I could have solved that one completely instead of one of the partial solutions.
The third problem, Expensive Dinner, involved finding the difference between the best and worst case for a particular problem involving least common multiples. I set about computing both cases separately and taking the difference. I thought I was doing well to reduce the naive O(n2) solution to O(n), but when n is 1012, that’s not good enough (for full credit). I reduced the best case to be the number of primes less than or equal to n, aka π(n), and the worst case to be the number of primes powers less than n. That seemed like a dead-end, though, since it’s not so easy to calculate π(1012). What I didn’t see in time is that since I was going to be taking the difference of the two and they both included π(n), I didn’t have to compute that part at all. And counting the higher prime powers is much easier, and that’s all I really needed to do. Oh well.
The second problem, Spinning Blade, didn’t involve any fancy math, but required a clever data structure to reduce it from O(n4) to O(n2) or so. (n was limited to 500, so O(n2) is fine.) I didn’t find it in time, though, and went with my brute force solution for the partial credit.