GlydonNeedsDedication's blog

Why classical-DP problems differ than CP-DP problems so much ?
By GlydonNeedsDedication, history, 3 years ago, In English

Most of the DP tagged problems that are below 1600 RATING are solvable by Greedy Approach hence not making much progress in my DP practice and DP problems that are rated above 1600 feels a bit tough even to understand sometimes. So what should I do? :( I know and solved many of the classical DP problems but am still unable to implement DP most of the time in CodeForces.

What should I do?

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

Comments Comments (17)
| Write comment?
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Even I have the same question...

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

the tag is usually misleading.maybe ask someone for dp problems recommendation?

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

You should improve the skill of finding states and transitioning between those states. You can develop these skills by solving some DP problems that challenge you. Important thing is that from all the classical-DP techniques you've learned, you should understand why and how they work.

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +28 Vote: I do not like it

I don't know whether people will agree or not but I think clinging to solving random problems in codeforces eventually makes one capable of every important part of cp with time

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

    Yup Yup, that's true, but one also needs to keep a check on the new learned concepts and see if he/she is able to solve the actual problems on cf from the same topic or not!

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

maybe try solving the same problem with dp after solving it with greedy approach

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +95 Vote: I do not like it

I think you're misunderstanding the implication of most problems below 1600 rating tagged dp having greedy solutions. Its not that most easy dp problems also have greedy solutions, but rather if the dp solution was the only solution for those problems they would probably be higher rated.

But coming back to your original question, practically any problem in competitive coding is made up of two parts:

  1. The adhoc part.

  2. The standard part.

The adhoc part is usually what makes the problem interesting, its the observations required to reduce the problem to something you know how to solve, i.e, the standard part. In a good problem $$$\text{difficulty(the adhoc part)} \gt \text{difficulty(the standard part)}$$$, otherwise it just becomes a game of who has memorized more standard ideas.

Most good competitive coding platforms (including Codeforces) tend to follow this rule for the most part and this is true for dp problems as well. Good dp problems will often require you to make adhoc observations to figure out some properties that allow you to apply dp on them.

If you've solved a lot of standard dp problems but aren't able to solve dp problems in CF contests, maybe you're struggling with the adhoc part? If so I'd suggest solving problems from the CF problemset without any topic restrictions. Aim for a difficulty range such that the problems that are tough, but not so tough that you can't understand the editorial either. Current rating + 100-300 is what a lot of people suggest, but remember to increase / decrease difficulty to find what suits you. Also personally I'd suggest avoiding older problems if you're trying to improve adhoc since they contain a lot more standard ideas.

Also on a personal note back when I was on the edge of Expert I remember really struggling with dp problems. And as far as I remember even simple linear dp problems were 16-1700, so unless their difficulty has sharply dropped maybe you're jumping into them a bit too early?

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

    I can't understand editorial for most problems, even one's I was able to solve myself. I usually waste like a day to understand editorial, and sometimes don't succeed. So that doesn't look like a good restriction for a "too hard" problems, as for me.

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

      I faced the same problem. In most cases, I'll find good solutions in the announcement/editorial comment section.

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

I hate this so much about CF tags. Most of these 1600s you are talking about have DP tag because there exists some solution (often very complicated compared to the official solution) that uses DP. Not because DP is in any way a reasonable method to solve this problem. More than once I have searched for easy DP problems for some workshop this way and every time I'm disappointed because the 1600s are not at all DP problems.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +32 Vote: I do not like it

    I'd say they're most likely dp problems. I somewhat often use DP on div2B/C because if you think of it as DP it removes the need to wonder if the "greedy" solution is correct or not because DP trivially proves the correctness usually.

    EDIT: taking a look at those problems, indeed it seems the DP tag is misused more often than I thought lol

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

      I was about to say the same thing and you beat me to it. To my students I always recommend to go for DP instead of greedy whenever applicable because it's trivially correct.

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

        If I can think of both a DP and a greedy approach, I always implement DP approach.

        1. Some seemingly fine greedies are wrong.
        2. Greedy sometimes has edge cases.
        3. DP is easier to implement and prove correctness of.
        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Pratice Atcoder Educational DP contest . Which I am also doing. Problems level are gradually increasing.So perfect for beginner.

→ Reply