You are not logged in. Please login at www.codechef.com to post your questions!

×

# REACAR-Editorial

 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 This question is marked "community wiki". asked 01 Feb '15, 01:07 47●2●7 accept rate: 12%

 0 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 893●2●11●35 accept rate: 10% This problem is based on "Kendall Tau Distance" (01 Feb '15, 19:55)
 0 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 2★sandy999 391●1●16●38 accept rate: 10%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,820
×371
×149
×14

question asked: 01 Feb '15, 01:07

question was seen: 2,455 times

last updated: 04 Feb '15, 16:29