Yuval Adam

GCJ 2011 - Qualification Round Review

The Google Code Jam 2011 qualification round has been pretty good.


But back to the beginning. I settled on the my rooftop with a beer, and listened to some mood-setting music (LCD Soundsystem and¬†!!!). The round started at 2AM here in Israel, and I didn’t plan on sleeping before, so I assumed I would probably not get all the problems done at once, and will need a good night’s sleep in between the problem sets. And I was right.

So obviously I started off with the two easier problems: Bot Trust and Candy Splitting. Bot Trust was an easy simulation exercise. Somewhere midway I thought I figured out a way to calculate the value by choosing the minimum value from both bots routes without running the entire simulation, but it didn’t take into effect the mutual exclusion rules. That wasted some precious time, so I went back to the simple simulation. The input set was simple enough to run a naive algorithm on it. So that was finished around the 40 minute mark.

Next up was the Candy Splitting problem. Recognizing the fact that it is nothing more than a xor summing problem is all it takes. Running a greedy algorithm on the candy set (linear!) gives you the result. Pretty easy, I finished this problem in about 20 minutes.

After that, I couldn’t quite wrap my head around the Gorosort problem, so I left it for the next day, and took a shot at the Magicka problem. It took me a while to figure it out, but then I realized it’s simply a matter of iterating over a string,¬† and replacing characters and deleting prefixes if necessary. I got the algorithm down, and implemented, but failed the first small test. I inspected the algorithm, and found nothing wrong. That got me frustrated, so I went to sleep, and figured I’d start fresh after several hours of sleep.

The next day I went out to a cafe near my place, and started working the problems again. I started off from the Magicka problem, and figured the late hours caused me to miss something simple; my only issue was that I was printing the output wrong - FACEPALM. I quickly fixed the output printing statements, and sure enough, problem solved.

Last issue, try to figure out the Gorosort problem before the round ends. This one really took me a while. I started out with some observations, such as the fact that binary flipping is always the best option (flipping more than 2 indices in the array isn’t efficient in terms of probability), and that flipping mutual pairs is obviously best. But I didn’t quite nail it down. I knew how to find the bad indices, but couldn’t quite get the calculation correct. Eventually it hit me, I was calculating the expected value completely wrong, I was taking each index flip and multiplying by two (for the 50-50 probability) instead of looking at the amortized cost!

Bottom line - qualification round was lots of fun! I have some observations like the fact that using source control (git FTW!) is really helpful in working diffs when changing strategies, and the fact that it’s important to work with a handy utility that does all the file handling and miscellanea¬† for you, but I’ll leave that to another post.

See you all in Round 1!