Problem Setter : Ashish Khatkar
Problem Tester : Ambar Pal
Editorialist : Ashish Khatkar
Contest link : INTERSEC
Practice link : INTERSEC
Pre-requisites : Merge Sort
For merge sort visit this link and select merge sort.
Now, lets come to the problem. Problem asked to find the number of intersections if we draw one-one correspondence line from given permutation to sorted permutation.
Lets see the sample test case given in the ques.
Now, when will be there an intersection. Intersection will be only when there are integers in the permutation after the given integer i which are smaller than i. In the given example, 5 intersects with 2 integers 3 and 4 because they are smaller than 5.
When there is a pair of integers such that A[i] < A[j] and i > j we call such pair an inversion. In this problem we need to calculate these pairs because intersection is only possible for such pairs.
For 40 points you can just use two for loops (bubble sort method to find the inversion pairs).
Pseudocode :
ans = 0
for j = 0 to n-1:
for i = j+1 to n-1:
if(ar[i] < ar[j])
ans = ans + 1
print ans
This was sufficient for 40 points.
But for another 60 points you need to do something smarter. For this we will use mergesort to count the no of inversions in given permutation.
Merge sort is a classic divide and conquer algorithm. So while sorting suppose we know the no. of inversions in left subpart and no. of inversions in right subpart i.e
So, now we know no. of inversions in left part and no. of inversions in right part. So what is left is to find the no. of inversion pairs which have one element in left sub-part and one element is right sub-part which are nothing but no. of inversions which we need to count during merge step.
Now, during merge step suppose i is the index for left array and j is the index for right array. Now, at any step during merge if A[i] > A[j] than there are (mid - i + 1) inversions because left and right sub-arrays are sorted so all the elements from A[i] to A[mid] will be greater than A[j] so the inversion count is mid - i + 1.
We have our inversions for merge step, so the inversion count (ans) will be
leftInversions + rightInversions + inversionsFoundDuringMergeStep
Pseudocode:
partition(A, low, high) :
ans = 0
if (low < high) :
mid = (low + high)/2
ans = partition(A, low, mid)
ans += partition(A, mid+1, high)
ans += merge(A, low, mid, high)
return ans
merge(A, low, mid, high) :
Normal merge operations except line with comment :
while((l<=mid)&&(m<=high))
{
if(arr[l]<=arr[m])
{
temp[i]=arr[l];
l++;
}
else
{
ans+=(mid-l+1); // This line
temp[i]=arr[m];
m++;
}
i++;
}
//NOTE: This merge operation is not complete, pseudocode is only shown to tell you how to use merge sort to find inversions.