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

×

REACAR-Editorial

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

murdocc007's gravatar image

3★murdocc007
4727
accept rate: 12%

edited 01 Feb '15, 14:56


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?

link

answered 01 Feb '15, 16:12

dragonemperor's gravatar image

3★dragonemperor
89321135
accept rate: 10%

This problem is based on "Kendall Tau Distance"

(01 Feb '15, 19:55) pulkitsinghal6★

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?

link

answered 01 Feb '15, 16:20

sandy999's gravatar image

2★sandy999
39111638
accept rate: 10%

edited 04 Feb '15, 16:29

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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