## Tuesday, September 16, 2014

### UVa Problem 299 - Train Swapping

Problem:

Solution:

In order to solve this problem, let's consider a measure called the number of inversions. An inversion is a pair of indexes (i, j) such that i < j and a[i] > a[j]. For example, in this array, we have 5 inversions

4, 3, 1, 2

Their inversions are

(0, 1), (0, 2), (0, 3) (1, 2), (1, 3)

For example, (0, 2) is an inversion because 0 < 2, and 4 = a[0] > a[2] = 1.

It is obvious that a sorted array has no inversion. It is not hard to prove that an adjacent swap that take a larger number to the right hand side remove exactly one inversion.

So in order to sort the trains, one must remove all inversions, and one can only reduce the number of inversions one at a time with adjacent swap. That gives a lower bound on how many swaps is required.

Now consider insertion sort, it remove all inversions, and it only swap when it reduce number of inversion by one. So it swaps exactly (number of inversions) times. That means to solve this problem, all we need to do is to do an insertion sort and count the number of swaps!

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=235

#include "UVa299.h"

#include <iostream>

using namespace std;

int UVa299()
{
int number_of_cases;
cin >> number_of_cases;
for (int c = 0; c < number_of_cases; c++)
{
int number_of_carriages;
cin >> number_of_carriages;
int* carriages = new int[number_of_carriages];
for (int ca = 0; ca < number_of_carriages; ca++)
{
cin >> carriages[ca];
}

int num_swap = 0;
for (int i = 1; i < number_of_carriages; i++)
{
for (int j = i; j > 0; j--)
{
if (carriages[j] < carriages[j-1])
{
int temp = carriages[j];
carriages[j] = carriages[j-1];
carriages[j-1] = temp;
num_swap++;

}
}
}
cout << "Optimal train swapping takes " << num_swap << " swaps." << endl;

delete[] carriages;
}
return 0;
}