AshrafSustS19's blog

What are the dynamic programming concepts I need to know before I start 2400R?
By AshrafSustS19, history, 10 months ago, In English

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.

  • Vote: I like it
  • -24
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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-

        → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

tf is divide and conquer DP?

→ Reply
»
10 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply