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.
Last month, I described how several successful competitive programmers approached their training. These stories are not uncommon on Quora and elsewhere. So as the year wraps up, here are some more suggestions from the experts, including the two experts you would expect to hear from.
In his 2008 chat on Topcoder, Petr Mitrichev made numerous suggestions for competitive programming training based on his own experience. Here are the ones I found most relevant:
- Use algorithms books (e.g., CLRS) and math books (e.g., Concrete Mathematics) for reference when you get stuck on a problem. But books on their own won’t teach you competitive programming. You have to work through actual competitive programming problems.
- If you want to get good at competitive programming, don’t just learn algorithms for their own sake. Instead, find a problem that uses an algorithm you want to learn, and combine the process of solving the problem with the process of learning the algorithm. That way, you’ll be able to implement the algorithm when you need it.
- When you can’t solve a problem, figure out what you’re missing. What would you have needed to know to solve it? If the missing piece is a new algorithm, learn it and implement it yourself. Don’t just read the problem editorial.
- If your competitive programming career is long enough, you’ll eventually be able to stop practicing. You’ll maintain your skills just by participating in contests. But that won’t happen at least until you hit red.
- The time when Petr felt he improved the most was when he attended the Russian IOI training camps (twice a year for two weeks each). The daily schedule at the camp included a programming contest from 9 AM to 2 PM, and a lecture on related topics from 3 PM to 7 PM. He learned the most from the contests, since they provided problem-solving practice. Although most of us don’t have access to Russian training camps, anyone can find an online judge and do virtual contests.
- Petr rarely used an online judge for practice, but that’s because he didn’t know about them during his practice years. However, he had coaches who assigned him problems in high school and university.
- He started coding in 1997, when he was 11 years old. That’s not uncommon for top performers. Which is why people ask, “Is 9th grade too late to start preparing for IOI?“
- For Dynamic Programming problems, there is no cookbook process you can use to come up with the DP relation. You have to practice DP problems and gradually learn to recognize patterns.
- If you get stuck on a problem, keep working on it until you get bored. Then look at the solution. (My note: the effectiveness of this advice will depend on how easily you get bored.)
- Learning to think mathematically is crucial to competitive programming success. Keep in mind that Petr’s degree is in math, which might influence his thinking. However, most problems require some math fluency, even when they don’t involve advanced math concepts.
- Here are a few ways to get better at the challenge phase of a programming contest: 1) Find opportunities to teach other people, and observe what mistakes they make as they’re solving a problem; then look for similar mistakes in people’s code during contest challenges; 2) Keep track of mistakes you make in your own solutions, and look for those mistakes during challenges; 3) As a last resort, look for a simple solution and try to find logical errors in it.
- To save debugging time, learn to see the invariants in your implementation, and set breakpoints in those places to make sure the invariant values are what you expect.
- Petr starts coding a solution before he is done thinking about the problem, but he doesn’t know if that approach is best for everyone.
In 2017, Gennady Korotkevich gave an interview to Rusbase. I don’t read Russian, but Chrome Translate did a good job of making it understandable. Here are some of Gennady’s tips on training and competing:
- During a five-hour programming competition, he finds food to be distracting, so he just drinks water. He also likes to walk around during the competition rather than trying to sit and think the whole time.
- He can solve some programming problems by just using logical thinking. Other problems require a specific problem-solving technique. For example, there’s the special case technique: find the most difficult special case that you can’t yet solve, and try to solve that special case. Then see if you can adapt the special case solution to solve the general problem.
- Some problems require patience. Gennady describes an example from ACM-ICPC World Finals 2015, where his team worked for over two hours on a problem that other teams solved much faster. But they finally solved it and went on to win the contest. In fact, they were the first team in history to solve every problem in an ICPC World Finals contest.
- Because ICPC rules allow only one computer per team, one contestant must code while the others think and make notes on paper. Rather than setting strict assignments in advance, Gennady’s team decided on the fly who would do what task during the contest. For example, the person at the keyboard might be the one who came up with the solution for a problem, the one who understood it the best, or the one who could write it the fastest. Gennady usually took the easy problems since he was the fastest at those. He also coded more problems overall than his two teammates.
- Gennady’s father taught him programming, but didn’t pressure him to practice. Even so, in school competitions he competed with students several years older than he was.
- In his early training, he could spend half a day practicing, but now he only spends a few hours per day.
- Comparing Java with C++: Java executes more slowly, but is a stricter language, which can allow the compiler to catch programming errors that the C++ compiler ignores.
- Gennady has a good relationship with Petr Mitrichev. He points out that they’re just competing over ratings. They’re not business rivals.
- Although his talent was obvious from a young age, he believes that you can’t become #1 at competitive programming by accident. It takes a lot of effort even when you’re talented.
He may not be a competitive programming household name like Petr or Gennady, but Xiao Mao (matthew99a, matthew99) is in the top 50 on Topcoder and Codeforces, which isn’t bad. Here are some tips from a 2017 Topcoder interview:
- “For most of my career, I spent nearly whole days on programming.” That’s a bit vague, but it’s similar to the practice times reported by other successful competitors. There doesn’t seem to be a way around that dedication to practice, especially early in a contestant’s practice years.
- In a contest, it’s beneficial to find easier problems to start with in order to build confidence: “Working on a tough task when you have already solved others is much less stressful than doing it in the beginning.”
- How long to spend on a problem: Mao can spend several days on hard problems. (For easy problems, he starts coding immediately). He considers himself better at solving problems on paper, and not as good at implementation. Hence his motto: “Think twice, code once.”
- How many practice problems to solve: “Your level of skills don’t depend on how many tasks you’ve solved, instead how you’ve solved them.” Start by trying to solve each problem on your own. If you get stuck, read a bit of the solution until you’re unstuck, then go back to solving it on your own. When you’re done, go back and figure out what caused you to get stuck. That’s the topic you need to work on if you want to get better.
- More advice to beginners: “Don’t try to copy others. Everybody has his/her own way of solving tasks.” That’s another reason not to read the whole solution at once. With a few hints, you might come up with a solution on your own that better matches your problem-solving style.
Amr Samir and Mohamed Mahmoud Abd El-Wahab
- Some things aren’t taught in courses, but have to be learned from experience. For example: which BST to use in a contest; which value to fill a DP array with before using it; common mistakes when reading a graph as input.
There’s no reason that someone couldn’t put this kind of knowledge in a course or book. And books/courses on competitive programming do exist. But experience is still more valuable than just reading about programming.
- A benefit that a coach provides: they can suggest the right problem to solve when you need to learn an algorithm or technique. By solving a problem rather than just studying the algorithm/technique in isolation, you learn it well enough to use it on the next problem that needs it.
Textbooks also try to do this. For example, one of the main features of Competitive Programming 3 is the list of categorized problems.
- Experienced competitive programmers learn where to put their breakpoints to get the information they need to find bugs.
Petr also mentioned this skill, in the context of invariants.
Balajiganapathi Senthilnathan says that although every top competitive programmer has slightly different techniques, one technique they all recommend is upsolving, the practice of solving contest problems that you couldn’t finish during the timed event.
This is a special case of the general advice to learn by solving problems. In theory, you could find practice problems anywhere. But solving problems from a contest you already invested time in may be more motivational.
Abhinav Shrivastava doesn’t like questions of the form “How Did X Become a Top Competitive Programmer” because 1) Every person’s path was different (and there’s no point in trying to copy it exactly); and 2) Although some details of their training were different, they always used a version of the following process:
- Pick an algorithm or data structure.
- Find a textbook section, blog post, or web article that helps you learn it.
- Code your own implementation, and add it to your personal algorithm repository.
- Find 20-30 problems that use it and try to solve each one.
- When you get stuck on a problem, look for help, but be sure to implement your own solution once you understand what you need to do.
- Participate in contests. Upsolve the problems you couldn’t solve during the contest.
It’s not bad advice. I would rearrange it a bit by trying to solve a problem before creating a reference implementation for an algorithm, since implementations made in isolation aren’t always useful in contest problems. But it’s true that using a problem-solving approach provides far more benefit than reading about one more process that a successful contestant used.
Nevertheless, if you’re already using a problem-solving approach, then reading about other people’s experiences can give you some ideas about how to implement each step. For example: For step 1, you might want to know which algorithms to learn, and in what order. For step 2, good sources to read about algorithms. For step 3, implementation suggestions. For step 4, which online judge has the best list of categorized problems. For step 5, how long to work on a problem, and where to find solutions. For step 6, which contests are best for your goals. So the Quora questions and answers continue to accumulate.
Here’s the CPFAQ page for this question: How did (person) become a top competitive programmer?
(Image credit: Ben David)