6
$\begingroup$

I have come across a question that is a bit hard to understand due to its wording, I may havecome up with a possible solution, but I don't know if it's correct. Can you please help me? Thanks in advance!

Question

Suppose we exchange elements $a[i]$ and $a[j]$, where $j > i$, which are originally out of order.

For example, $a = [2,8,3,7,1,5,6]$ and we exchange the second and sixth elements, we have $[2,5,3,7,1,8,6]$.

The array has now fewer inversions. What is the maximum number of inversions that can be removed if we exchange $a[i]$ and $a[j]$?

My proposed answer

Take an array and sort it in reverse order. The first element would have the most inversions. We switch it with the last element and the number of inversions decrease drastically.

The maximum number of inversions would be $j-i+n-2$.

My concern

Since the question doesn't say anything about me being allowed to change the order of the array, I don't know if my proposed answer is the one they were aiming for.

$\endgroup$
5
$\begingroup$

The question is indeed not completely clear, but they definitely wanted you to search the "worst possible" array $a$ (the one leading to the largest number of removed inversions). Otherwise there is nothing to do - just look at the array and calculate the number of inversions resulting from the swap.

What is somewhat less clear is whether they also wanted you to optimize over $i$ and $j$. Your answer, which doesn't assume that, is on the safe side.

One thing you haven't shown is that your example leads to the maximal number of inversions being removed. The argument is very simple, but it's still needed for completeness.

$\endgroup$
  • $\begingroup$ when you say leads to maximal number of inversions, do you mean show that the first element takes n-1 inversions and so on? $\endgroup$ – Julio Garcia Oct 24 '13 at 16:00
  • 1
    $\begingroup$ No - rather, that for given $i,j$, the amount of inversions removed that you obtain is the maximal over all choices of $a$. That may be obvious, and indeed the proof is not difficult, but it is part of the proof. The proof has two parts: (i) this particular array results in so many inversions removed, (ii) all arrays result in at most as many inversions removed. $\endgroup$ – Yuval Filmus Oct 24 '13 at 16:08
  • $\begingroup$ So, why I got j-i+n-2? $\endgroup$ – Julio Garcia Oct 24 '13 at 16:22
  • $\begingroup$ That's a question for you... $\endgroup$ – Yuval Filmus Oct 24 '13 at 18:54
  • $\begingroup$ Touche, well thanks for taking me in the right direction. $\endgroup$ – Julio Garcia Oct 24 '13 at 20:18

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.