I came across a problem in stackoverflow. The problem gives you an array and a value 'K'. You can move an element to right at any position, but you can't move it more than K positions left. Find the optimal ordering on which number of inversions is minimum, e.g. array 3,2,1 has 3inversions. For K=1, solution array is: 2,1,3.
I had a greedy algorithm for this problem, but can't prove its correctness (though I'm pretty sure about its correctness):
iterate the array from left to right.
For each position i we consider a subarray from i to i+k. Then we find the minimum valued element on this subarray and insert this element at the beginning of the subarray and right shift the elements between this interval.
Now, go to position i+1 and do the same.
for example:
given array = 5 3 4 7 8 2 1 0 and K = 2
This algorithm gets the solution array as this:
3 4 5 2 1 0 7 8
minimum inversion value = 12
This is just a naive version of algorithm which we can make as fast as O(nlogn).
How would you prove it if this algorithm is right?
Help is greatly appreciated.
Incorrect. When moving value X left through N values < X and M values > X your "score'increases by N-M. Why would putting X near minimum be optimal? Idk. Also we don't know if behaving totally greedily now won't negatively affect next moves. Could you please add constraints?
The solution seems right to me. Still, let's see why that is true.
Let us suppose the initial permutation is P(1..n) and define an "operation" an erasing of an element at position i and its insertion at some position j where max(1, i - k) ≤ j ≤ n. There is one important observation to the proof: the order of the first k terms of the sequence does not affect the answer. This is obvious due to the simplified form of the constraint 1 ≤ j ≤ n. Now, let's prove the first element of the solution is min{P(i), i = 1, k}. Suppose it were not. Then, because swapping the (not minimum) element with the minimum one would break only the relative order of the first k elements in the permutation, it will make our solution better. Then we have fixed the element the first element by only messing up the order of the first k numbers. Because the rest of the elements will always be amongst the first k elements, our greedy choice did not add any extra constraints to the problem, and we can safely proceed with an induction-type argument.