This post is part of a series of commentaries covering each chapter of Competitive Programming 3 by Steven and Felix Halim. You can find the rest of the posts in the series by visiting my CP3 post category.
Many of the problems in the UVa Online Judge are taken directly from past ACM-ICPC contest problems. If you’re preparing for this contest or the IOI (which targets a subset of ICPC content), it makes sense to be familiar with these problems. But even if you’re planning to compete on platforms like TopCoder and CodeForces, it can be useful to train using UVa OJ problems, despite the platform’s quirks. Competitive programming problems tend to cover similar topics regardless of the contest platform, especially when it comes to easy and medium problems. The difference is mainly about which topics are emphasized more.
Because UVa OJ has been around for a while, several books use its problems as exercises. One of these is Competitive Programming 3 (CP3), the companion book to the uHunt site. Last week I wrote about the Chapter 1 uHunt starred problems. This week I’m going to cover some highlights from the corresponding chapter in the CP3 book. I’m using the 3rd edition, but you can find similar (but older) content in the free 1st edition ebook.
Competitive Programming Practice Advice
While practice is the most important ingredient for competitive programming success (as repeated endlessly on Quora), it doesn’t hurt to have some tips and guidance to inform your practice. That’s the idea behind CP3. It combines aspects of an algorithms textbook, some tips and advice specifically for competitive programmers, and a set of recommended exercises highlighting the most useful and interesting problems from UVa OJ.
CP3 defines competitive programming as the process of solving well-known computer science problems as quickly as possible, with the objective of becoming a better programmer or computer scientist. So the problems have all been previously solved, and are designed to be solvable under time constraints. Therefore, preparation for programming competitions is about learning a subset of the CS curriculum, and then applying that knowledge by writing short programs under exam-like conditions. Given that, it’s not surprising that competitive programming is most popular among high school and college students. One aspect of competitive programming that can be compared to real-world programming is the set of secret test cases. CP3 compares these test cases to the unpredictable behavior of the users of a real-world program.
CP3 describes five types of competitive programmers based on their approach to solving UVa 10911: Forming Quiz Teams. The programmers range from a clueless beginner to a TopCoder target. Just as using the correct algorithm can mean the difference between a runtime measured in centuries and one measured in seconds, the appropriate competitive programming training can turn a seemingly impossible problem into one that can be solved and implemented in under 30 minutes. For beginning competitive programmers, competitive programming is not just about coding faster than someone else. The knowledge gained in the early stages of training can make entirely new problems solvable.
CP3 Chapter 1 provides seven general tips for competitive programming success:
1 – Practice typing
Typing practice for programming is like regular typing practice, but with an emphasis on the special characters used in code. Being able to type fast isn’t sufficient on its own, since you still have to be able to solve the problem and known how to implement it. But it can be a tiebreaker between you and people with similar problem-solving abilities. There’s more discussion on Quora about the relationship between typing speed and competitive programming.
2 – Learn to identify problem types
CP3 and uHunt are mainly organized around solving problems by type. This contrasts with alternative strategies like solving problems from easiest to hardest (which uHunt also supports with its “Next Problems to Solve” grid), or just participating in competitions (solving the problems that happen to come up in contests during a given week). The problem type approach works because programming competitions cover a finite set of topics. By studying a few examples of each topic, you can learn the techniques that apply to that type of problem.
Even a competitor who is well-versed in all of the standard algorithms won’t be able to solve harder problems just by typing out some familiar code. Medium and hard problems are designed to require problem-solving skills in addition to algorithm knowledge. As with competitive programming skills, it’s possible to develop problem-solving skills just by solving a lot of problems. But it’s more efficient to also read some general problem-solving advice.
The execution time limit for a problem is the amount of time that an online judge allows a program submission to run. For example, many online judges terminate execution of a submission after three seconds. This time limit, in conjunction with the input range chosen by the problem author, has a lot to do with why competitive programming problems are challenging. If a competitor only had to solve a problem for very small inputs (like the sample input), they would often be able to solve it with a brute force algorithm. Since brute force algorithms are generally easier to implement than more sophisticated algorithms, many problems that are difficult with large input values are easy with small ones.
Since online judges use a time limit, algorithm analysis is important when deciding how to solve a competitive programming problem. You want to have your submission accepted on the first try without exceeding the time limit, but you don’t want to use extra time implementing a more sophisticated algorithm than necessary. Making the right judgement call requires knowledge of algorithm analysis and how to translate the time complexity results to real-world runtime. CP3 suggests using 100 million operations as a rule of thumb estimate of what an online judge can execute within a typical 3-second time limit.
As an algorithm becomes more complex, it also gets more important to “prove” (or at least demonstrate to your satisfaction) that it will produce the correct result for any legal input. This can be a better use of time than trying to find bugs using tricky test cases.
4 – Master your programming language
Mastering a programming language (or at least a subset of one) is one of the beneficial side effects of competitive programming practice. The CP3 authors make a few interesting sub-points in this tip:
Although C++ provides speed benefits that Java can’t match in the competitive programming context, there are some essential Java library functions that still aren’t available in the C++ STL. I have mainly been using Java for my practice, and so far have only run into one problem (UVa 195 – Anagram — see Lessons from uHunt Chapter One) that I wasn’t able to submit in Java due to performance limitations. We’ll see how that plays out in future chapters.
Implementation should only take up a small subset of the time you spend on a competitive programming problem. This has been discussed on Quora as well.
5 – Learn testing techniques
In addition to using the algorithm analysis and proof techniques suggested in tip #3, the other way to improve your chances of getting an Accepted verdict is to practice thinking like the problem author who wrote the test cases. Besides avoiding Wrong Answer verdicts, the other advantage of catching bugs with your own test cases is that you can see what those test cases are. The judge’s test cases, on the other hand, are secret, so it’s hard to use them for debugging.
This tip provides a few reminders of the types of test cases that problem authors use:
- The sample test cases. Be sure to compare the expected output to your own output using a diff tool, to catch differences that are harder to see, such as those related to whitespace.
- Two consecutive identical test cases, to catch variable initialization problems. Alternatively, you could write a code template designed to avoid this problem by isolating the code for each test case iteration.
- Extreme or special values: 0, 1, negative values, values at the limits provided by the problem description, values that produce overflows in intermediate calculations, and so on.
- When using large test cases, try to find one that you can verify manually. When you get this one to match your manual calculation, try a random large value. You won’t be able to verify it manually, but you can verify that your program doesn’t crash or produce clearly incorrect results.
- Test badly-formatted input, such as input with extra whitespace. (See Lessons from uHunt Chapter One for tips on avoiding bugs related to input whitespace).
- There are software engineering books that focus on software testing, and provide other techniques and ideas.
Also in this tip is a review of the steps for solving a competitive programming problem:
- Identify the problem type.
- Design an algorithm to solve this variation of the problem.
- Use algorithm analysis to verify that your algorithm will run within the judge’s time and space limits.
- Implement your algorithm.
- Test your algorithm.
This process has some overlap with the problem-solving process that I wrote about last month, but steps #1 and #3 aren’t in my process, so I’m going to add them to my problem-solving template.
6 – Practice
This one is self-explanatory. In this tip, the CP3 authors provide a list of some of the major online judges.
7 – Learn to work in a team
This tip advises competitors to practice coding, debugging, and preparing test cases on paper. It is mainly applicable to ICPC teams, which only have access to one computer during a contest. It’s also good advice for programmers who are preparing for a coding interview, which often takes place away from a computer and features problems similar to those used in programming contests.
The Practice Problems
CP3 is organized around practice problems, so Chapter 1 covers the basics of a competitive programming problem. Problems, especially those from the same online judge, tend to have a predictable structure:
- A problem description, which may require you to filter through an elaborate story in order to extract the relevant details.
- A description of the input/output formats and constraints. There are a few possibilities for input format, which differ in details such as how test cases are delimited. Similarly, output formats may require blank lines in specific places, or numbered output sections.
- Sample input/output that only exercise the most basic aspects of your solution.
- Some additional information or hints (optional).
The Chapter 1 problems are categorized as “ad-hoc,” which means they generally don’t require techniques from the other CP3 chapters. They aren’t necessarily easier than the problems from the other chapters, except insofar as they require less specialized knowledge.
CP3 Chapter 1 points out that programming contests tend to include a higher proportion of ad-hoc problems relative to other problem types. The authors don’t discuss why that is, but they do mention that ICPC teams who can only solve ad-hoc problems typically end up in the bottom half of the rankings. So one theory is that these problems are included to give all teams a chance to solve some problems. Problems that require more specific algorithms skills can then be used to distinguish between teams in the top half of the rankings.
For casual competitive programmers, or programmers who are using programming puzzles to improve their general coding skills, ad-hoc problems can also be useful. There’s a lot to be learned from easier problems. The benefits of competitive programming practice don’t come only from studying specialized algorithms.
In addition to classifying problems according to the major categories specified in the chapter titles, CP3 and uHunt use numerous minor categories to classify UVa OJ problems. In Chapter 1, examples of minor categories are Chess, Palindromes, and Anagrams. A student could specifically study these categories as well, though as the categories become smaller, the benefit is also reduced. However, some problem sub-types do tend to come up more often than others in contests and coding interviews. It can be helpful to familiarize yourself with these so you don’t have to figure them out from scratch under time pressure.
CP3 Chapter 1 in Review
Chapter 1 provides a good introduction to the types of ad-hoc problems found in programming competitions, along with some tips to jump-start the process of solving them. Even for someone who has experience with competitive programming, it’s worth taking a look at.