Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

### wish_me's blog

By wish_me, history, 2 years ago, ,

There are n-pairs and therefore 2n people. everyone has one unique number ranging from 1 to 2n. All these 2n persons are arranged in random fashion in an Array of size 2n. We are also given who is partner of whom. Find the minimum number of swaps required to arrange these pairs such that all pairs become adjacent to each other.

n<10^3 arr.size<10^3

Input: n = 3

pairs[] = {1->3, 2->6, 4->5} // 1 is partner of 3 and so on

arr[] = {3, 5, 6, 4, 1, 2}

Output: 2

We can get {3, 1, 5, 4, 6, 2} by swapping 5 & 6, and 6 & 1

• +4

 » 2 years ago, # |   +10
•  » » 2 years ago, # ^ |   +10 your jokes are worth your rating
•  » » » 2 years ago, # ^ |   0 That wasn't a joke... I was just telling him to first google the question and then only ask here.PS-> Your views tell a lot about your thinking about people below you(rating wise)... God bless you :-)
•  » » » » 2 years ago, # ^ |   0 Let's call a spade a spade. That wasn't a friendly advice to google the question. He is wise who says nothing when he has nothing to say.PS-> Your jokes tell a lot about your thinking about people below you(rating wise)... God bless you :-)
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 As I said...that wasn't a joke.. :-) :-)
 » 2 years ago, # | ← Rev. 2 →   +7 Up. I met this problem before and know linear reference solution but I can't prove it :(
•  » » 2 years ago, # ^ |   0 The solution which makes swaps along the cycles of permutation?
•  » » » 2 years ago, # ^ |   +5 Yep.Consider first two elements. If they are partners then skip them and move to the next two elements. Otherwise find a pair for any of these two elements (suppose the pair was among a[2k] and a[2k + 1]), make swap, now move to elements with indexes 2k and 2k + 1 and repeat step.
•  » » » » 8 months ago, # ^ |   0 Thanks for small comment. Makes huge difference.