#### Scroll directly to the last sentence if you want to avoid spoilers on some 1800-2100 rated problems↵
↵
**Disclaimer**: the following post is drafted according to my personal experience, I acknowledge that others might have different paths to improvement and it'd be helpful to provide more perspectives in the comments. Also, I don't know if I'm regurgitating some older posts, but I still think it's helpful to provide a more recent update.↵
↵
I reached CM after the 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:↵
↵
[contest:1832]↵
↵
[problem:1832A], [problem:1832C]: none [submission:205576206] [submission:205584244]↵
↵
[problem:1832B]: prefix sums [submission:205579825]↵
↵
[problem:1832D1]: (hacked but right idea) greedy, binary search [submission:205597153]↵
↵
[problem:1832E]: prefix sums, binomial coefficients [submission:205605946]↵
↵
Performance rating: 1927 (would've been ~2200 if I didn't get hacked)↵
↵
------↵
↵
[contest:1840]↵
↵
[problem:1840A], [problem:1840B], [problem:1840E]: none [submission:208720913] [submission:208727427] [submission:208781811]↵
↵
[problem:1840C]: two pointers [submission:208732221]↵
↵
[problem:1840D]: binary search [submission:208742587]↵
↵
[problem:1840G1]: _sqrt decomposition_ [submission:208757942]↵
↵
Performance rating: 2183↵
↵
------↵
↵
[contest:1929]↵
↵
[problem:1929A], [problem:1929B]: none [submission:246536607] [submission:246546010]↵
↵
[problem:1929C]: greedy [submission:246544088]↵
↵
[problem:1929D]: dfs [submission:246557025]↵
↵
[problem:1929F]: binomial coefficients [submission:246537238]↵
↵
Performance rating: 2188↵
↵
------↵
↵
[contest:2002]↵
↵
[problem:2002A], [problem:2002B], [problem:2002C]: none [submission:275805098] [submission:275811322] [submission:275819238]↵
↵
[problem:2002D1]: dfs [submission:275840969] (please excuse me for the horrendous coding style, this was my first time doing any competitive programming in 2 months)↵
↵
[problem:2002E]: stacks [submission:275803661] (I used a deque because I couldn't remember whether I needed a stack or a queue)↵
↵
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 around my 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 shallowly on a 2200 rated problem.↵
↵
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: ↵
↵
<spoiler summary="Their tags">↵
↵
</spoiler>↵
↵
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 used alternative solutions).↵
↵
This is not to say that classical algorithms are useless (after all, they're at least beautiful for their own sake and still show up sometimes); just that **they shouldn't be atop the priority list of div3 and arguably div2 contestants.**↵
↵
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 them. 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 can be the crux to solving problems like [problem:1852A] and [problem:1929D].↵
↵
Of course, it's easy to state that you should do this and harder to put it into practice. I've found that it helps to just write down things. Write down pseudocode when you're trying to modify an algorithm. Write down the inbetween "moving parts" when you're trying to combine two algorithms; for example, while doing [problem:1832D1] using my approach, write down what the problem is reduced to after the greedy observation, and then figure out that you can use binary search. It's usually more complicated in practice but you'll probably get better intuition regarding what to write down as you tackle harder problems.↵
↵
**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 C in time and would've taken several minutes to prove A or B. This advice is covered in more detail in [a YouTube video here](https://www.youtube.com/watch?v=UwHqsX2JIYA). Though, I feel like a secret behind being good at guessing is fast arithmetics and pattern recognition. For example, on [problem:1929C], 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 [problem:2002A], I guessed the solution in a few seconds by factorizing the answers to the samples in my head. It's possible to guess even high-rated problems like [problem:1762E] (as one of my CM friends did in-contest), but that requires some sort of way to develop 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 coefficient identities, such as [problem:1696E], [problem:1832E], [problem:1929F]. I think that [AoPS Alcumus](https://artofproblemsolving.com/alcumus) is a solid resource to practice them. Combinatorial ideas also permeate through even early div3 problems such as [problem:1840B], so it's essential to get familiar with them early on. rather than be afraid of math.↵
↵
**Constructives**↵
↵
Honestly, I feel like I don't have a lot to say besides to come 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 it often has clues as to how to construct a YES**. Look at [problem:1852B]; 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 combinatorics and learn to read samples.
↵
**Disclaimer**: the following post is drafted according to my personal experience, I acknowledge that others might have different paths to improvement and it'd be helpful to provide more perspectives in the comments. Also, I don't know if I'm regurgitating some older posts, but I still think it's helpful to provide a more recent update.↵
↵
I reached CM after the 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:↵
↵
[contest:1832]↵
↵
[problem:1832A], [problem:1832C]: none [submission:205576206] [submission:205584244]↵
↵
[problem:1832B]: prefix sums [submission:205579825]↵
↵
[problem:1832D1]: (hacked but right idea) greedy, binary search [submission:205597153]↵
↵
[problem:1832E]: prefix sums, binomial coefficients [submission:205605946]↵
↵
Performance rating: 1927 (would've been ~2200 if I didn't get hacked)↵
↵
------↵
↵
[contest:1840]↵
↵
[problem:1840A], [problem:1840B], [problem:1840E]: none [submission:208720913] [submission:208727427] [submission:208781811]↵
↵
[problem:1840C]: two pointers [submission:208732221]↵
↵
[problem:1840D]: binary search [submission:208742587]↵
↵
[problem:1840G1]: _sqrt decomposition_ [submission:208757942]↵
↵
Performance rating: 2183↵
↵
------↵
↵
[contest:1929]↵
↵
[problem:1929A], [problem:1929B]: none [submission:246536607] [submission:246546010]↵
↵
[problem:1929C]: greedy [submission:246544088]↵
↵
[problem:1929D]: dfs [submission:246557025]↵
↵
[problem:1929F]: binomial coefficients [submission:246537238]↵
↵
Performance rating: 2188↵
↵
------↵
↵
[contest:2002]↵
↵
[problem:2002A], [problem:2002B], [problem:2002C]: none [submission:275805098] [submission:275811322] [submission:275819238]↵
↵
[problem:2002D1]: dfs [submission:275840969] (please excuse me for the horrendous coding style, this was my first time doing any competitive programming in 2 months)↵
↵
[problem:2002E]: stacks [submission:275803661] (I used a deque because I couldn't remember whether I needed a stack or a queue)↵
↵
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 around my 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 shallowly on a 2200 rated problem.↵
↵
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: ↵
↵
<spoiler summary="Their tags">↵
↵
</spoiler>↵
↵
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 used alternative solutions).↵
↵
This is not to say that classical algorithms are useless (after all, they're at least beautiful for their own sake and still show up sometimes); just that **they shouldn't be atop the priority list of div3 and arguably div2 contestants.**↵
↵
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 them. 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 can be the crux to solving problems like [problem:1852A] and [problem:1929D].↵
↵
Of course, it's easy to state that you should do this and harder to put it into practice. I've found that it helps to just write down things. Write down pseudocode when you're trying to modify an algorithm. Write down the inbetween "moving parts" when you're trying to combine two algorithms; for example, while doing [problem:1832D1] using my approach, write down what the problem is reduced to after the greedy observation, and then figure out that you can use binary search. It's usually more complicated in practice but you'll probably get better intuition regarding what to write down as you tackle harder problems.↵
↵
**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 C in time and would've taken several minutes to prove A or B. This advice is covered in more detail in [a YouTube video here](https://www.youtube.com/watch?v=UwHqsX2JIYA). Though, I feel like a secret behind being good at guessing is fast arithmetics and pattern recognition. For example, on [problem:1929C], 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 [problem:2002A], I guessed the solution in a few seconds by factorizing the answers to the samples in my head. It's possible to guess even high-rated problems like [problem:1762E] (as one of my CM friends did in-contest), but that requires some sort of way to develop 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 coefficient identities, such as [problem:1696E], [problem:1832E], [problem:1929F]. I think that [AoPS Alcumus](https://artofproblemsolving.com/alcumus) is a solid resource to practice them. Combinatorial ideas also permeate through even early div3 problems such as [problem:1840B], so it's essential to get familiar with them early on. rather than be afraid of math.↵
↵
**Constructives**↵
↵
Honestly, I feel like I don't have a lot to say besides to come 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 it often has clues as to how to construct a YES**. Look at [problem:1852B]; 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 combinatorics and learn to read samples.
