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

DP problems that you learnt the most from.
Автор AvadaKedavara, история, 13 дней назад, По-английски

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.

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

»
13 дней назад, # |
← Rev. 5   Проголосовать: нравится +3 Проголосовать: не нравится

I think some of the best that I saw are these

→ Ответить
  • »
    »
    13 дней назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      13 дней назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      → Ответить
      • »
        »
        »
        »
        13 дней назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        → Ответить
»
13 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

use death spell

→ Ответить
»
13 дней назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить