REACAR-Editorial

general
, , ,
1

Problem Links

Contest

Practice

Category

Easy

Pre-requisites

BIT,Merge Sort

Problem Statement

Given an array of n distinct integers we have to find the minimum number of swaps in order to make it similar to the another array.

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.

For example

Let array A[]=[23, 34, 56, 78]

and array B[]=[34,56,78,23]

then array C will be 

[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

Solution

1 Like
2

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?

3

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?

4

This problem is based on “Kendall Tau Distance”