The Story So Far
Long ago (2008), I read a post on the “xkcd blag” (yes, Randall Munroe occasionally just writes regular blog posts) about “a site with a lot of math-oriented programming problems that you can solve in any language.” I like math and programming, so that seemed like fun. I spent a few years on and off working through the first 76 problems on Project Euler, at which point the problems started to require more math than I had at my disposal. Around that time (2011), I heard about a site called CodeEval that was coming out of beta. CodeEval also has programming puzzles, but with less of a math emphasis. As I’m writing this post (early 2015), I have finished 107 puzzles on CodeEval. Back in 2011, a site called CoderCharts (no longer online) was briefly popular. CoderCharts hosted contests that ran over several days, like the long contests on CodeChef. That was my first experience with contests that allowed participants to compete against each other during an event. However, the schedule allowed a day or so for each problem, so there was plenty of time to think.
Most competitive programming contests happen over a period of hours. To get an idea of what those are like, I tried out some archived problems on CodeForces, a popular site where contestants are given five problems to solve in two hours. After trying a few of those, I realized that I needed a more structured training approach if I was going to get serious about this programming puzzle thing. But things were busy at work, so I just made the occasional CodeEval submission instead.
Fast forward to 2014. I stumbled on the Competitive Programming topic on Quora. It turns out that for general questions about competitive programming, this is the place to be. (Specific questions about code get better answers on Stack Overflow). Quora’s competitive programming topic is full of duplicate, incomprehensible, and inane questions and answers, but also has many gems — for example, Nick Wu’s answer to “How do I manage time in programming competitions?”. More of my favorites are listed later in this post.
A Book to Explain Everything
Readers of Quora’s Competitive Programming topic often ask for book recommendations — i.e., what books should I read to get better at competitive programming. I love the idea of a book that explains everything (even though they rarely do), so I looked through these questions. I found that people were discussing books in three categories:
- General algorithms books
- Books about competitive programming
- Books about coding interviews
Books in category 1 are good to have around for reference, but they’re too general to serve as the only resource for someone who is trying to get started in competitive programming. Books in category 3 can be useful given the similarity between coding interviews and competitive programming. Also, who can’t use a bit of extra interview practice. But it turns out that a few people have written books specifically about competitive programming. The two such books that appear repeatedly in Quora answers are:
- Competitive Programming 3 (the number at the end means “3rd edition”, not “volume 3”; there’s no need to read the first two) by Steven and Felix Halim
- Programming Challenges by Steven S. Skiena and Miguel A. Revilla
While these are both are worth looking at, they are dense textbook-style books, so it’s only realistic to concentrate on one at a time. With that in mind, I decided to go with the Halim book (let’s call it CP3) over the Skiena/Revilla book (let’s call that one PC), for a few reasons:
- CP3 was published in 2014, and the authors say they’re going to write a Competitive Programming 4, so it feels like it’s a living project. PC was published in 2003.
- PC gets mixed to slightly positive reviews on Amazon. The ratings for CP3 on Lulu (the site the authors have chosen to sell it on) are higher. Neither book has a large number of reviews due to their niche audience, but this is one data point.
- This Quora answer recommends CP3 over PC for developers with moderate experience, though it says that both books are good.
- The problem submission and tracking web site for CP3 is more feature-rich than the analogous site for PC.
With those points in mind, I bought a copy of CP3. (A free version of the first edition is also available). The advantage of both of these books compared to general algorithms texts is that they are organized around problems that have appeared in programming competitions. Therefore, the reader learns the algorithms topics in conjunction with practice problems that can be submitted through an online judge. I have used algorithms textbooks with traditional end-of-chapter problems, and I can say that having an online judge check your work is extremely convenient.
The problems listed in CP3 are almost all from the University of Valladolid (UVa) Online Judge, an ancient (est. 1995) repository of competitive programming problems. Compared to modern competitive programming sites, it’s quite primitive. It accepts a limited set of languages — C/C++, Pascal, and Java. Site outages happen. Submission failures can be hard to debug. On the other hand, it’s a well-known site so it’s easy to find help with the problems. And, conveniently for our purposes, people have written books based on its problems.
UVa has over 4000 problems. CP3 narrows those down to about 1675 recommended problems, organized so that they reinforce the concepts discussed in each chapter. A subset of those are designated as “starred problems.” In math textbooks, a starred problem means “good luck figuring this one out.” In CP3, the authors say it means “must try.” I interpret that to mean that if you solve all of the starred problems, you have demonstrated a good understanding of the material in the book. There are 462 starred problems in nine chapters (as shown in the image at the top of this post). That seems like a manageable number, so my plan is to read through CP3 and implement each of those 462 problems in Java. Why Java? I use C# (aka “Java without the annoying parts”) at work, and I’d rather focus on problem-solving and algorithms than the details of a less familiar language. I have already solved and submitted the first 20 problems just to get an idea of what they are like. My thoughts so far? I’m going to have to get a lot faster at these if I’m going to finish the remaining 442 in any reasonable timeframe. Fortunately, solving problems faster is one of the main goals of practicing competitive programming problems. You can follow my progress on uHunt.
In Deliberate Practice for Software Developers, I outlined a system for practicing software development using competitive programming puzzles. Using the 462 problems, I’ll be fine-tuning this process, and presenting the results here. I’ll refer to this effort as Project 462, since that’s such a catchy name. With any luck, I’ll finish before CP4 comes out and adds more problems.
The subtitle of CP3 is “The New Lower Bound of Programming Contests.” The authors aren’t claiming that reading their book (and working through the problems) will make you a competitive programming expert, just that it will teach you the basics. I find this to be an honest admission on the part of the authors, and also an indication of how much work it takes to learn the fundamentals of competitive programming.
Over the past month, I have kicked off this blog with four posts about improving your programming skills through deliberate practice:
- Making Sense of the Deliberate Practice Debate: a report from the nature vs. nurture wars.
- Coding is Underrated: in defense of a software developer’s fundamental skill.
- Deliberate Practice for Software Developers: a process for getting better at coding.
- 12 Reasons to Study Competitive Programming: an endless supply of practice material, with added benefits.
Over the coming year, I’ll continue to publish one post per week with my latest ideas about programming practice. In addition to general ideas, I’ll now be able to include specific examples from the CP3 problems and other programming puzzles. That will ensure that I don’t get too caught up in theory, and that these ideas are useful for their intended purpose.
Getting Started with Competitive Programming
The most popular type of question on Quora’s Competitive Programming topic is some variation on “How do I get started with competitive programming?” or “How do I get better at competitive programming?” Some excellent answers were written in the early years of the topic, but people keep asking (and answering) similar questions, which clog up the feeds and make it difficult to find the best answers. Quora doesn’t provide an equivalent service to the Stack Exchange Data Explorer or the Stack Exchange Data Dump. This means that users can only search Quora in ways that are supported by the standard Quora UI. For example, I would really like to list all answers in the Competitive Programming topic in descending order by total upvotes. This would help to find the best content without relying on someone flagging it manually or the Quora algorithms bumping it to the top of the feed. One technique that could provide similar results, and which has better support in the Quora UI, is finding good answer writers and then looking through their answers. The standard way to do this is by following people. But that gives you all of their activity, which may not be what you want. For a more targeted search, Quora lets you list a person’s answers for a particular topic. Here’s an example of how to use that feature to find good Competitive Programming content:
- Open the Followers page for the Competitive Programming topic. This lists everyone who follows the topic. Competitive Programming has tens of thousands of followers, so fortunately the list is sorted. The sort criteria seems to be some combination of how many followers a person has, and how many answers they have written for the topic.
- Starting at the topic of the page, click on each follower’s “View n Answers” link to see their answers. For example, right now Brian Bi is at the top of the list. All of his Competitive Programming answers are on the Brian’s Answers about Competitive Programming page.
This is a roundabout way to find the best answers. It will miss highly-voted answers from users with few followers, though you can often find these as answers to the same questions that the high-follower users participate in. In any case, I have found the technique useful for finding good answers from experienced competitive programmers. Here are a few examples:
- What are the steps to be taken to become a good TopCoder?: advice from Nick Wu on which TopCoder problem levels to focus on as you get better.
- How do we get better at preparing for programming contests?: Nick Wu’s suggested practice method, based on identifying and improving your weaknesses.
- How can people code the easy problems so quickly on Codeforces/TopCoder?: Michal Forišek explains fast submission techniques.
- What are the best guidelines for testing a program you just finished coding on ACM-ICPC competitions?: summary: use a diff tool.
- How much work did it take to get on the US IOI team?: Richard Peng solved 750 practice problems to accomplish this.
- How should I go about starting, improving, and ultimately acing TopCoder competition: Mark Gordon recommends the USACO training pages.
- How do you debug your code quickly in programming contest environments?: a great checklist from Nikhil Garg.
- How should I practice so that I will be at a level where I can approach TopCoder’s Div1-500 problems with confidence?: a classic question from the early days of the Competitive Programming topic. Nikhil Garg’s and Michal Danilák’s answers are full of useful advice.
- Finally, a quote from Michal Danilák: “Training for competitive programming works like a funnel – no matter where you start, it will eventually get you to the same place. The most important thing is to start and keep going.” So don’t spend too much time reading Quora.
And there are plenty more where those came from.
So one way to find answers to the get started/get better question is to read Quora. The best Quora answers to these questions provide targeted advice from someone with experience in competitive programming, such as a high-ranked TopCoder or CodeForces member. Generally you’ll be able to read through one of these answers in a few minutes. For a much more in-depth answer, you can read books like Competitive Programming 3 and Programming Challenges. If you solve the problems recommended in these books (which is the only way to get much out of them), they could take a year or more to complete. One of my goals in writing about the 462 starred problems in CP3 is to provide another source of information for people who are interested in competitive programming, but aren’t sure about the best way to get started or improve their current skill level. Jeff Atwood sometimes talks about online posts as a public research notebook that others can learn from. Consider this a record of my research on how to use competitive programming to get better at programming.