Denis' Solution 1A: Train Swapping

This is the personal work of Denis Dmitriev; it is not an officially verified or endorsed solution.

Denis writes: The solution is based on the fortunate fact that the optimal number of the required train swaps is equal to the number of swaps done by the bubble sort on the same data set (even though bubble sort does not necessary exchange adjacent elements). Proof of this fact is left as an excersize to the reader. -DD


C++ Source Code

#include <stdio.h>
#include <stdlib.h>

void main(void)
{
    FILE *fp=fopen("swap.in","r");
    FILE *fo=fopen("swap.out","w");

    int cnt,i,j,n,t[51],ntests;

    /* determine the number of test cases */
    fscanf(fp,"%d",&ntests);

    for(;ntests--;)
    {
        /* read test case data */
        fscanf(fp,"%d",&n);

        for(i=0;i<n;i++)
            fscanf(fp,"%d",t+i);

        /* bubble sort */
        for(cnt=i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                if(t[i]>t[j])
                {
                    t[i]^=t[j]^=t[i]^=t[j];
                    /* count the number of swaps */
                    cnt++;
                }
            }
        }

        /* print the result */
        fprintf(fo,"Optimal train swapping takes %d swaps.\n",cnt);
    }

    fclose(fo);
    fclose(fp);
}