VM7WC '15 #1 Silver - Jung Goon

View as PDF

Submit solution

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

Problem type

Junghoon Jugoon Jung Goon, in an attempt to impress Mr. White, has decided to perform a complex magic trick. He starts out by laying L (0 \le L \le 60) cards face down on a table in a straight line. Each card has a number such that the L cards form some permutation of the numbers 1 \dots L. 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 1,2,\dots,L-1,L. 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 N (1 \le N \le 10). Each test case consists of two input lines. The first line of a test case contains an integer L, determining the number of cards. The second line of a test case contains a permutation of the numbers 1 through L, 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

1 3 2
4 3 2 1
2 1

Sample Output



  • 0
    stringray  commented on June 10, 2019, 4:27 p.m.

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

  • 0
    println_hi_  commented on Nov. 6, 2016, 9:37 a.m.

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

  • 1
    d  commented on July 10, 2015, 2:57 p.m.

    See also Train Swapping.

    • -2
      bobhob314  commented on July 11, 2015, 4: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! ;)

  • 1
    d  commented on July 10, 2015, 2:57 p.m. edited