Problem Links Category Prerequisites Problem Statement Explanation
Let A[] be an array which is to be converted to the array B[]. Let us make another array C which stores the index of a given element A[i] in array B. [4 ,1 ,2 ,3 ](index starts from 1) Now the problem only reduces to finding the minimum number of swaps in array C in order to make it a sorted array. This further reduces to finding the number of inversions which we can easily find by using BIT (Binary Index Tree). Here’s a very nice article about finding the number of inversions . Another way of finding inversions is by using merge sort. Here’s an interesting quora article about finding the number of inversions using merge sort. Editorialist’s solution
This question is marked "community wiki".
asked 01 Feb '15, 01:07

While reading about how to solve it on the web, I came across two terms "Cayley distance" and "Kendall Tau distance". Is the problem related to either one of them? answered 01 Feb '15, 16:12

http://www.codechef.com/viewsolution/6046029 If I am not wrong, the worst case complexity of the above solution is of the order O(N^2). Can someone tell me how it got accepted in just 0.04 seconds? answered 01 Feb '15, 16:20
