cote's blog

How to solve this dp problem?
By cote, history, 4 years ago, In English

I am struggling with this problem: https://dunjudge.me/analysis/problems/896/

It is suggested on cp-algorithms.com that convex hull trick can solve this problem. I read this problem a month ago and now come back to it I still cannot solve it.

Can anyone help me with this, Thanks in advance.

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

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

You need a couple of observations:

First, if there are some cats $$$i, j$$$ such that $$$a_i \le a_j$$$ and $$$b_i \le b_j$$$ then it's optimal to put the cat $$$i$$$ on the same group as cat $$$j$$$. We can ignore the cat $$$i$$$. Therefore we can sort all cats by $$$(a_i, b_i)$$$ and erase all these "useless" cats, getting at the end an array where the cats are sorted strictly increasing by $$$a_i$$$ and strictly decreasing by $$$b_i$$$.

Other observation: now with this new array, it's optimal to group consecutive cats.

Therefore now you can use the following DP:

$$$dp[i]$$$: min cost of partitioning the prefix until position $$$i$$$. The transitions are:

$$$dp[i] = \min_{j < i}\{dp[j] + a[i]\cdot b[j+1]\}$$$

Now you can apply easily Convex Hull Trick here. You can get linear complexity, because the slopes are sorted and the points of the queries to your DS are sorted too.

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

    Gee, I came up with part of the first observation but didn't think of erasing all the useless cats. Thanks for your explanation.

    → Reply