How I Solve It

Below are my solutions to Google Code Jam problems. But if you want to get better at programming contests then don’t read them! At least, not at first: you should instead try problems without reading up on theory. Only after expending substantial effort should you consider seeking assistance.

I love this method of learning. If I somehow solve a hard problem, then I am rewarded by a sense of accomplishment. If I fail, then when I learn the ingenious method that neatly dispatches the problem I’ve been fruitlessly attacking, I certainly remember it well. I win either way, for I appreciate and understand new material more than I would if I had just read about it.

Some researchers call this productive failure, and their studies support this approach. See also problem-based learning and active learning in general.

How to Solve It

I’m fortunate I’ve always intuitively known how to attempt problems that I have no idea how to start. Well, “no idea” is inaccurate: I usually have some ideas, it’s just that they seem unlikely to work. But I’ll pursue them anyway, and with luck, understand more about the problem. With even more luck, this leads to more ideas, which eventually crack open the problem.

For the less fortunate, I recommend How to Solve It by George Pólya, a step-by-step guide to problem solving. Actually, I recommend it for everyone. Even if you know what to do, it’s nice to see the steps written out.

Particularly poignant for me is when Pólya stresses the importance of looking back. He gently chastises students who, having “obtained the solution of the problem and written down neatly the argument, shut their books and look for something else.” This sounds uncomfortably familiar!

I’m now trying to atone for past laziness. Apart from showing off Haskell, these notes help me look back. In the words of Pólya: “There remains always something to do; with sufficient study and penetration, we could improve any solution, and, in any case, we can always improve our understanding of the solution.”

2009 Qual 1A 1B 1C

2010 Qual 1A 1B

2011 Qual

2012 Qual

2014 Qual 1B 1C 2 ; China New Grad Test: the Practice Round uses problems from the EuroPython 2013 contest, Round A, Round B.


Ben Lynn blynn@cs.stanford.edu