Блог пользователя AshrafSustS19

Автор AshrafSustS19, история, 17 месяцев назад, По-английски

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.

  • Проголосовать: нравится
  • -24
  • Проголосовать: не нравится

»
17 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        17 месяцев назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        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-

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

tf is divide and conquer DP?

»
17 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Not 2400 but I feel like standard DP optimization tricks are no longer required in cf contest anymore.

»
17 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.