VM7WC '15 #1 Silver - Jung Goon

View as PDF
Submit solution
Points: 5
Time limit: 2.0s
Memory limit: 64M
Author:
thorthugnasty
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 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, 2, \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. 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

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

Sample Output

1
6
1

Comments


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

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


  • 0
    println_hi_  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?


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

    See also Train Swapping.


    • -2
      bobhob314  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! ;)


  • 2
    awaykened  commented on Jan. 8, 2015, 10:33 p.m. ← edit 2

    https://wcipeg.com/problems/desc/ccc96s2p1