UVa 299

From Algorithmist
Jump to: navigation, search

299 - Train Swapping[edit]

Summary[edit]

This problem amounts to counting the number of inversions in the dataset. L\leq 50, so we can do this trivially using an O(N^{2}) algorithm, such as bubble sort or insertion sort.

Explanation[edit]

Counting the number of inversions simply counts the number of swaps it takes in sorting, which is straightforward for bubble sort - increment a counter everytime you swap two adjacent items.

In c++ you can swap easily by using algorithm library function but it is not appropriate in that problem.

Optimizations[edit]

This can also be done with O(N\log N) sorting algorithms, but they are overkill as L\leq 50

Input[edit]

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

Output[edit]

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