UVa 299

From Algorithmist
Jump to navigation Jump to search

299 - Train Swapping[edit]

Summary[edit]

This problem amounts to counting the number of inversions in the dataset. , so we can do this trivially using an 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 sorting algorithms, but they are overkill as

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.