Last weekend I finally hit CM, and today I reached a rating of over 2000, so in celebration, here's a list of some things I've heard of but don't know. I'm relatively new to CP—I started in August 2024—so there are a lot of techniques that most people probably consider standard that I'm not familiar with; feel free to comment below with more suggestions. (This definitely is not a copycat of a certain other famous blog, I swear this is a completely original idea.)
- Lazy propagation in segment trees
- Fenwick trees
- Sparse table
- Sqrt decomposition
- Mo's algorithm, which cost me an ICPC solve
- Small-to-large merging
- Binary search trees, including treaps
- Heavy-light decomposition
- Binary lifting
- I've never implemented most graph algorithms, including Kruskal's/Prim's, Bellman-Ford, Floyd-Warshall, etc
- I don't think I've ever implemented BFS before, although I know the general idea
- Actually I don't think I've ever implemented any $$$O(n\log{n})$$$ sorting algorithm before; I just use
std::sort() - Flows (I don't even have the slightest idea of what this is)
- Ternary search
- Chinese Remainder Theorem (I have a vague sense of what it is, though)
- Convex hull
- Fast fourier transform
- Pretty much any geometry
- Any string algorithms (although I'm familiar with the general idea of some of them)
- Anything about hashing
- How to compute binomial coefficients of large numbers quickly (is this possible?)
- Every single thing in this list
Just as a bonus, I don't think I've ever AC'd a problem during contest using either DSU or segment trees. As a second bonus, I also do not know how to install C++, use the command prompt, use Github, or write legible code.
Knowing techniques can be useful, but in general I think it's possible to hit CM (perhaps even Master) with only knowledge of basic programming (I/O, control statements, etc), what's provided in C++ standard library (vectors/arrays, sets/multisets, sort(), etc), DP, and some basic combinatorics.
