Hi everybody! Can any one help me solving this problem.
Given an array of n integers in range 1 to 106 (1 ≤ n ≤ 103), find the minimum steps to make the absolute difference of every two numbers less than or equal to one?
At each step we can subtract 1 from one number and add 1 to an adjacent number.
For example if we do one step on 2nd element of this array: 1,2,3. It can become 2,1,3 or can become 1,1,4 ?
What does step mean?
At each step we can subtract 1 from one number and add 1 to an adjacent number.
Both adjacent numbers? i.e. if we do one step on 2nd element of this array: 1,2,3. It will became 2,1,4?
You can view just the effect of the moves on the differences array: define b[i] = a[i] — a[i + 1] for each 1 <= i < N. Now, a move actually makes b[i] += 2 or b[i] -= 2. In order for the final condition to hold, we need -1 <= b[i] <= 1. Also, we need -1 <= b[i] + b[i + 1] + ... + b[j] <= 1 for each 1 <= i <= j < N. Let's define a third array c[i] = b[1] + b[2] + ... + b[i]. The above condition rewrites as -1 <= c[j] — c[i] <= 1 for each 0 <= i < j < N. That also implies , -1 <= c[j] <= 1 for each j (as we could choose i = 0 in the precedent condition). whenever we fix the value of a new b, to make sure the condition would hold, we need to compute the new value of c (which will be -1, 0 or 1) and check whether there is some newly formed subarray of b with the absolute value of the sum greater than 1. For that, it's enough to keep the last value of c, and the maximum and minimum ones so far. Hence, we get dp[i][j][k][p] = minimum number of moves to make change the first i values of b in such a way that their sum (which is c[i]) is p and the minimum and maximum value of a partial sum encountered so far are j and k (these values are actually the minimum and maximum values of c[something <= i]). The transition can be done in constant time, as we could iterate the value q of b[i + 1] and go from dp[i][j][k][p] to dp[i + 1][min (j, p + q)][max (k, p + q)][p + q] with the condition that -1 <= p + q <= 1 and |j — (p + q)| <= 1 and |k — (p + q)| <= 1. That can be achieved with something like |b[i + 1] — q| / 2 operations, as long as this is an integer (otherwise, it's impossible to change the value of b[i + 1] to q as the parity is invariant). Thus you get O(N) complexity, though with a pretty large constant factor of 3^4. You could decrease this constant factor in some ways (for example dp[i][j][k][p] is defined only when |j — k| <= 1 and j <= p <= k, the parity stuff and so on)
Another solution: we keep the notations of the previous one. Observe that the overall sum is invariant, so if you denote it by S, you'll know the exact values of the final array (without the order though). We saw that if b is even, b will remain even, so it should be 0 and -1 or 1 otherwise. Basically, we identified the contiguous segments of equal values in the final array. Let's say we'll find our that out final array will be something like:
aaabbccccdeef
And we know that the final array will have K values of X and N — K values of X + 1. So, we get two cases: either a = c = e = X and b = d = f = X + 1 or a = c = e = X + 1 and b = d = f = X. One of the cases, if not even both could fail, as we have to have EXACTLY K values of X and the rest of X — 1. But we get at most two final arrays for a to check. Once we have a final array we can look at it's difference array d[i] = finalA[i] — finalA[i + 1]. And the number of moves to obtain finalA from a is sum of |b[i] — d[i]| / 2 (which we'll know is an integer by the way we chose finalA based on the arrray b). Thus we get O(N) with no dp involved and a really small constant factor (N could be one million and the values up to 10^9)