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.
Questions that are too specific to one person’s situation don’t work well on Quora. They tend to be non-canonical duplicates that are fishing for ultra-personalized advice that’s unlikely to help future readers. Often they include a long personal story.
Answers, on the other hand, can benefit from writers who are willing to share their life experience. In the competitive programming topic, several people have described how they made the journey from beginner to expert level in the world of programming contests.
Anudeep Nekkanti is a former Google employee (2014-2016) who left to pursue more entrepreneurial interests. In 2013, he wrote two Quora answers about his competitive programming training process. During his competitive programming career, he competed in the yellow range on Topcoder, the purple range on Codeforces, and the orange range on CodeChef.
A popular competitive programming training technique suggests that students should learn an algorithm and then practice problems that use that algorithm. Anudeep dismissed that approach, writing, “If you know what algorithm to use you generally think in that direction and leave about correctness.” I think what he means is that if you know a problem is designed for a particular algorithm, you focus on fitting the problem to that algorithm, rather than reasoning about the correct way to solve the problem. To put it another way: the algorithm-first approach lets you practice implementing algorithms, but it doesn’t help you get better at deciding which algorithms to use.
Rather than selecting practice problems by topic, Anudeep selected them by difficulty. In his early training, he used this SPOJ query to find and solve 300 problems in order from easy to hard. By solving these problems, he improved his C++ and STL skills, learned standard competitive programming terminology and algorithms, and got better at solving problems quickly.
On the question of how long to work on a problem, Anudeep is on the high end. In his early practice, he would first spend one to four hours on a problem. If he couldn’t solve it in that amount of time, he would put it aside for an entire month before coming back to it, working on other problems in the meantime. If he couldn’t think of any new ideas when he picked it up again, he searched for hints. In some cases, he found that the problem required an algorithm he hadn’t yet studied, so he would look for online resources on the algorithm.
Although competitive programmers eventually need to learn how to select the right algorithm for a problem, I don’t think the early stages of practice (the first few hundred problems) are the right time to do this. Instead of burning through tens of hours struggling with problems that you don’t have the background to solve, it’s better to spend that time learning new algorithms. Then once you know the standard algorithms, use contests to practice matching them with the right problems.
While Anudeep started his competitive programming training without a math or programming background, Goutham studied for math and programming Olympiads in high school. Here’s how he describes the role of math in competitive programming:
Almost every good competitive programmer has a strong math background. And everyone at the very top (targets in Topcoder and International Grandmasters in Codeforces) are unbelievably good at math. That doesn’t mean they have done thousands of mathematical problems in online judges. I believe they know most things that only a pure math student would read, and one that most engineering students would not bother to read as it is not useful for their career. Their use may not be very obvious when we do CF/TC problems but I bet the thinking that helps solve very hard algorithmic problems is built by doing pure math or theoretical computer science. Doing olympiad math earlier is probably the reason I am able to understand solutions to algorithmic problems quickly now.
For problem selection, Goutham combined the topic approach with the contest approach. To practice implementing algorithms, he found appropriate problems using the IARCS Problem Archive. But he also discovered the benefits of learning from contests. He noticed that he could learn multiple topics in one session if he upsolved the contest, taking time after each contest to study and solve the problems he didn’t complete. He also found himself more motivated to pursue contest practice. It was more fun to take part in a contest than to solve problems on his own. He used the Contest List site to track the contest schedule on multiple online judges, giving him plenty of opportunities to practice.
Once he was more experienced, Goutham supplemented his contest participation by setting (writing) HackerRank problems, reading people’s code as they submitted it to contests, writing problem editorials, and coaching a training camp. This experience made him realize that “when you teach something to someone, you really get it.”
Lalit Kundu is currently at Google, working on YouTube Premium. He qualified for ACM-ICPC World Finals 2015 and is rated purple on Codeforces and yellow on CodeChef. In an answer from 2015 on Quora, he tells the story of how his team prepared for ICPC 2015.
Since he was preparing for a team contest, Lalit’s answer focuses on team preparation. He and his team used the Codeforces Gym to complete about past 20 contests, comparing their performance to that of the teams in the original contests. To avoid getting discouraged, they did a mixture of easier and harder contests. Their schedule was grueling: midnight to 5 AM for the contest, and then more time the following evening to upsolve the problems they couldn’t get during the contest. (I’m not sure when classes or sleeping happened). In the end, they won their regional contest, but a team from their university did better in another India region, so the other team went to World Finals.
While some practice stories focus on how many problems to solve, this one illustrates the commitment and focus required to prepare for the “oldest, largest, and most prestigious programming contest in the world.”
(Image credit: John Jones)