Problem Detail: 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.
Asked By : Julio Garcia
Answered By : Yuval Filmus
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16400
