## VM7WC '15 #1 Silver - Jung Goon

View as PDF

Points: 5
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Junghoon Jugoon Jung Goon, in an attempt to impress Mr. White, has decided to perform a complex magic trick. He starts by laying cards face down on a table in a straight line. Each card has a number such that the cards form some permutation of the numbers . However, since Jung Goon has a photographic memory, he knows the exact order of his cards. His trick involves making a series of swaps, where he switches the positions of two adjacent cards. Since he is a computer science student, he wishes to use as few swaps as possible to sort the line of cards into the order . Help him compute the minimum number of swaps required to sort the cards.

#### Input Specification

The input contains on the first line the number of test cases . Each test case consists of two input lines. The first line of a test case contains an integer , determining the number of cards. The second line of a test case contains a permutation of the numbers through , indicating the current order of the cards.

#### Output Specification

For each test case, print the minimum number of swaps needed to sort the cards.

#### Sample Input

3
3
1 3 2
4
4 3 2 1
2
2 1

#### Sample Output

1
6
1

• commented on June 10, 2019, 8:27 p.m.

just counting the number of inversions in the array should be sufficient right .

• commented on Nov. 6, 2016, 2:37 p.m.

Where do these questions come from-what is the VMSS 7 week challenge, and where is it run?

• commented on July 10, 2015, 6:57 p.m. edited

• commented on July 11, 2015, 8:42 a.m. edited

Hey Jas, just a heads up we typically don't point these things out; it's not really good etiquette. It doesn't really help anyone. Still, good observation, I'm sure many people would just miss the similarity! ;)

• commented on Jan. 8, 2015, 10:33 p.m. edit 2
• commented on Jan. 8, 2015, 11:06 p.m. edited

Don't snake

• commented on Jan. 8, 2015, 11:20 p.m. edit 2

don't Snake? :(

• commented on Jan. 8, 2015, 11:00 p.m. edited

LOL XD