I’m working on a project this year to build a competitive programming FAQ. This is one in a series of articles describing the research, writing, and tool creation process. To read the whole series, see my CPFAQ category page.
Anyone who has practiced solving competitive programming or coding interview problems, has confronted a choice: when you get stuck on a problem, when is it time to look for help? Here are some principles and suggestions to make the right decision.
Old problems vs. new problems
You have a finite amount of time for practice. So any time you spend struggling with a problem is time you aren’t working on a new problem. Competitive programming problems are designed to be solved using well-known algorithms and techniques. They aren’t research problems. To gain expertise, you have to make it through many problem types, learning algorithms as you go. If you haven’t seen the algorithm that a problem uses, it’s unlikely that you’ll be able to invent it on the spot. A computer scientist may have spent years doing that.
The benefit of struggle
On the other hand, competitive programming requires the ability to concentrate on problems for a period of time, at least for the length of a contest (a few hours). At one extreme, if you always look at the solution as soon as you read the problem, you won’t learn much. Just reading solutions doesn’t provide the learning benefit of trying the problem yourself. (This is too bad. It would make practice a lot easier). So you have to spend time struggling with problems, to train your brain for problem-solving work.
As Eric Wilson wrote on Quora:
Programming requires dogged determination and the ability to endure thousands of little defeats. It is a constant struggle against your own limitations.
Pick the right problems
To avoid having to reinvent well-known algorithms, pick problems that use algorithms you already know. A classification tool like uHunt (for UVA Online Judge), or similar tools for other online judges, can help you select the right problems. Using these tools, you can learn a new algorithm and then practice a set of problems that use that algorithm. This is how math and science textbooks work.
The downside of working on pre-classified problems is that you don’t get experience deciding which algorithm to use for a new problem. So eventually you need to work on unclassified problems. But this is a more advanced skill. Unless you know you’ll be facing unclassified problems soon (e.g., you have an interview or contest coming up), it’s fine to choose classified problems.
Pick the right difficulty level
A problem can be difficult because it requires an algorithm you haven’t studied, but there are levels of difficulty even when you pick a problem that requires a familiar algorithm. To make the most efficient use of your practice time, it’s important not to pick problems that are too easy or too hard. If they’re too easy, you won’t learn anything by solving them. If they’re too hard, you’ll waste time on problems you have no reasonable chance of solving. uHunt classifies problems by level, and other online judges allow you to sort by how many people have solved each problem, which can give you some idea about difficulty level. Timed contests often present problems in order of difficulty.
How long to work
Even if you pick a problem at the right level that uses an algorithm you’re familiar with, you’ll still sometimes get stuck. So how long should you stay stuck before looking for help? A rule of thumb is to keep working as long as you’re making some kind of progress. As long as you have a new idea to experiment with, a simplified version of the problem to solve, new test data to generate, or any other promising problem-solving techniques to experiment with, it can be worth continuing to work.
Eventually, you may reach a point where you’re not making any progress and you don’t have any good ideas on how to proceed. Fortunately, competitive programming problems rarely exist in isolation. There are hints, sample input and expected output, editorials, and complete solutions in multiple languages.
Besides this rule of thumb, you might want guidelines about how many hours to keep working. One way to estimate that number is to keep track of how long you spent solving each problem you attempted. That allows you to compare your current problem duration with previous problem durations, to see if the current problem is taking an unusual amount of time.
When I did this for uHunt (UVa Online Judge) problems, I got a median of 2.5 hours per problem, and an average of 3.75 hours per problem. uHunt provides a difficulty level for each problem, which can help estimate the expected duration. Another factor is how many hours per day you have available to work on problems. I only had a few hours per day, so for the rest of the day I could subconsciously work on problems while I did other things. If you’re spending the whole day on problems, it might make more sense to put a problem aside when you get stuck and move on to another problem. Then after a night’s sleep, come back to the original problem and see if any new ideas have appeared.
Suggestions from Quora
Variations of this question come up regularly on Quora. Here’s a sample of the suggestions from competitive programming experts and enthusiasts.
- No one suggested spending less than half an hour on a problem. Several people suggested times between 1 and 5 hours, with one person suggesting 6 hours. A few people made suggestions in the 1 to 3 day range, and a few suggested a week (including Rob Kolstad, the USACO Training Administrator). One person even suggested waiting a month before looking at the editorial.
- Many problems have tags or hints that point out what tools to use to solve a problem. This can provide a middle ground between using a classified problem source and attempting a problem blind (as in a contest).
- Deon Nicholas: “With editorials, try reading one sentence at a time. The moment you read something that you didn’t already think of, stop reading and return to solving the problem. Do this until you get stuck again, and then repeat.”
- Anonymous: If you’re stuck on a problem, look for an easier problem in the same area and solve it first to see if it gives you any ideas.
- Arjun Pitchanathan: Don’t just solve one problem at a time. When you get stuck on a problem, make a note and put it aside, and move on to another problem. Periodically return to problems you have set aside to see if you have learned any useful tricks in the meantime.
- Thanh Trung Nguyen, quoting Michal Forišek: “a rule of thumb is to solve problems, such that you’re able to solve roughly 50% of problems you attempt.”
- For USACO training problem, Brian Bi says “I don’t really have an opinion on how soon you should give up” but he points out the value of getting “through a greater volume of problems, instead of getting stuck.”
- More from Brian Bi: “But as long as you still have ideas about how to find the bug in your code, I think you should press on. When you finally find the bug, you’ll probably remember to avoid a similar bug in the future. Also, practice with debugging will help you debug more quickly in the future. When you’re new to programming contests, you’ll spend a lot more time debugging code than writing code. When you’re experienced, it should be the other way around. Nobody gets there without doing a lot of debugging.”
- Bohdan Pryshchenko: “A simple rule that I’d suggest for you – to use your time in such a way that you can’t get significantly more from doing something else during that time.” It’s worth reading this whole answer. It’s probably the best one I found on the topic.
- Finally, here’s how long Petr, currently #2 overall on Topcoder, thinks you should work on a problem: “As long as it’s still interesting for you.”
- Two years ago I wrote How Long Should You Spend on a Problem?, which has some overlap with this article.
- To see the complete list of Quora questions I have collected on this topic, check the CPFAQ page for How long should I work on a competitive programming problem before looking at the answer?
(Image credit: Caetano Candal Sato)