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.
orz reirugan congrats on CM
so, you know how to get a generating function?
lmao this is not a comprehensive list of things I do not know, although we did have a substantial unit on generating functions in my combinatorics class two semesters ago
how about getting a GF?
seems harder than hitting CM
harder than hitting GM
harder than hitting Specialist ngl
afaik it is possible to compute binomial coefficients, from what i know the most efficient way is is to precalculate the factorials and use modular inverses which works in O(n) for the precomputation and O(log n) for each query. i might be wrong though
If you also precompute inverse factorial in O(n), then you can do O(1) per query.
To compute inverse factorials fast, compute inverse of MAX! and then multiply one by one to get lower factorials.
huh interesting. thanks for the correction man
Also to further the point of this blog, I didn't learn this technique until the literal day after I hit IGM.
In the contest I hit IGM I initially TLE-d using the $$$O(\log)$$$ technique in python, so I had to switch to C++. The next day pajenegod messaged me to tell me how to do it in $$$O(1)$$$.
how did you reach CM from August 2024? What type of experience did you have?
i like olympiad math, probably helps
like olympiad maths- also don't know Chinese remainder theorem. crt is quite easy just a glance over it will suffice ig. as for geometry if you want to work upon that there is an excellent course on couresera by some russian uni called computational geometry, solving geometry problems from aurthur engle would help in. apart from that there is a lot more in this list i still have to learn. so thanks for that hope you have a nice time learning geometry.
ps. forgive my spelling errors i am severely dyslexic
brother you have 4 skipped contests
I didn't say I was good at oly math lol, just that I like it :)
I didn't take competition math seriously at all in high school, so I didn't make it very far in the US track. In university I started looking over oly problems casually for fun, and I also take the Putnam every year (which is the North American undergraduate math olympiad). I've done alright (I placed top 700) but nothing special. I'm pretty weak at N and G (luckily Putnam doesn't have G though); I'm decent at C and A.
That being said, I still think it's fun. One does not have to be good at things to enjoy them.
top 700 in putnam is amazing, i hope i am good enough for simon marais next year, i meant no disrespect by my comment nor was it a judgement, it was poised more as a joke, and making my recommendations of some resources i have come across. I am sorry if i offended you in any manner.
not offended, don't worry :)
P.S. Lilypad said the same thing to me. After he read this blog, he DM'd me "bro there is actually no way you don't know what crt is". Honestly fair, most oly mathers probably do know CRT lmao, perhaps that's the most surprising thing on this list.
I think some math theorems are derivable, though. I derived Legendre's while solving a problem without knowing it was a known formula (to be fair, it's pretty easy if you know how factorials and prime factorizations work), and I also used p-adic valuation on the Putnam without knowing it was a real thing. Some things are fairly straightforward.
I find it fascinating how you’re unfamiliar with many concepts that are considered fundamental in competitive programming from an Olympiad perspective: like Fenwick trees, sparse tables, sqrt decomposition, Mo’s algorithm, small-to-large, binary search trees, heavy-light decomposition, binary lifting, and ternary search.
This is a testament to how much math can help you on Codeforces. Congratulations on reaching CM!
thanks! and also true, i didn't start CP until my third year of university, so i never did OI or anything of the sort. math is helpful though!
As a new master I will say I agree with 96% of what you said.
Interestingly, at least in my memory, the majority of the other 4% comes from contests that are unrated for experts+(some div3 G problems)(Excluding 2500+ problems)
There is a big difference between "don't learn unnecessary things" and "not learning things you should know". If you said the above list when you are orange, then I think it is very much in the second class. For CM, I think it is midway between.
Besides start costing actual solves (where the technique is the only solution), you must also appreciapte how standard DS or techniques can allow you to skip observations, or allow you to look at some "apparently smart things" and they become useless. Efficient use of standard DS to simplify coding can make life so much easier.
I just don't want this blog to have a sentiment of "proud to be lazy", that's all.
Though in some sense, I hitted CM after doing aboslutely nothing — at that point I would know many of things you said but will never be able to implement it. But surely, you could reach CM without any of these, but you probably won't want to stop at CM right
This is true. That being said, I think at least in Div2 CF rounds specifically, technique is perhaps slightly less prioritized than in other contests (and since I don't really do any CP other than Div2 CF, technique perhaps isn't my main priority). As far as I can remember, I can't think of a specific instance where I feel like anything on the above list cost me a CF solve — usually if I see something I'm not familiar with in the editorial of a problem I struggled with during a contest, I'll learn the technique on the spot, but this is quite rare. Now that I can compete in Div1, perhaps this will be different going forward. In any case, thanks for your advice!
For CNOIers, this is unimaginable.
Yes, although I roughly knew what to expect before clicking, I was still shocked by what I saw.
But upon reflection, I realized that I haven't actually used those algorithms and data structures I'm familiar with on Codeforces (except for using a segment tree once), even though they are quite useful in the CNOI series of competitions.
As a person who has participated in this platform in 4 years, that is most of the time correct. Usually, it's us overthinking the pattern to problems rated CM below...
congrats for 2000+
I felt that
The emphasis on so-called algorithms has led many learners down a detour. I don't think those algorithms aren't important.
I think if somebody always practice on Codeforces and can't keep on purple(just like me), learning too many algorithms can be misleading because they can't master using these algorithms.
I found a very strange phenomenon that some of the kids who are learning programming are now learning digital dynamic programming, but many of them can't even write the correct 01 backpack and full backpack code.
I believe that the learning of programming is a process of long-term understanding and experience, rather than the accumulation of these algorithms.
Although I stayed at blue for a long time, however, when I checked the solution after the competition, I always found that the reason why I did not do the next question was not that I did not know the knowledge point, but that I did not master it.
You can do it under a prime modulo with mod inverse and precomping factorials
Also surprised at some of the stuff on this list if you're doing ICPC. I feel like there's frequently problems in the style of "easy solve if you know x algorithm" at NA regionals. Like there was one problem on SER this year that was gatekept by tree diameter knowledge and another that was gatekept by string algorithm knowledge. I can understand not learning a lot of these things if you're just doing div2 cf rounds but for ICPC it's definitely worth learning a lot of this stuff just so you can solve it if a problem using it shows up.
Yep, dnialh mentioned the binomial coefficients one :)
And yes, you're probably right. I've only done ICPC once (GNYR in 2024) and we didn't do particularly well (we did alright, but not near contention for NAC) even though our team was fairly decent by CF level. Maybe we should learn more algorithms if we want to have a shot at NAC lol. We'll see, though. If my teammates tell me that they really care about pushing for NAC later this year, then I'll definitely study so as to not hold them back, of course. Right now, I'd say I value CF more, though.
As an expert, I am on the same page. I know sparse tables, tho and know the basic idea behind lazy segment trees.
And the only problem I have got AC (during contest) using a segtree or dsu was this whose intended solution is priority queue.
And I have one AC in atcoder where I used segtree and intended was fenwick or lazy segment tree
the first problem which I used a segtree was also a problem that pqueues were intended.
Weirdly enough I solve a segtree problem with pqueues once :/
CM too and I will go down ur list.
The class I keep mentioning: Georgia Tech's CS 1332
Over all yeah I agree with this, but you do need to learn some more DSA to improve. On the bright side, you are more than good enough for >99% of technical interviews already so this is a CP rather that general idea.
I think you intended 1999G2 - Ruler (hard version) for ternary search.
yeah I did
I think you mean $$$KMP$$$
I know most of things you say,but i am still CM lol
Also, to compute every coefficient of the form $$$\binom{m}{i}$$$ where $$$m$$$ is a fixed large number and $$$1\le i\le n$$$ where $$$n=5\cdot 10^5$$$ or something, you can just use $$$\binom{m}{i}\cdot \frac{m-i}{i+1}=\binom{m}{i+1}$$$. You can make it faster by precomputing inverses from $$$2$$$ to $$$n+1$$$ in $$$O(n)$$$, see https://cp-algorithms.com/algebra/module-inverse.html#finding-the-modular-inverse-for-array-of-numbers-modulo-m
Problem where I used this in-contest: https://mirror.codeforces.com/contest/1929/problem/F
Now that you're a master, have you crossed out any item of the list? :-)
Several of them, I learned during contests because I knew the general idea of what it did, so I recognized it'd apply and read an article when I needed it lmao.
I think that's it.
I almost know 12 of the things mentioned, and I'm still a specialist. Especially these days, I feel like I'm suffering from brain rot, but I'm sure the breaking point is on its way. I'm also hoping to be a candidate master by the end of the year.