Disclaimer: the following post is drafted according to my personal experience, I acknowledge that others might have a different path to improvement and it'd be helpful to provide more perspectives in the comments. Also, I might be regurgitating some older posts, but I still think it's helpful to update.
I reached CM after the most recent div1+2 round, here's a list of all the algorithms I've used on my past 4 official contests where I've gained the most rating:
Educational Codeforces Round 148 (Rated for Div. 2)
1832A - New Palindrome, 1832C - Contrast Value: none 205576206 205584244
1832B - Maximum Sum: prefix sums 205579825
1832D1 - Red-Blue Operations (Easy Version): (hacked but right idea) greedy, binary search 205597153
1832E - Combinatorics Problem: prefix sums, binomial coefficients 205605946
performance rating: 1927 (~2200 if i hadn't been hacked)
1840A - Cipher Shifer, 1840B - Binary Cafe, 1840E - Character Blocking: none 208720913 208727427 208781811
1840C - Ski Resort: two pointers 208732221
1840D - Wooden Toy Festival: binary search 208742587
1840G1 - In Search of Truth (Easy Version): sqrt decomposition 208757942
performance rating: 2183
1929A - Sasha and the Beautiful Array, 1929B - Sasha and the Drawing: none 246536607 246546010
1929C - Sasha and the Casino: greedy 246544088
1929D - Sasha and a Walk in the City: dfs 246557025
1929F - Sasha and the Wedding Binary Search Tree: binomial coefficients 246537238
performance rating: 2188
EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2) (please excuse me for the horrendous coding style, this was my first time doing any competitive programming in 2 months)
2002A - Distanced Coloring, 2002B - Removals Game, 2002C - Black Circles: none 275805098 275811322 275819238
2002D1 - DFS Checker (Easy Version): dfs 275840969
2002E - Cosmic Rays: stacks (i used a deque because i couldn't remember whether i needed a stack or a queue) 275803661
performance rating: 2203
So, based on these contests, it seems like that string algorithms, segment trees and "classical" graph algorithms such as BFS, DSU, Dijkstra, etc. are getting phased out at the level, and it's very possible to reach CM or even master without knowing them. Furthermore, only 1 problem out of 21 used any "advanced" algorithm in general, and it was applied in a shallow way.
One might argue that the set of contests I've taken part in is a small sample, so let's check out the 10 most recent 2100 rated problems:
As we can see — 1 data structure problem (which did not require segment trees), 1 shortest paths problem, and a staggering 4 dfs's, 4 constructives, 4 greedy's. While I didn't encounter any DP problems, it's proven here to be relevant with 3 problems (also, some problems I've solved have the DP tag while I personally had an alternative sol).
Then, what to prioritize in today's meta? Here are a few insights I've personally realized:
- Understand simple things deeply
Binary search, greedy, dfs, two pointers, prefix sums... Everyone should be familiar with these terms. Oftentimes a slight modification of the basic algorithms would already become a ~1900 rated problem. For example, ideas like binary searching for the answer and using DFS to relay information from the subtrees to the ancestor are the crux to solving problems like 1852A - Ntarsis' Set and [submission:1929D].
- Get good at guessing
I guessed the answers to problems A,B,C on my last contest. I don't think I could have proved either B or C in time. This advice is covered in more detail at Your text to link here..., Though, I feel like a secret behind being good at guessing is fast arithmetics and pattern recognition. For example, on 1929C - Sasha and the Casino, I guessed when the answer was -1 quickly by just observing that $$$\frac{1}{2}+\frac{1}{3}+\frac{1}{6}=1$$$ but $$$\frac{1}{2}+\frac{1}{3}+\frac{1}{7}<1$$$, and on 2002A - Distanced Coloring, I guessed the solution in a few seconds by factorizing the sample answers in my head. It's possible to guess even high-rated problems like 1762E - Tree Sum (which one of my CM friends did in-contest), but that requires some sort of intuition about the problem that's hard to cover in text.
- Learn some combinatorics
A lot of 2000+ combinatorics problems require nothing but basic binomial coefficent identities, such as 1696E - Placing Jinas, 1832E - Combinatorics Problem, 1929F - Sasha and the Wedding Binary Search Tree. I think that AoPS Alcumus is a solid resource to practice them. Combinatorial ideas also permeate through even early div3 problems such as 1840B - Binary Cafe, so it's essential to get familiar with them early on.
- Constructives
Honestly, I feel like I don't have a lot to say besides coming up with small cases, which is a common advice. Though, a useful remark that I don't see often is that if the answer is ever NO (which should happen in the samples if there's not always a construction), do everything to find out why, because that probably has clues to how to construct a YES. Look at 1852B - Imbalanced Arrays; by just looking at the second test case in the sample, you'd wonder why of all 5 test cases, it's the only one that doesn't work. Trying to come up with properties unique to it in the samples would readily lead to the observation that the two 4's made it bad, and that the frequency of $$$n$$$ in $$$a_i$$$ is important, which should readily lead to the first step in the official solution.
TL;DR learn binary search, but also learn math and learn to read samples.
