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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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, 2013 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, 2013 at 16:08
  • $\begingroup$ So, why I got j-i+n-2? $\endgroup$
    – Julio Garcia
    Oct 24, 2013 at 16:22
  • $\begingroup$ That's a question for you... $\endgroup$
    – Yuval Filmus
    Oct 24, 2013 at 18:54
  • $\begingroup$ Touche, well thanks for taking me in the right direction. $\endgroup$
    – Julio Garcia
    Oct 24, 2013 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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