Train Swapping#8735

Train Swapping (Editorial)

Let the array $m$ contain the input permutation — the current order of the train cars. The desired minimum number of swaps is equal to the number of inversions in this permutation.

An inversion is a pair of elements $(m_{i}, m_{j})$ (m_i, m_j) such that $i < j$ i < j but $m_{i} > m_{j}$ m_i > m_j. In other words, a pair of elements forms an inversion if they are arranged in the wrong order.

For example, in the array $m = {3, 1, 2}$ m = \{3, 1, 2\}, the pairs $(3, 1)$ and $(3, 2)$ form inversions. The pair $(1, 2)$ does not form an inversion since the numbers $1$ and $2$ are in the correct relative order.

The number of inversions in an array of length $n$ can be counted using a double loop: iterate over all possible pairs $(i, j)$ such that $1 \leq i < j \leq n$ 1 \le i < j \le n, and if $m_{i} > m_{j}$ m_i > m_j, increase the inversion counter by one.

Example

Let us consider an example of counting inversions in a permutation. Under each number, we'll write the number of inversions it forms with the elements to its right. Let $in v [i]$ denote the number of indices $j$ such that $i < j$ i < j and $m [i] > m [j]$ m[i] > m[j].

The total number of inversions is $16$ .

Exercise

Simulate the solution for the following example.

Algorithm implementation

Declare the array $m$ .

int m[100010];

Sequentially process all $t es t s$ test cases.

scanf("%d", &tests);
while (tests--)
{

Read the input order of the train cars into the array $m$ .

  scanf("%d", &n);
  for (i = 0; i < n; i++)
    scanf("%d", &m[i]);

The minimum number of swaps required to arrange the train in order is computed and stored in the variable $r es$ .

  res = 0;
  for (i = 0; i < n - 1; i++)
  for (j = i + 1; j < n; j++)
    if (m[i] > m[j]) res++;

Print the answer.

  printf("Optimal train swapping takes %lld swaps.\n", res);
}