Train Swapping

Interview

Time limit1sMemory limit128 MB

Summary

For each test case, count the inversions of a permutation of 1..L, the minimum number of adjacent swaps needed to sort the train.

Level: Easy3 of 10
Topics: Array, Sorting, Math, Brute force
Solved: No attempts yet

Problem

At an old railway station you may still meet one of the last remaining "train swappers". A train swapper is a railway employee whose only job is to rearrange the carriages of trains.

Once the carriages are in the best order, the driver simply drops them off one by one at the stations each load is meant for.

The name "train swapper" comes from the first person to do this job, at a station next to a railway bridge. Instead of opening upward, that bridge rotated around a pillar in the middle of the river; after turning 90 degrees, boats could pass on either side. The first train swapper found that the bridge could be operated with at most two carriages on it: turning the bridge 180 degrees swapped those two carriages, letting him rearrange the train. (As a side effect the carriages then faced the opposite way, but a carriage runs equally well in either direction, so it does not matter.)

Now that the train swappers are almost gone, the railway wants to automate their work. Part of the program must decide, for a given train, the least number of swaps of two adjacent carriages needed to sort it. The minimal number of adjacent swaps that sorts a permutation equals its number of inversions — the number of pairs of carriages that are currently in the wrong relative order.

Questions:

For a train $T$ , let $m[T]$ be the minimal number of swaps needed to sort $T$ . What is the largest possible value of $m[T]$ for a train of $L$ carriages? (It is $L(L-1)/2$ , reached when the train is completely reversed.)
Write a program that meets the specification below.

Input

The first line contains the number of test cases $N$ .

Each test case consists of two lines:

The first line contains an integer $L$ , the length of the train ( $0 \le L \le 50$ ).
The second line contains a permutation of the numbers $1$ through $L$ , the current order of the carriages. The carriages must be sorted so that carriage $1$ comes first, then $2$ , and so on, with carriage $L$ last.

Output

For each test case, print the sentence:

Optimal train swapping takes S swaps.

where $S$ is the minimal number of swaps needed to sort that train.

Examples3

Example 1

Input

Expected output

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.

Example 2

Input

1
5
1 2 3 4 5

Expected output

Optimal train swapping takes 0 swaps.

Example 3

Input

1
1
1

Expected output

Optimal train swapping takes 0 swaps.