4
$\begingroup$

This was asked in the (very) recently concluded Hackerrank Worldcup. Paraphrased:

Given a permutation $a$ of integers from $1$ to $N$, how can I minimize the number of inversions by a single swap of any two integers?

An inversion is a pair of indices $(i, j)$ such that $i < j$ but $a[i] > a[j]$.

I think that this can be achieved by swapping the numbers which have been shifted the most from their position. That is:

If $n_{inv}(a)$ is the number of inversions in a permutation $a$, and $swap_a(i, j)$ is the permutation obtained by swapping the integers at $i$, $j$, then:

$$ \underset{i, j}{argmin} \{n_{inv}(swap_a(i, j))\} = \underset{i}{argmax} (a[i] -i), \underset{j}{argmin} (a[j] - j) $$

In pseudo-code:

leftmost = [-1, -1]        # The first value is the displacement
rightmost = [1, -1]        # The second the index where it occurred
for i in 1..n
    d = N[i] - i           # N being the array of numbers
    if d > leftmost[0]
        leftmost[0] = d
        leftmost[1] = i
    else if d < rightmost[0]
        rightmost[0] = d
        rightmost[1] = i
return leftmost[1], rightmost[1]

The thing is, I have no idea why this is correct, or even if it is. How can I prove that this works? Or determine the conditions for which it will work?


I have been struggling to understand how I reached this idea and feel that proving it would help me.

To be clear, I am not looking for a solution to the minimizing inversions problem, but only a way to prove that the solution I came up with is correct or incorrect.

$\endgroup$
  • 4
    $\begingroup$ It didn't work for some of the test cases, ergo it is incorrect. $\endgroup$ – Yuval Filmus Sep 20 '15 at 21:33
  • $\begingroup$ @YuvalFilmus the coding problem itself has some extra conditions (like lexicographically earlier set of indices being preferred, the output being a given string if you cannot decrease the number of inversions, etc.). Neither of us can be sure that these conditions aren't the reason for the failure in those test cases (that's to say - error in implementation vs error in algorithm). $\endgroup$ – muru Sep 20 '15 at 21:39
  • $\begingroup$ @YuvalFilmus for example, the method above will always return a set of valid indices, and it might be that for some cases, swapping these indices keeps the number of inversions same (only case I can think of when this can happen is when the integers are sorted, but if there is another case...). $\endgroup$ – muru Sep 20 '15 at 21:41
  • 1
    $\begingroup$ Then implement the extra conditions! $\endgroup$ – Raphael Sep 21 '15 at 7:34
  • 3
    $\begingroup$ Sorry, but this is a bad place for "check my algorithm" type of questions. Please try to formulate an argument for why your solution should be correct. $\endgroup$ – Raphael Sep 21 '15 at 7:42
4
$\begingroup$

Let's calculate the difference in number of inversions given that you swap $a_i$ and $a_j$. We can assume that $i < j$. There are three kinds of pairs of indices whose status (being inversions or not) could change as a result of the swap: $(i,j)$ and, for $i < k < j$, $(i,k)$ and $(k,j)$. We can distinguish two cases: $a_i < a_j$ and $a_i > a_j$.

If $a_i < a_j$ then the pair $(i,j)$ becomes an inversion, and for every $i < k < j$, there are three possible cases:

  1. $a_k < a_i < a_j$: number of inversions stays the same.

  2. $a_i < a_j < a_k$: number of inversions stays the same.

  3. $a_i < a_k < a_j$: number of inversions increases by 2.

This is clearly not a good idea if you can avoid it. If you must (when the permutation is monotone increasing), it's best to switch a pair $a_i,a_{i+1}$.

In contrast, if $a_j < a_i$ then the number of inversions decreases by one plus twice the number of indices $i < k < j$ such that $a_j < a_k < a_i$. As a consequence, if the permutation is not monotone increasing, your goal is to choose a pair $(i,j)$ such that $a_j < a_i$ and the number of indices $i < k < j$ satisfying $a_j < a_k < a_i$ is maximal. You take it from here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.