AvadaKedavara's blog

DP problems that you learnt the most from.
By AvadaKedavara, history, 13 days ago, In English

I am learning DP I have solved almost all of the problems in CSES DP section. I want to solve CF problems because they are trickier. So I want you guys to help me with this by commenting the best problems which are above 1500 difficulty on DP.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
13 days ago, # |
← Rev. 5   Vote: I like it +3 Vote: I do not like it

I think some of the best that I saw are these

→ Reply
  • »
    »
    13 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I was looking forward to solve them. Then I found out I have already solved them all. If you need help with "Planar Reflection" let me know.

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

      Wooow great, yes, I really suffer there as it is also ununderstandable :(

      If you can help with anything to let me understand it more that would be great as I have read many things about it, but in vain (also is this a specific type of DP that I don't know or what coz even after looking at its code it looks strange)

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

        What you need to understand is when a particle is hit on a plane it changes it's direction as well as it decays by 1. let's assume there are three 4 planes. if a particle of level 3 is going right and hits on the second plane, it decays by 1 and becomes level 2 and starts going left. If you think about it closely, it is the same as a particle who is going to right and "will" hit the fourth plane. But in reverse. In this way you can formulate the DP.

        → Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

use death spell

→ Reply
»
13 days ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

this is going to sound weird but you need to just say it, just say to your self, lets say i knew the answer for all _______, could i then know the answer to the problem, can i transition in a reasonable time? usually its pretty obvious what types of things you might want to know, then its just a matter of picking one that has good complexity and transitions. You need to do some more problems(as do we all) but lowkey at your current level, the hardest part should be realizing it is dp, rather than actually finding the right dp or the right transitions, so just add it to your problem solving system i.e don't forget to stop and say "if someone told me this was dp, how would I solve it?"

Here are two nice problems:

https://mirror.codeforces.com/contest/2031/problem/D — this one makes dp feel almost like magic, just trust the logic

https://mirror.codeforces.com/contest/2037/problem/G — need a tad of combinatorics knowledge

→ Reply