Very loosely inspired by some comments on Thoughts on Reaching Cyan? and my recent AMA.
Until now, I've avoided telling beginners to practice math before working on competitive programing problems because I haven't figured out a helpful way of doing so. This post is my attempt at telling grays to train math first in a way that might lead to improvement without an absurd time commitment.
Introduction
This section is largely motivation for why I'm proposing this training plan. If you just want to see the instructions for the training plan I'm proposing, you can skip this part. The first subsection in particular is not especially relevant to the rest of the post, but I wanted to have some documentation explaining why I still think the traditional "just solve problems" advice is good.
The Conventional Advice on Improvement
I'm frequently asked for advice on how to improve at competitive programming. Typically, I tell people to focus on solving problems and learning from the ones they can't do, and I think this is the most common advice most strong competitive programmers give to beginners asking for tips. Below, I'll explain why I like to give this advice.
Looking back at my own experience, there were two main points in my career when I was totally stuck and felt like I wasn't improving at all. The first was when I had no background in algorithms at all, and I needed to learn e.g. what big-O notation is, what DP is, what it means to binary search for the answer, etc. Most of the people who ask me for advice know all of these things, so this isn't especially relevant to their situations (but if you don't know these things, read the first eight chapters of the Competitive Programmer's Handbook, and chapter four of Competitive Programming 4 if you have it).
The second was when as a high school junior, I couldn't solve USACO Platinum problems and convinced myself that segment trees, centroid decomposition, and heavy-light decomposition were really important algorithms that I needed to learn to do well on USACO, and thus I decided to spend a bunch of time repeatedly rereading articles about these topics in order to try to understand them better. I generally understood the concept of a segtree, but I wasn't able to implement them from scratch and also didn't have a great sense of how to apply them to problems, meaning that this knowledge was absolutely useless in USACO contests (indeed, that year I failed to solve several easy segtree problems). Meanwhile, centroid decomposition and HLD hardly come up, and even if they had, I didn't really come to understand them well enough to apply them to actual problems. I occasionally spent time thinking about Platinum problems, but they were mostly way too hard for me, so I found it hard to focus on them for extended periods of time or even to understand solutions when I saw them.
That experience is why I think the "just solve problems slightly above your level" advice is actually pretty good--I think I would have stood a fair chance at making USACO Camp as a high schooler if instead of trying to learn advanced topics and solve problems that were way too hard for me, I solved problems from the CF archive that were a bit above my current rating. This also would have fixed my segtree issues because I would eventually have encountered actual segtree problems in the wild that were closer to my skill level, and by solving them or understanding their solutions I would have eventually become strong enough to work on USACO Platinum problems.
Indeed, I improved a lot faster once I started following this advice. After tanking USACO as a junior and failing to make camp, I no longer had a good reason to focus on USACO (it's very hard to make camp for the first time as a senior, and it would have been too late for college admissions anyway, which in retrospect I cared about much more than I should have). I ended up shifting my focus to Codeforces contests; I switched from Java to C++ and started solving problems from the CF archive. Despite not doing any actual USACO practice that year, I did much better on the USACO (plus, I actually started to understand how to use segtrees), solving five problems during the season and getting very close to six, compared to just two the year before.
Motivating a Different Approach
I feel unqualified to give good advice to people who are hardstuck gray/green because I was never stuck in low Elo on Codeforces. This is partly because I had some programming contest experience before I started CF, but I was still a relative beginner when I signed up for CF, so I think the larger factor is that I had five years of math contest experience at the time. Many of the specific topics from math contests transferred well to CF, but more than that, the general thinking process was very similar, and many steps within Codeforces problems (e.g. when proving that your solution is correct) are essentially just math contest problems.
Thus, if I wanted to tell people to follow the same training plan I did, I would have to advise them to spend five years doing math contests first. This is obviously infeasible, so until now I've mostly given up on telling people to do math before trying competitive programming.
However, I've seen a large number of people, especially beginners, who at least appear to be following the conventional advice I outlined above but who don't see the same improvement I did. My theory is that the conventional advice may not work for some people because they haven't developed the background in mathematical thinking necessary to succeed in programming contests. Empirically, many of the top competitive programmers had extensive experience in math contests first, but this may be correlation and not causation. As a result, the goal of this post is to see if focused practice on math problems can help beginners improve at competitive programming more efficiently without the sort of time commitment I put into math contests.
There are (at least) two reasons I think training on math problems might be more efficient than directly training on programming contest tasks. First, programming contest editorials are often not great at motivating the mathematical thinking necessary to come up with solutions, meaning that it may be difficult for beginners who don't have practice thinking about hard math problems to reflect on how they could have solved problems themselves. Second, while most easy programming contest problems involve mathematical thinking, they are usually tagged "math", "combinatorics", "number theory", etc, making it difficult to isolate specific problem-solving strategies or to find patterns across problems. In contrast, the plan I'm proposing uses a tool designed to systematically build up various mathematical problem-solving strategies.
The Plan
In short, this plan calls for systematic practice on math contest problems involving no programming. I'll outline a specific roadmap below.
Instructions
For this training plan, we'll be using Alcumus. Alcumus is a completely free platform provided by Art of Problem Solving that allows you to pick a topic and receive problems from that topic targeted to your skill level. I suspect that practicing problems from e.g. Mathcounts, AMC 10/12, and AIME would give similar results, but the advantage of Alcumus is that we can focus on problems in topics relevant to competitive programming and e.g. ignore all geometry.
Start by registering for an Alcumus account. Go to your settings and set Problem Difficulty to Insanely Hard (you can tune this down later if the problems you receive are much too hard for you, but generally you want to be doing the harder problems on Alcumus) and Advance Only on Mastery to Yes. When you click play, you will be presented with a problem. You'll have two tries to answer it correctly. In the top-right, you can change your focus topic, the topic which most of your problems will be drawn from. Your focus topic will automatically change when you master it (once the progress bar in the top right becomes blue).
Once you're signed up for Alcumus, work through the following steps.
- Algebra: Set your focus topic to "All Topics in Algebra" and solve problems until you're mostly receiving Level 20+ algebra problems. If these problems feel much too easy for you, skip to the next step. Otherwise, master all topics in algebra up to "Advanced Quadratics". The easy topics will not take long to master (you should finish them in ~5 problems each). Algebra is less directly relevant to competitive programming problems, but it's fundamental to the problem-solving process and to the other fields of math we'll work on. If high-level problems in the early sections of algebra feel too difficult, master all topics in prealgebra first. Finish all topics up to "Factoring General Quadratics" before moving to the next steps. The remaining topics ("Sum and Product of Roots" through "Advanced Quadratics") can be done concurrently while working on the next steps.
- Counting and Probability: Master all topics in Counting and Probability. Combinatorics is the field of math that comes up most in competitive programming and is the most relevant to the style of thinking in programming contests, so this is where you should see the most improvement. Master topics through "Distinguishability" before starting the next step; the remaining topics can be done concurrently with the next step.
- Number Theory: Master all topics in Number Theory. These topics come up frequently in programming contests and are also valuable for building general numerical reasoning skills.
You can ignore all topics in Geometry, Intermediate Algebra, and Precalculus.
Finishing these steps should give you a reasonable baseline level of mathematical thinking skills (comparable to where I was when I started competitive programming). If you want to keep solving math problems, you can work on past problems from the AMC 10, AMC 12, and AIME. My advice is to start by working on algebra, combinatorics, and number theory problems numbered 1-5 on the AIME. Once you can solve these consistently, move on to combinatorics and number theory problems numbered 6-10, then work on combinatorics problems numbered 11-15. (It may be that AIME problems feel too difficult, in which case you should start with AMC 10/12 problems.)
You should continue to participate in programming contests and upsolve problems from those contests while working through this plan; it is designed to supplement and not replace programming contest training.
Time Commitment
The time commitment for this plan depends on your prior math background. I think most people should be able to master at least two topics per day in algebra and one per day in C&P/NT, with easier topics going faster. With about thirty topics per section, this should lead to a completion time of at most around two months. I'm not especially confident in this estimate, though, and you might work through it much faster or much slower than I did (which is totally fine). (However, if you e.g. complete the plan in under two weeks, it was probably too easy for you unless you spent many hours on it in that timeframe.)
Target Audience
I think this plan is most likely to help grays, and maybe greens. People above cyan probably already have enough mathematical reasoning skills that the problems on Alcumus will be too easy and thus won't benefit from this plan. I'm also not sure this will be useful if you've already completed a high-quality discrete math course, which would have taught many of the same concepts.
Obviously, this training plan will not teach you any programming. If you want to advance past gray, you should also know big-O notation, the basics of programming in your language of choice, and the STL data structures or their equivalent in your language. As mentioned previously, this plan is not a substitute for programming contest practice.
Additionally, I think this plan will be much more helpful in competitive programming than in job interviews because technical interview/LeetCode problems don't heavily emphasize mathematical problem-solving. I don't recommend this plan if your main goal is to prepare for technical interviews.
Some Thoughts on the Plan
I think this plan has several advantages as a way of practicing math for competitive programming:
- It is completely free. Many of the other math resources I'd recommend (including the AoPS books) are not, and their costs may be prohibitive for some people.
- It is very systematic. There are clear instructions and a specific set of benchmarks you need to achieve to finish the program.
- Alcumus isolates specific math problem-solving skills. For those with limited math background, I think it can be very helpful to e.g. isolate casework, constructive counting, and complementary counting as separate counting strategies rather than just trying combinatorics problems in general.
My main concern about these instructions is that I'm not sure the Alcumus problems are difficult enough to be useful for this purpose. I've tried to compensate for this by suggesting a way of organizing practice on AIME problems, which I'm hoping will be useful for anyone who wants to continue working specifically on math problems.
I also am not confident that training on math problems will ultimately be more efficient for beginners than training directly on programming contest problems. To my knowledge, this theory has not been tested before, hence why I'm writing this blog :)
I've described the plan as "highly experimental" because I have very little sense of whether this plan is actually the best way for beginners to start their training. I think those who complete this plan will almost certainly experience some improvement, but I'm not sure whether this improvement will come faster than if they had instead spent an equivalent amount of time on programming contests. However, I think there's a small but nontrivial chance this plan will lead to significant improvements for a sizable population of beginning competitive programmers who are struggling to train by solving programming contest problems. I'm posting the plan here so that hopefully some people will try it out and we can see if it works for them.
If you try this training plan, please feel free to post updates on your progress below! Let me know if you have thoughts or suggestions, and I'll be eager to see whether you see improvement within a few months of finishing.
