Hello everyone, recently I have decided that I am going to start solving 2400R problems. Now, I am a bit hesitant to start, because last time I saw, there seem to be many advanced DP concepts I haven't yet learnt about, like divide and conquer DP, Component DP and some other stuff. Since I don't look into editorials before solving problems, it's a big problem for me if I have to constantly worry about missing topics. So, what are the all advanced dynamic programming topics I need to learn before starting 2400, also any other advanced ds and algo I should look into. For 2400R specifically, higher difficulty topics are not important right now.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3821 |
| 3 | Benq | 3736 |
| 4 | Radewoosh | 3631 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3388 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 10.11.2024 09:39:27 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
can you please tell me to reach Expert, what Data structure and algorithms i should know ? and what rating problem i should solve?
thanks in advance
Well, I can tell you about algorithms I knew when I became Expert. Euler phi, sieve variants, trie tree, disjoint set union, binary exponentiation, modulo inverse/ Fermet's little theorem, topological sorting, dijkstra, floyd warshal, bellman ford, hashing, DP (coin dp, knapsack, LCS etc), segment trees, BITs etc. I don't even remember using half of these ever in any contest, but these are more than enough. I learnt like CRT, Edmond carp which have no use in expert. Also I learnt some stuff for fun like Sqrt decomposition, Mo's algorithm, Heavy light decomposition, Centroid decomposition they also have almost no uses below 2000 rating problems. I also learnt KMP, LCA, binary lifting. Problems related to these topics are fairly common in 1900-2000s. KMP is found in 1700-1800s sometimes. These are not necessary. I learnt them because I enjoyed learning, also because by the time I was Expert I was already solving 2000R problems and I don't like worrying about missing out topics.
Ok, thanks alot. Do you have any practice log sheet or somewhere you collected the solved problems ? And Are you solving just on CF or there are any platfors that helped you?
Nah, just on CF. There is no need for a sheet. Just go to problemset, set a range and start solving problems one by one. Like this: codeforces.com/problemset?order=BY_RATING_ASC&tags=1600-
tf is divide and conquer DP?
Yeah, I don't know either https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html
Not 2400 but I feel like standard DP optimization tricks are no longer required in cf contest anymore.
Maybe, but I may need to deal with them when practicing.
DP + Segment Tree, Divide and Conquer DP, Knuth Optimization, Convex Hull Trick. Uhh, I think these are sufficient. These thing shouldn't take too long to learn.
Thanks man