Hello Codeforces Community,

A couple of months back, AtCoder had organized an Educational DP Contest. As can be seen from the blog, the contest had received some amazing feedback and there was a huge demand for more such similar contests. Unfortunately, I don't think AtCoder admins have had enough time to organize more such contests.

I wanted to, with the help of this community, create a collection of about 25 — 30 advanced DP problems, which would have a structure similar to the problems of AtCoder's Educational DP Contest (classical problems; simple, straight-forward statements) but more harder. Or problems that could potentially cover a dynamic programming technique that was not covered by AtCoder's contest (Knuth's Optimization, or Alien's binary search technique, for example).

Please post problems (statements, links, anything) that you think would make a good addition to this list. If possible, please post each problem as a separate comment so we can get an idea of how much liking there is for each problem, from the community.

As more and more problems are posted and upvoted, I'll add them to the blog roughly organized in the order of difficulty. I'll add these problems to two different sections as probably not all of them would be considered educational/advanced as per the definition above.

If this blog receives a good number of upvotes, I'll make more such blogs for different topics (Search, Graphs, Greedy, etc).

Thanks!