This is a question from a programming competition ( which has ended ). I was struggling to solve this problem but couldn't find a healthy method to do so.
The question is as follows:
IIIT Allahabad is celebrating its annual Techno-Cultural Fiesta Effervescence MM12 from 1st to 5th October. The Chef has agreed to supply candies for this festive season. The chef has prepared N boxes of candies, numbered 1 to N (Each number occurring exactly once ). The Chef is very particular about the arrangement of boxes. He wants boxes to be arranged in a particular order, but unfortunately Chef is busy. He has asked you to rearrange the boxes for him. Given the current order of boxes, you have to rearrange the boxes in the specified order. However there is a restriction.You can only swap two adjacent boxes to achieve the required order. Output, the minimum number of such adjacent swaps required.
Input
First line of input contains a single integer T, number of test cases. Each test case contains 3 lines, first line contains a single integer N, number of boxes. Next 2 lines contains N numbers each, first row is the given order of boxes while second row is the required order.
Output
For each test case, output a single integer 'K', minimum number of adjacent swaps required. Constraints:
1<=T<=10
1<=N<=10^5
Example
Input:
4
3
1 2 3
3 1 2
3
1 2 3
3 2 1
5
3 4 5 2 1
4 1 5 2 3
4
1 2 3 4
2 3 4 1
Output:
2
3
6
3
I was almost clueless about this question. Can somebody please explain the logic behind the question!!
There is no way to group all 1's together with 0 swaps. Thus, the minimum number of swaps required is 1.
Selection Sort requires the minimum number of swaps. Based on Number of Comparisons This is the number of times the algorithm compares elements to sort the input.
Given an array of n distinct elements, find the minimum number of swaps required to sort the array. This can be easily done by visualizing the problem as a graph. We will have n nodes and an edge directed from node i to node j if the element at i'th index must be present at j'th index in the sorted array.
The minimum number will be . Explanation: Since it is the exchange of cards in pairs, the exchange between two people can only be done once.
Reduce the source list to a permutation of (1,2,...,N). (By applying the inverse of the target to the source)
Then count the number of inversions.
ie
vector<int> source = ...;
vector<int> target = ...;
vector<int> inv(N)
for (int i = 0; i < N; i++)
inv[target[i]] = i;
vector<int> perm(N);
for (int i = 0; i < N; i++)
perm[i] = source[inv[i]];
Then count inversions in perm using the standard algorithm.
The problem is quite a "classic" competitive programming problem, which is counting inversions in an array. Inversion is defined as a pair (i, j) where i < j and A[i] > A[j].
The most general version, which an array of arbitrary numbers are given and you are asked to count the number of inversions, has an O(n log n) solution by modifying merge sort algorithm.
A more restricted version^, in which there is a reasonable upperbound on the maximum value in the array (note that this is NOT the length of the array), can be solved in O(n log m), where m is the maximum value in the array. The main point here is the amount of code you have to write is much less than merge sort approach.
The problem in the question is about counting the number of swaps to sort the array to certain order, which can be reconstructed as counting the number of swaps to sort the array in ascending order, and it boils down to count the number of inversions. Why number of inversions? Because you can only resolve at most one inversion per swapping 2 adjacent elements.
You need to create an array that describes the current position of the boxes with respect to the final settings. Then the algorithm can start:
Construct a Fenwick Tree (Binary Indexed Tree) with length m (m = n for the problem in the question).
We will use the Fenwick Tree to help us in counting the number of preceding elements in the array that is larger than the current element. We will keep the frequency of the numbers that we have encountered so far and use Fenwick Tree range sum query to get the number of elements less than current element (and derive the number of elements larger than current element).
Loop through n elements of the array:
The inversion count that is accumulated in the (*) step.
^ The question clearly says the elements are unique, so the algorithm above will work. I'm just not sure whether uniqueness is necessary condition, or the algorithm can be modified to accommodate the case where there are repeating elements.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With