# UVa 299

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.