When I’m solving competitive programming problems for practice, I follow a specific series of steps to help me get the most out of the process. My current process ends with submitting an accepted solution and recording my stop time (for measurement purposes). But there really should be another step: find someone else’s solution and compare it with mine.
Arduous Chess Study
Serious chess players spend time doing what Cal Newport describes as “the arduous task of reviewing past games of better players, trying to predict each move in advance.” Here’s how it works: Given a chess position in a game between experts, come up with what you think is the optimal move. Compare your move with the expert’s move. If they differ, think about the pros and cons of each one. What made the expert choose their move? Is there a flaw in your reasoning that led you to choose your move? Repeat this process until the end of the game.
Let’s think about how to adapt this process for competitive programming practice. When you make a submission to an online judge, you get two pieces of feedback: a verdict (Accepted, Time Limit Exceeded, etc.) and a runtime measurement (e.g., 0.531 seconds). If you don’t get an Accepted verdict, you can keep trying until you do. If your runtime is under the time limit but higher than other submissions in the same language, you can try to improve the efficiency of your implementation.
One way to get more specific feedback on your submission is to find someone else’s solution and compare it to yours. Fortunately, there are a lot of sample solutions available. Some online judges, like CodeForces, let you see everyone’s submissions once a contest is over. To take advantage of that feature, you could pick a contestant and follow their work across contests. Or you could just pick any top contestant and see what they have to offer. In my practice, I’m using the uHunt problems, which are well-known and often have editorials and solutions available on blogs and GitHub.
Like going over expert chess games, analyzing someone else’s programming puzzle solution is hard work. Most people just post their code with minimal explanation, so you have to figure out what the code does on your own. If you’re looking at a contest submission from a top contestant, the code will be optimized for coding speed and runtime efficiency, not readability. Extracting algorithms and design choices from code is good experience, but it takes time and effort. If you’re doing it after you already have your own accepted solution, it’s tempting just to move on to the next problem.
To Compare or Not To Compare
Why go to the trouble of figuring out someone else’s solution when you have already finished yours? Because getting an accepted solution doesn’t mean you have extracted everything you can out of a problem. Here are some things you might have missed:
- Your solution might run under the time limit but still not be optimal. A future problem might use a similar algorithm with test data that requires a more efficient solution.
- You might find a less verbose way to express the solution, which would save you coding time in the future.
- Your algorithm might work for this problem but might not be general enough to work for all similar problems. Looking at another solution can be a more efficient way to get experience than doing a set of additional practice problems on the same topic.
This isn’t to say that you should use this process for all of your solutions. The time you spend comparing your solution is time you could be spending solving another problem on your own. So you have to consider what you’re getting out of the process for each problem. Solving a problem and analyzing someone else’s solution provide two different types of experience. Being able to quickly and accurately solve a problem from scratch is the fundamental skill you are working on. If you finish a problem and feel like you have a good command of the topic that it’s based on, it’s probably best just to move on to the next problem.
An Example: UVa 10567
Two weeks ago, I posted an editorial on UVa 10567, a string processing problem in uHunt Chapter 3. Has anyone else done the same? A Google search turns up a small number of solutions, including mine. I picked one by Sai Cheemalapati.
Sai’s editorial includes a brief explanation of the algorithm, and a short C++ solution. My solution is in Java, so I decided to translate Sai’s solution, to make it easier to compare, and to better understand it. Here’s what I found:
We both use lists of lists of integers (
vectors ofvectors ofints in C++) to store the positions of characters in the input string.However, my version does a bit more pre-processing, storing “segments” of consecutive characters (start and end positions) rather than just start positions. This makes the code more verbose: the core algorithm in my version is about 60 lines of Java, vs. 30 lines of Java for his (translated) version.
His version (translated to Java) runs a bit faster on the online judge than mine does — 0.700 seconds vs. 0.920 seconds. However, his was slower when I ran it on a local test file that I generated, probably because my test data had longer runs of characters than the data used by UVa OJ.
Comparing Solutions
The usual reason for looking up a programming puzzle solution is that you’re having trouble figuring out how to solve it. There’s nothing wrong with peeking at answers, especially if you have already put a lot of effort into your own solution. But it can also be profitable to look up a solution to a problem you have already solved. For my UVa 10567 example, I found a solution with 50% less code than I used. My solutions tend to be verbose, so for me, it’s good to study examples of how to solve the same problem with less typing.
(Image credit: Everyman Films)