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$$$

# | User | Rating |
---|---|---|

1 | tourist | 3751 |

2 | Benq | 3727 |

3 | cnnfls_csy | 3691 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | orzdevinwang | 3559 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 163 |

5 | maroonrk | 162 |

6 | SecondThread | 160 |

7 | nor | 158 |

8 | -is-this-fft- | 154 |

9 | kostka | 146 |

10 | TheScrasse | 144 |

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$$$

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/30/2023 12:42:21 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Auto comment: topic has been updated by hieua3xyz (previous revision, new revision, compare).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.

So do you think what the solution is?

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.

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)$$$.

Thank you very much <3

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

Thank you very much <3