What is competitive programming?

Rating Distribution

What is competitive programming? Here are a few definitions.

From Wikipedia:

Competitive programming is a mind sport usually held over the Internet or a local network, involving participants trying to program according to provided specifications. … A programming competition generally involves the host presenting a set of logical or mathematical problems to the contestants … [who] are required to write computer programs capable of solving each problem. Judging is based mostly upon number of problems solved and time spent for writing successful solutions, but may also include other factors.

From experienced competitive programmer Ashar Fuadi on Quora:

Competitive programming is solving well-defined problems by writing computer programs under specified limits.

From Competitive Programming 3, Chapter 1:

The core directive in ‘Competitive Programming’ is this: “Given well-known Computer Science (CS) problems, solve them as quickly as possible!”.

Competitive programming is still not a mainstream practice in the larger programming community, as demonstrated by some of the Stack Overflow comments from last week. Nevertheless, it is notable enough to have its own Wikipedia article and Quora category, and several books have been published on the topic.

But when I’m writing about competitive programming here on this blog, I often find the definitions quoted above to be too restrictive. That’s why I sometimes use the term programming puzzle instead. Here’s how I would adjust Ashar Fuadi’s definition to describe that term:

A programming puzzle is a well-defined problem that is designed to be solved using a computer program.

While it might be convenient to talk about “programming puzzle enthusiasts” rather than “competitive programmers,” that’s a bit cumbersome, and it’s not a term that people tend to use. So for this article, I’m going to stick with “competitive programming” and “competitive programmers,” while still tweaking the definition a bit.

To demonstrate the benefits of using a definition that doesn’t involve time or memory limits, I’m going to describe a system of levels for competitive programmers. As we move through the levels, the definition of “competitive programming” changes. And this is not just a semantic exercise. People at different levels really do experience “competitive programming” in very different ways.

Note that these levels are not the same as the levels that software companies use to track developer seniority and compensation. There is some correlation between these two level-based systems at the lower levels, but eventually they diverge: The skills that experienced competitive programmers use to win contests are not required by most employers. And the skills that distinguish senior developers from their less experienced colleagues don’t make much difference in the top tier of a programming competition.

Let’s start with someone who is just learning to write code.

Level 0: Learning to Code

A programmer at this level is writing their first lines of code, and learning about the idea of programming. They may be submitting their first Codecademy. Khan Academy CS, or Code.org exercises, or investigating what it takes to write a mobile app for their favorite platform. If they are using programming puzzles to practice, then they aren’t worried about time and memory limits, since the easiest puzzles can be solved without considering code efficiency. Usually what they’re working on are not really “programming puzzles,” but rather “programming exercises,” which are designed to teach basic syntax and programming concepts.

Level 1: Learning a Language

At this level, a programmer is focusing on a particular programming language and its idiosyncrasies. When they’re solving a programming puzzle, the hard part is still the process of translating their solution into code, because they’re still not comfortable with the syntax. They may be spending a lot of time on Stack Overflow looking at code examples and learning how algorithmic concepts are expressed in the language they’re using.

Level 2: Becoming Fluent in a Language; Learning Problem-Solving Techniques

This is the level at which a programmer becomes truly comfortable with a language. Once they reach this level, they spend less time looking at Stack Overflow or language references, since they have internalized all of the language constructs that are required to solve programming puzzles. Now that they don’t have to think much about how to express their solution, they can focus mainly on problem-solving skills. The process of solving puzzles has its own techniques and practice routines, regardless of whether the puzzles involve any programming. Progressing beyond this level requires spending time learning problem-solving techniques, since it’s not possible to solve puzzles at Level 2 just by coding fluently.

Level 3: Studying Problem Patterns; Writing Code Quickly

At this level, programmers have to study programming problems the way a serious chess student studies example games: with the goal of learning patterns. Contest authors don’t have an unlimited number of programming problem ideas. Experienced competitive programmers have seen enough problems that rather than starting from scratch with each one, they can relate it to a problem that they have previously solved.

Once a programmer can quickly spot a familiar puzzle type and recall an applicable implementation, they need to be able to code it quickly. That’s where typing speed comes into play, along with macros, short variable names, and other techniques that can get you in trouble on Stack Overflow.

Level 3 is the first level that for the most part is specific to competitive programming. While the skills learned in previous levels are useful for any kind of programming, there’s not much point in spending time on Level 3 other than to do better in contests. One exception may be practicing for technical interviews, but that’s usually a short-term project that stops once you get the job. And many developers can do well in interviews without the amount of practice required to get past Level 3.

Level 4: Competing

Some skills are best learned in the high-pressure environment of a live contest. You can practice coding quickly on your own time, but when the countdown timer is running in a contest, there’s an extra level of urgency that helps you figure out where your weak points are. Contests that allow you to challenge other contestants’ submissions also provide a type of practice that is difficult to simulate offline.

Some competitive programming enthusiasts even give up offline practicing entirely, and spend all of their competitive programming time in contests.

Back to Definitions

The Competitive Programming article on Wikipedia basically describes Level 4. It focuses on competitions, competitors, and contest sites. This is a reasonable way to approach the topic, and getting too far from the standard definition would probably be considered original research and flagged by the Wikipedia police. Nevertheless, it does reinforce the idea that everyone who is involved with competitive programming is at Level 4. In reality, most people are probably between Level 1 and Level 2. Some evidence of this is the rating distribution (see the image at the top of this post) that appears on every TopCoder member profile page. This distribution is skewed to the left (positively skewed), with the large majority of contestants in the lower ranks (grey, green, blue) and a long tail of red and yellow contestants: currently there are 46% grey, 30% green, 16% blue, 7% yellow, and 1% red contestants. The types of questions that appear in the Competitive Programming topic on Quora also support the conclusion that there is a large population of beginners looking for basic answers about the topic, and only a few people who are serious competitors.

Code Chefs

A Quora user once asked Dr. Thomas Cormen, co-author of the well-known Introduction to Algorithms textbook, what he thought of competitive programming. He started his answer by focusing on the Level 4 definition: “I write programs to solve problems, not to demonstrate that I’m better than someone else at programming.” But he then compared competitive programming to competitive cooking, and pointed out that one reason to watch a cooking competition is to pick up ideas from creative people. I think this is a great analogy. Programming competitions are one of the only times that you get to compare creative solutions to the same problem from many different programmers. And this is just one of the benefits of competitive programming (number 12, as it happens), most of which don’t depend on a Level 4 approach. So although we’re probably stuck with the name and its associated baggage, it doesn’t hurt to remind people once in a while that there’s more to competitive programming than just competition.

(Image credit: from the TopCoder member profile page of some guy from Harvard with the handle mzuckerberg)