Competitive programming practice sites often organize problems by topic area. For example, uHunt has categories for graphs, string processing, dynamic programming, and many others. uHunt Chapter 5 covers topics in mathematics. Since math is a separate field from computer science and algorithms (though it’s closely related), I’m considering this week how it relates to competitive programming preparation.
Targeted vs. Comprehensive Learning
The Quora question How do I learn algorithms when I don’t understand any of the CLRS algorithm book’s mathematical parts? has two answers that illustrate two extremes of advice about learning math for competitive programming:
- Vishnu Narayanan’s advice: Learn algorithms by implementing them. If you get stuck on the implementation, read the CLRS explanation. But skip the mathematical description of the algorithm if you’re having trouble with that part.
- An anonymous user has the opposite advice: If you’re having trouble with the math in CLRS, put CLRS away and learn discrete math first.
These two philosophies promote two different learning strategies. Let’s call them targeted and comprehensive. A more targeted strategy focuses on a specific result — like improving a competitive programming rating — and looks for the most direct route to that goal. In the CLRS example, the goal is to learn to implement an algorithm and use it in a contest. If understanding the mathematical background in CLRS delays that process, the targeted strategy says it’s not worth spending time on.
Another example of the targeted strategy is using interview preparation sites, rather than programming contests, for coding interview preparation. Although the early levels of competitive programming training resemble coding interview preparation, the targeted strategy would recommend choosing interview preparation sites because they more closely match interviews, even though programming contests might offer other long-term benefits.
The alternative to the targeted strategy is a more comprehensive approach, as illustrated by the anonymous user’s answer to the CLRS question. This approach favors learning the fundamentals of a topic as a way to gain a more complete understanding of it. Because CLRS uses a mathematical approach to algorithms, a user of the comprehensive strategy would look up and learn any math topics required to fully understand the CLRS descriptions.
It’s possible to overdo either one of these strategies. Taking the targeted strategy to an extreme would mean skipping any difficult topics that threatened to slow down the learning process. The result would likely be surface-level understanding that would impede future learning.
An extreme comprehensive strategy could mean getting bogged down in more and more specific topics, without ever being able to apply your new knowledge. As Donald Knuth warns in the “Mathematical Preliminaries” section of The Art of Computer Programming Volume 1: “If too much time is spent studying this material when first reading the book, a person might never get on to the computer programming topics!”
How Much Math Do You Need?
Solving competitive programming problems doesn’t require knowledge of a wide range of math topics, or highly advanced math. Here’s how Brian Bi puts it:
The TopCoder algorithm tutorials cover a lot of the math that is actually needed. It is not advanced stuff—it’s mostly things like modular arithmetic and basic combinatorics that anyone should be able to learn. The challenging part of TopCoder is rarely the math. It’s about dynamic programming, greedy algorithms, graphs, and stuff like that.
Maybe for most competitive programmers, mastering algorithms is more challenging than mastering the math required for coding competitions. But there’s still a baseline math requirement that will trip you up if you don’t have it. And there’s also the argument that solving competitive programming problems requires mathematical thinking skills that aren’t exclusive to any particular math topic, but which you have to develop by studying and practicing math.
Bohdan Pryshchenko doesn’t believe that math should be given special status in competitive programming preparation. In response to a question about how to get better at finding “mathematical insights,” he says those insights aren’t anything exceptional:
What sounds like “mathematical insight” for you, will usually be “yet another slight modification of common trick used to solve such math problems” for a person with proper skill set. I think they learned it in the same way you learned solving problems about “standard algorithms like Dijkstra”.
In other words, you don’t need to study math specifically. You can pick up what math you need as you practice algorithmic problems. As you learn algorithmic tricks, you’ll also learn math tricks. This is another expression of a targeted learning strategy.
I think a more comprehensive learning approach is warranted if you have time for it. Math has broad enough utility that there’s no downside to learning it from the ground up, unless you have a short-term deadline like a job interview.
I’m writing about discrete math and competitive programming this year. For an introduction, see A Project for 2019. To read the whole series, see my Discrete Math category page.
(Image credit: Bill Bradford)