Can anyone solve this?
You are given array a1...n. We want to make a zero-array(array consisting only of zeroes) from it. You have 3 buttons:
1-button) Take an element ai, replace it with integer x such that |x−ai|≤1. The cost of using this button is 1 gold. 2-button) Take a range [l…r], increase all elements in this range by 1. The cost of using this button is X gold. 3-button) Take a range [l…r], decrease all elements in this range by 1. The cost of using this button is X gold. Find the minimum total gold to achieve zero-array. Input The first line contains two numbers n and X (1≤X≤n≤1000000).
The second line contains n numbers a1,a2,…,an(1≤ai≤1000000000) — array a.
Output Print a single integer — the minimum amount of gold to reach the zero-array.
I can solve it when $$$X=1$$$:)) First operation is redundant and you look at differences between adjacent numbers. At one operation you pick a pair and increase one number by one and decrease the other by 1. The sum of positive differences is then an achievable lower bound (equal to the negation of the sum of negative differences).
I would then try to count on operations being commutative: we know how to solve it when we have just 2nd and 3rd operation, so we can assume we perform all the operations of 1st kind in the beginning and then compute $$$f(a) = X \cdot \left(\sum\limits_{i=0, a_{i+1}>=a_i}^n{a_{i+1}-a_i}\right) = \frac{X}{2} \cdot \left(\sum\limits_{i=0}^n{|a_{i+1}-a_i|}\right)$$$, where you set $$$a_0=0$$$. So the question is now to minimize $$$f(b)+\sum\limits_{i=1}^n{|a_i-b_i|}$$$. If you look at the differences $$$\delta_i=a_{i+1}-a_i$$$ alone, then you can pay 1 to decrease one and increase and adjacent one, to then end up paying $$$X/2\geq 1$$$ for every $$$|\delta_i|$$$. One observation is that in an optimal $$$b$$$, when $$$X$$$>2, it never makes sense to leave 2 adjacent deltas that are of opposite signs. That is, either all deltas are negative, or all are positive. So you need to first sort the array to non-decreasing or non-increasing and then apply this. If $$$X$$$ was infinity, this would still be difficult for the given constraints, you can check this problem. Basically you can try to simulate $$$dp_{i, X}$$$ what's the cost so far if I've fixed the values of $$$b_1, .., b_i$$$ s.t. $$$b_i=X$$$. I am pretty sure the solution for that problem generalizes to this: you need slope trick to keep the dp (as in points where the slope changes via a set). As the problem is strictly harder than that one, I doubt you can do it differently, without solving that one differently as well.
BTW, what contest is this? The problem seems pretty qualitative
"That is, either all deltas are negative, or all are positive." I don't think this is right, there may be some zeroes. For example: 1 0 0 0 0 0 -1 This problem is from IZhO 2021 in Computer Science (Trainers League). I have also posted another interesting problem: [](http://mirror.codeforces.com/blog/entry/87717)
Yep you're right, I got sloppy. I still think keeping a dp where you fix the type 1 moves that you make on the go and add the absolute value of the newly formed adjacent differences, that slope trick would work, but I don't have the power to check it myself. I'm just slightly less sure because there is no longer a direct reduction to that problem, so maybe something easier can be done. Also, I was assuming in here that X is an integer (so either equal to 1, or >= 2 which may be useful), is that the case?
X and all a(i) are integers
You can register on contest here: https://impact21.contest.codeforces.com/enter
.....
Consider $$$Y = X/2$$$.
My take on this problem would be to analyze $$$dp(i, j)$$$ minimum cost for $$$[1..i]$$$ such that there are $$$j$$$ open intervals ($$$j$$$ can also be negative). Let's dynamically keep $$$dp(i, j) = f(j)$$$. Initially $$$f(j) = |j| \cdot Y$$$. Now, you need to simulate the following updates:
Both these operations can be simulated by keeping finite differences over $$$f$$$, namely $$$f'$$$ in a segment tree.
First operation is add $$$-1$$$ on range $$$f'(-\infty .. v_i)$$$ and add $$$+1$$$ on range $$$f'(v_i + 1, \infty)$$$ (and also add $$$+\infty$$$ to some global bias value, accounting for $$$f(-\infty)$$$).
Second operation is do $$$f'(x) = clamp(f'(x), -X, +X)$$$, which is Segment Tree Beats-able (however, updating the "bias" value $$$f(-\infty)$$$ might be trickier, but still solvable).
Obviously, answer would ultimately be $$$f(0)$$$, so some partial sum on our "derivative" segment tree.
Later edit: it seems that both operations conserve the convexity of $$$f$$$, therefore it might be easier implementation-wise to simulate the operations on the second derivative $$$f"$$$ (idea similar to slope trick).
An extension of this problem appeared on AGC049 as problem E.
Task: https://atcoder.jp/contests/agc049/tasks/agc049_e
Editorial: https://atcoder.jp/contests/agc049/editorial/335
Some more discussion: https://mirror.codeforces.com/blog/entry/84664
There are 2 main approaches. (1) You can consider the DP which is the minimum cost for the first $$$n$$$ elements given that we applied the first type of operation $$$k$$$ times to the last element. Then, this DP is convex in $$$k$$$, and we can maintain it as a polyline. (2) Alternatively, you can convince yourself that it suffices to solve the 0/1 version of this problem, i.e. the problem with $$$a'_i = 0$$$ if $$$a_i < k$$$ and $$$a'_i = 1$$$ if $$$a_i > k$$$, and sum it over all thresholds $$$k$$$. Then, the 0/1 problem is a pretty simple DP, and we can try to find an efficient way to compute them all.