Red-Green-Code

Deliberate practice techniques for software developers

Project 462

By 7

462 stars

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:

  1. General algorithms books
  2. Books about competitive programming
  3. 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:

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.

Starred Problems

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.

Project 462

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.

RedGreenCode.com

Over the past month, I have kicked off this blog with four posts about improving your programming skills through deliberate practice:

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:

And there are plenty more where those came from.

Research Notebook

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.