Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Every algorithm I've used to reach CM in 2024, and some observations on getting better

Правка en8, от mitsukiyo, 2024-08-14 07:47:40

Scroll directly to the last sentence to avoid spoilers

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 might be regurgitating some older posts, but I still think it's helpful to provide a more recent 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 - Новый палиндром, 1832C - Контрастность: none 205576206 205584244

1832B - Максимальная сумма: prefix sums 205579825

1832D1 - Красно-синие операции (простая версия): (hacked but right idea) greedy, binary search 205597153

1832E - Задачка на комбинаторику: prefix sums, binomial coefficients 205605946

Performance rating: 1927 (~2200 if I hadn't been hacked)


Codeforces Round 878 (Div. 3)

1840A - Шифр шифер, 1840B - Бинарная кофейня, 1840E - Блокировка символов: none 208720913 208727427 208781811

1840C - Горнолыжный курорт: two pointers 208732221

1840D - Фестиваль деревянных игрушек: binary search 208742587

1840G1 - В поисках истины (простая версия): sqrt decomposition 208757942

Performance rating: 2183


Codeforces Round 926 (Div. 2)

1929A - Саша и красивый массив, 1929B - Саша и рисование: none 246536607 246546010

1929C - Саша и казино: greedy 246544088

1929D - Саша и прогулка по городу: dfs 246557025

1929F - Саша и свадебное бинарное дерево поиска: 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 - Дистанционная раскраска, 2002B - Игра с удалением, 2002C - Чёрные круги: none 275805098 275811322 275819238

2002D1 - Проверка DFS (лёгкая версия): dfs 275840969

2002E - Космические лучи: 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 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:

Their tags

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 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 can be the crux to solving problems like 1852A - Набор Ntarsis and 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 - Саша и казино, 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 - Дистанционная раскраска, 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 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 1696E - Размещение кукол, 1832E - Задачка на комбинаторику, 1929F - Саша и свадебное бинарное дерево поиска. I think that AoPS Alcumus is a solid resource to practice them. Combinatorial ideas also permeate through even early div3 problems such as 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 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 math and learn to read samples.

Теги improvement

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский mitsukiyo 2024-08-14 20:02:12 195
en17 Английский mitsukiyo 2024-08-14 19:59:12 43
en16 Английский mitsukiyo 2024-08-14 13:22:52 624
en15 Английский mitsukiyo 2024-08-14 13:16:35 100 Tiny change: 'ased out at the ~CM,2024-08-14 level, an' -> 'ased out around my level, an'
en14 Английский mitsukiyo 2024-08-14 09:12:09 45
en13 Английский mitsukiyo 2024-08-14 09:11:38 263
en12 Английский mitsukiyo 2024-08-14 09:10:29 29
en11 Английский mitsukiyo 2024-08-14 09:09:37 15
en10 Английский mitsukiyo 2024-08-14 09:00:12 24
en9 Английский mitsukiyo 2024-08-14 07:54:14 55
en8 Английский mitsukiyo 2024-08-14 07:47:40 28
en7 Английский mitsukiyo 2024-08-14 07:46:54 56 Tiny change: '**Disclaim' -> '#### Scroll directly to the bottom to avoid spoilers\n\n**Disclaim'
en6 Английский mitsukiyo 2024-08-14 07:34:06 87
en5 Английский mitsukiyo 2024-08-14 07:29:24 50
en4 Английский mitsukiyo 2024-08-14 07:28:24 344 (published)
en3 Английский mitsukiyo 2024-08-14 07:15:21 30
en2 Английский mitsukiyo 2024-08-14 07:14:22 6261
en1 Английский mitsukiyo 2024-08-11 22:05:00 593 Initial revision (saved to drafts)