1

Why classical-DP problems differ than CP-DP problems so much ?

 1 year ago
source link: http://codeforces.com/blog/entry/97679
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By Glydon, history, 7 months 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?

7 months ago, # |

Even I have the same question...

7 months ago, # |

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

7 months ago, # |

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.

7 months ago, # |

← Rev. 4 →  

+28

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

  • 7 months ago, # ^ |

    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!

7 months ago, # |

Even I faced the same problem. The thing is that if you solve problems by tag, probably you wouldn't be able to solve a problem given at a contest, cause there won't be any tag at that time.

So just remove those tags from setting and then start solving. In my case it really helped.

  • 7 months ago, # ^ |

    me too

7 months ago, # |

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

  • 7 months ago, # ^ |

    that's a boring idea at least for me

7 months ago, # |

← Rev. 3 →  

+95

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 difficulty(the adhoc part)>difficulty(the standard part)difficulty(the adhoc part)>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?

  • 7 months ago, # ^ |

    Valuable information! Thank you :). I have got an idea where I was wrong :).

  • 7 months ago, # ^ |

    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.

    • 7 months ago, # ^ |

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

7 months ago, # |

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.

  • 7 months ago, # ^ |

    ← Rev. 2 →  

    +32

    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

    • 7 months ago, # ^ |

      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.

      • 7 months ago, # ^ |

        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.

7 months ago, # |

← Rev. 2 →  

+3

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

  • 7 months ago, # ^ |

    I second this recommendation. Here's a link: https://atcoder.jp/contests/dp/tasks

    CSES also has a Dynamic Programming section with some basic problems, and some more advanced DP problems later: https://cses.fi/problemset/list

    • 7 months ago, # ^ |

      can you clarify why you recommend cses dp section over atcoder educational dp contest problems?

      • 7 months ago, # ^ |

        I don't. Both are good. Solve both.

4 hours ago, # |

Leetcode has standard dp problems. Maybe try there and comeback to codeforces.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK