Procon Junior (Intersections) Editorial

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.

alt text

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

alt text

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.