Google Code Jam 2019 Qualifying

This year’s Google Code Jam started yesterday with the 27-hour Qualifying Round. I managed to get all the problems correct for a score of 100/100 along with about 1000 of the 35,000+ participants. You only needed a score of 30 to advance, so many who could have done better probably stopped when they had enough points to qualify.

The problems always get harder with each round, but this year’s qualifying round seemed easier than usual. The first two problems only took a few minutes each, and I almost stopped there since I knew I already had 30 points.

The third problem, Cryptopangrams, was also easy to figure out, but the solution required doing math on 100 digit integers, which I couldn’t readily do in C++. I briefly looked around for a simple big-integer library to include but decided to relearn enough Python to use that. It felt silly googling things like whether array indices start at 0 or 1 (it’s 0 in Python), how to comment out a line (‘#’ character), and how to do integer division (‘//’ operator). I never did come across a good Python cheat sheet; instead I had to wade through various introductory teaching pages. Fortunately, there was no real time pressure and it was a simple problem.

All the problems have at least one small/easy test case and one large/hard test case. For the fourth problem, I could figure out the easy case quickly but had no idea how to solve the hard case. After re-reading the problem statement I realized the parameters were constrained enough (looking for at most 15 errors in a 1024 bit string) for me to solve. These are most fun problems to solve: when you start with no clue and keep looking at different angles until you find a solution.

The other complication for the fourth problem was that it was interactive. Instead of the usual read-problem-input/write-solution sequence, an interactive problem requires multiple queries and responses before the final solution can be determined, and that makes testing your code much trickier. Google nicely provides a testing Python script, which I eventually got working in my CLion environment. Had to use chmod to make executable and had to prefix it with #!python for it to run. Then I set up a CLion target for the script which would launch the testing tool and my code and get them to talk to each other. Maybe I can remember enough of it to get through the next round when time is more constrained.

The Code Jam results list is a bit harder to navigate than it used to be. I wanted to look at other contestants’ solutions to the Cryptopangrams problems to see if any of them used C++. You can still look at submitted solutions, but when you do so you lose your place in the list, so you have to start over at the top of the list with each try. I looked at a few entries in the top 20 and none used C++ for that problem. Most used Python, some Java and one Ruby.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.