We have arrived at that time of the year when students leave behind their regular academic schedules and take up summer activities like bike riding, taking long walks on the beach, and learning competitive programming. Last week, a reader sent me an email asking for advice on the best way to spend two months practicing algorithmic problem solving. Here are some ideas for others who may be interested in pursuing that as well.
How to Learn Competitive Programming
The only way to get better at solving programming puzzles is to solve programming puzzles. There’s no secret path to avoid that hard work. But there are different practice methods and sources of puzzles, and some work better than others.
Algorithmic programming contest problems are drawn from a limited set of categories. Problem setters don’t ask contestants to attack unsolved research problems, or problems that can only be solved using algorithms that were just invented last month. The harder contest problems require creative application of common algorithms and techniques, but the algorithms and techniques themselves aren’t obscure.
So training for programming contests involves taking the types of problems that you’re likely to find on contests, and then solving enough of each type that you can:
- Recognize the category that a problem belongs to based on its problem statement.
- Deploy the technique or implement the algorithm that is most appropriate for the problem category.
- Learn the problem-solving skills required to convert a general solution category into a specific solution for a new problem.
There are two approaches to finding and solving programming puzzles:
The contest approach: Find a contest. Solve as many problems as you can. Look up editorials or other contestants’ solutions for ideas on solving problems that you have trouble with. Repeat.
The textbook approach: Find a source of categorized problems. Read about an algorithm or technique in a book or online source. Pick a problem that uses that algorithm or technique. Solve it to the best of your ability. Look up an editorial or solution for ideas on how others approached the problem. Repeat.
The advantages of the contest approach are: 1) You learn how to solve problems under pressure; and 2) You practice selecting the appropriate algorithm or technique for a problem. But as regular readers of this blog know, I prefer the second method. I like the more structured approach of learning a topic and then practicing it, rather than the random approach of using whatever problems happen to appear in a contest. There will be plenty of time to use the contest approach once you’re familiar with all of the common problem types. When you get to that point, you’ll be ready to practice contest-specific skills like coding under time pressure and challenging other contestants’ solutions.
There are many sources for contest problems, but if you’re going to use the textbook approach, you need a source of problems that’s organized in the right way. One such source is uHunt. It has an actual textbook (Competitive Programming 3). But more importantly, it has many well-categorized problems and a tool (uDebug) to help test your solutions. It’s also reasonably popular, which means you’ll have a good chance of finding help in forums or blog posts. If you’re happy writing your solutions in C, C++, or Java, it’s worth a look.
A Practice Process
Once you’ve selected your problem source, you need a process. Unlike working on a programming side project, competitive programming doesn’t provide you with an app or service that you can gradually add features to. Instead, you’ll have a lot of miniature programs that you’ll work on for an hour or two and then throw away. So you need some other way to set goals and track your progress.
Almost every online source of programming puzzles will tell you how many problems you have solved over time. So that might sound like the logical metric to use as a goal. The problem with that approach is that problems vary widely in difficulty, even when they have the same difficulty level rating. You don’t know for sure when you start a problem whether it’s going to take you one hour or five hours. And some days you may not work on problems at all, because you’re reading about a new algorithm or technique. That makes it difficult to set goals based on the number of problems you solve.
Instead, I would recommend setting a goal for how many hours per day you want to practice. You can use a fixed number, or a more flexible system like Time Bank. If you set and meet your time goals, you’ll learn what you need to learn and you’ll get your practice problems solved. Fixed time goals are also important so you don’t get overwhelmed by an unlimited amount of work every day, which is not a good way to get motivated to learn.
Your Summer Project
In summary, here’s a plan for your summer learning project in competitive programming:
- Pick a source of well-categorized programming puzzles, like uHunt.
- Based on your summer schedule, pick a target number of hours per day for study. Find a way to track your time, like the Time Bank spreadsheet or old-fashioned paper.
- Find a topic that you could use some practice on, or just start with the first topic in your list.
- Find an easy problem in that topic. If your problem source doesn’t rate problems by difficulty, pick one that a lot of people have solved.
- Solve progressively harder problems until you’re comfortable with the topic.
- Move on to the next topic. Repeat. See how far you can get by the end of the summer.
If you’re having trouble staying focused, remind yourself of the benefits of competitive programming practice. My favorite is #6: It’s a way to focus on the fundamentals of algorithmic problem solving. See which one you like best, and remind yourself of it as you sit down every day to work on your time goal. Good luck!
(Image credit: Floyd Manzano)