USING JAVA At an old railway station, you may still encounter one of the last re

Question

USING JAVA

At an old railway station, you may still encounter one of the last remaining "train swappers". A train swapper is an employee of the railroad, whose sole job it is to rearrange the carriages of trains. Once the carriages are arranged in the optimal order, all the train driver has to do, is drop the carriages off, one by one, at the stations for which the load is meant The title "train swapper" stems from the first person who performed this task, at a station close to a railway bridge. Instead of opening up vertically, the bridge rotated around a pillar in the center of the river. After rotating the bridge 90 degrees, boats could pass left or right The first train swapper had discovered that the bridge could be operated with at most two carriages on it. By rotating the bridge 180 degrees, the carriages switched place, allowing him to rearrange the carriages (as a side effect, the carriages then faced the opposite direction, but train carriages can move either way, so who cares) Now that almost all train swappers have died out, the railway company would like to automate their operation. Part of the program to be developed, is a routine which decides for a given train the least number of swaps of two adjacent carriages necessary to order the train. Your assignment is to create that routine Input The input contains on the first line the number of test cases (N). Each test case consists of two input lines. The first line of a test case contains an integer L, determining the length of the train (0sL50) The second line of a test case contains a permutation of the numbers 1 through L, indicating the current order of the carriages. The carriages should be ordered such that carriage 1 comes first, then 2, etc with carriage L coming last Output For each test case output the sentence: 'Optimal train swapping takes S svaps.' where S is an integer Sample Input 1 3 2 4 3 2 1 2 2 1 Sample Output Optimal train swapping takes 1 swaps Optimal train swapping takes 6 swaps Optimal train swapping takes 1 swaps

Explanation / Answer

The given problem can be solved through the fact that the number of swaps needed is equal to number of inversions count of an array.

The fact is established by using the following observations:

two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j.

Sample Code:

import java.io.*;

import java.util.*;

class Test {

// This function merges two sorted arrays and returns inversion

// count in the arrays.

static int merge(int arr[], int temp[],

int left, int mid, int right)

{

int inv_count = 0;

// i is index for left subarray

int i = left;

// j is index for right subarray

int j = mid;

// k is index for resultant merged subarray

int k = left;

while ((i <= mid - 1) && (j <= right))

{

if (arr[i] <= arr[j])

temp[k++] = arr[i++];

else

{

temp[k++] = arr[j++];

/*At any step in merge(), if a[i] is greater than a[j],

then there are (mid - i) inversions.

because left and right subarrays are sorted,

so all the remaining elements in left-subarray (a[i+1], a[i+2] - a[mid])

will be greater than a[j]*/

inv_count = inv_count + (mid - i);

}

}

// Copy the remaining elements of left subarray (if there are any) to temp

while (i <= mid - 1)

temp[k++] = arr[i++];

//Copy the remaining elements of right subarray (if there are any) to temp

while (j <= right)

temp[k++] = arr[j++];

//Copy back the merged elements to original array

for (i=left; i <= right; i++)

arr[i] = temp[i];

return inv_count;

}

// An auxiliary recursive function that

// sorts the input array and returns

// the number of inversions in the array.

static int _mergeSort(int arr[], int temp[],

int left, int right)

{

int mid, inv_count = 0;

if (right > left)

{

// Divide the array into two parts and

// call _mergeSortAndCountInv() for

// each of the parts

mid = (right + left)/2;

/* Inversion count will be sum of

inversions in left-part, right-part

and number of inversions in merging */

inv_count = _mergeSort(arr, temp,

left, mid);

inv_count += _mergeSort(arr, temp,

mid+1, right);

//Merge the two parts

inv_count += merge(arr, temp,

left, mid+1, right);

}

return inv_count;

}

// This function sorts the input array and returns the number of inversions in the array

static int countSwaps(int arr[], int n)

{

int temp[] = new int[n];

return _mergeSort(arr, temp, 0, n - 1);

}

public static void main (String[] args)

{

Scanner sc = new Scanner(System.in);

int T = sc.nextInt();

while(T-->0){

int l = sc.nextInt();

int arr[]=new int[l];

for(int i=0;i<l;i++){

arr[i] = sc.nextInt();

}

System.out.println("Optimal train swapping takes "

+ countSwaps(arr, l)+" swaps.");

}

}

}

Sample Input:

3
3
1 3 2
4
4 3 2 1
2
2 1

Sample output:

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.