hieua3xyz's blog

This problem cannot be dp ?
By hieua3xyz, history, 16 months ago, In English

Given $$$n$$$ elements $$$a_i$$$

Each operation can increase or decrease an element by one unit.

Ask for the minimum number of operations so that two consecutive elements have a difference less than $$$k$$$.

Let $$$n \le 100; \;a_i, k \le 10^9$$$

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

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hieua3xyz (previous revision, new revision, compare).

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

No this can't be called as dp as any state is not depending on some previous state, any particular state (2 consecutive elements) are independent of other states.

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

    So do you think what the solution is?

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

      Hey sorry, i thought any one pair should have difference less than k. It's a dp qestion Okk so dp will go something like this

      minimum number of moves needed to make the difference of ith pair less than k will be minimum of the moves needed to make the difference of i-1'th pair less than k when i-1 th element was decremented or incremented.

      → Reply
»
16 months ago, # |
  Vote: I like it +12 Vote: I do not like it

The first dp solution you will think of is $$$dp[n][$$$max value you in $$$a]$$$, which are the current index and the value of the previous element.

Obviously this dp solution is not good enough but you can use this observation.

Imagine that final array of the optimal solution that you will get after doing all of your operations is array $$$b$$$, for some index $$$i$$$ we know that $$$b_i$$$ should be in the intersection of $$$[b_{i-1} - k , b_{i-1} + k]$$$ and $$$[b_{i+1} - k , b_{i+1} + k]$$$.

So if $$$a_i$$$ is already in the intersection the best thing is to make $$$b_i$$$ equal to $$$a_i$$$, otherwise since it is outside the range the best thing is to make $$$b_i$$$ equal to one of the boundaries of the intersection, which is one of $$$[b_{i-1} - k , b_{i-1} + k , b_{i+1} - k , b_{i+1} + k]$$$.

Now for two adjacent elements in array $$$b$$$ lets say that they are connected if the absolute difference between them is exactly $$$k$$$.

This way we can split array $$$b$$$ into some connected subarrays, for every subarray you can increase or decrease all its elements by one and still array $$$b$$$ is correct.

for a connected sub-array $$$[l,r]$$$ let $$$x$$$ be equal to number of elements $$$(a_i = b_i)$$$, $$$y$$$ equal to number of elements $$$(a_i < b_i)$$$ and $$$z$$$ equal to number of elements $$$(a_i > b_i)$$$ where $$$(l \leq i \leq r)$$$.

If $$$x$$$ equals to $$$0$$$, if I increase all elements by $$$1$$$ I will add to the answer $$$(z-y)$$$, and if decrease all elements by $$$1$$$ I will add to the answer $$$(y-z)$$$, so if $$$y$$$ is not equal to $$$z$$$ array $$$b$$$ can't be the best solution.

so If $$$x$$$ equals to $$$0$$$, I can keep increasing or decreasing $$$1$$$ to the subarray until it has an element where $$$(a_i = b_i)$$$, or it connects with another subarray.

That means that in the final answer you will leave $$$a_i$$$ unchanged, or you will change it to $$$a_j + x \cdot k$$$ where $$$(-n < x < n)$$$ for some other $$$j$$$.

So for every index $$$i$$$ we have $$$n^{2}$$$ options, so the dp will become $$$dp[n][n^{2}]$$$, and there is a way to find the answer of every state in $$$O(1)$$$.

→ Reply
»
16 months ago, # |
  Vote: I like it +11 Vote: I do not like it

This is doable in O(NlogN) with slope trick, it is a classic task. Just google "slope trick codeforces".

→ Reply