How to prove correctness of this algorithm?

Question

I am solving a problem from codeforces.

Our job is to find a minimum cost to make a given integer sequence be a non-decreasing sequence. We can increase/decrease any number of the sequence by 1 at each step and it will cost 1.

For example, when we are given a sequence 3, 2, -1, 2, 11, we can make the sequence be non decreasing with cost 4 (by decreasing 3 to 2 and increasing -1 to 2, so the non-decreasing sequence will be 2, 2, 2, 2, 11)

According the editorial of this problem, we can solve this problem using dynamic programming with 2 sequences, (one is the sequence we are given, and the other one is sorted sequence of the given one).

The outline of solution:

If we let a be the original sequence and b be the sorted sequence of the sequence a, and let f(i,j) be the minimal number of moves required to obtain the sequence in which the first i elements are non-decreasing and i-th element is at most bj. Then we can make recurrence as follows. (This is from the editorial of the problem)

f(1,1)=|a1-b1|
f(1,j)=min{|a1-bj|,f(1,j-1)},  j>1
f(i,1)=|ai-b1|+f(i-1,1),  i>1
f(i,j)=min{f(i,j-1),f(i-1,j)+|ai-bj|},  i>1, j>1

I understand this recurrence. However, I can't figure out why we should compare the original sequence with the sorted one of itself and I am not sure whether we can get the correct minimum cost with another sequence other than the sorted sequence of the given one.

How we can prove the correctness of this solution? And how can we guarantee the answer with sorted sequence to be the minimum cost?

btilly btilly · Accepted Answer · 2013-06-26T06:22:31

The point of the exercise is that this recurrence can be proven with induction. Once it is proven, then we have proven that f(n,n) is the minimum cost for winding up with a solution where the nth value is at most bn.

To finish proving the result there is one more step. Which is to prove that any solution where the nth value exceeds bn can be improved without increasing that maximum value. But that's trivial - just omit one of the +1s from the first value to exceed bn and you have a strictly better solution without a larger maximum. Therefore no solution winding up with a maximum greater than bn can be better than the best with a maximum at most bn.

Therefore we have the optimal solution.

How to prove correctness of this algorithm?

1 Answers