LPAIR - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Shiplu Hawlader
Tester: Tasnim Imran Sunny
Editorialist: Lalit Kundu

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

MergeSort
Binary Indexed Tree

PROBLEM:

There are N males and N females (N<=10^5). Each male and female have indexes (unique for all males and unique for all females). All males are arranged in one line (standing at equal distances) according to increasing value of indexes. Similarily for females in another line.
Now pairings are done(between males and females) and line is drawn between each pair. We have to find how many pair of lines intersect each other.

QUICK EXPLANATION:

We map all indexes of males to values between 1 and N. Let’s define a map A. A[i]=j, if there is a pair of male with value i and female with index j. Now, answer is number of pairs of i and j such that A[i] > A[j] and i < j. This is same as counting inversions in an array. We can use Binary Indexed Tree or Enhanced MergeSort to count such pairs.
See explanation for implementation and further details.

EXPLANATION:

We need to count how many pairs i,j exist such that A[i] > A[j] and i < j.
Suppose we pick A[i]. We need to count how many j exist(j > i) such that A[j] < A[i]. So if we have a data structure where we have inserted all A[j] such that j>i, we just need to count how many values in data structure exist which are less than A[i].
That’s where a BIT comes in. Read the topcoder tutorial on BIT first. We will update A[j] with 1 if insertion is done. To count, we find the sum of all elements in the BIT from j=1 to A[i]-1.
But since BIT can handle upto 10^6 indexes, we map all A[i]'s to numbers between 1 and N. How do we map? We sort all the indexes and give them values from 1 to N.

Pseudo code:

// Assume all numbers have been mapped properly between 1 to N.
ans=0   
for i=1 to N:   
   ans += foo(i)   
print ans   
   
// function foo   
foo(i):   
    for j=i+1 to N:   
        update(A[j],1)  // update(x,1) increases value of x in BIT by 1.   
    return read(A[i]) // read(x) returns some of values of all indexes which are less than x

But the above pseudo code will be O(n*n) solution. How can we do it in one loop? Since for each i, we need A[j] where j>i, so we begin from i=N moving towards 1.

Pseudo code:

// Assume all numbers have been mapped properly between 1 to N.   
ans=0   
for i=N to 1:   
    ans += read(A[i])   
    update(A[i],1)   
print ans

Each update and read query takes O(log(n)), so total complexity O(NlogN).

ALTERNATIVE SOLUTION:

Using Enhanced Merge Sort, here is a proper explanation.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

Problems with applications of BIT:
IITI15
MSE06H

9 Likes
2

Can someone tell what is wrong with this solution? I am not able to figure out.
http://www.codechef.com/viewsolution/3431031

3

For input:

4
4 10
1 30
2 20
3 5

it returns 3, but for

4
1 30
2 20
3 5
4 10

it returns 5…

1 Like
4

I am getting Time limit exceeded for my solution… http://www.codechef.com/viewsolution/3432102 … :-/
Where can I optimize?

5

N <= 10^5, not 10^4…

6

Your algorithm runs in O(N^2), which is O(10^10), no chance to do this in 2 seconds…

7

How similar to this problem: Live Archive.

That problem was extended to even harder constraints than here (BIT can handle 10^6 marriage lines as well) and used almost exactly 5 years ago in a minor Slovak ACM training. Counting inversions by BIT is quite standard, anyway - on that note, the mergesort method is infinitely more difficult…

Also, I believe that in “There are N males and N females (N<=10^4).”, you meant 10^5.

1 Like
8

Not to mention this one: http://code.google.com/codejam/contest/619102/dashboard

However, I think that this is also part of the reason why people evolve and get better right? The more resources you know, the more logics you’ve seen, well, the better you can get :smiley:

1 Like
9

Yeah… it’s funnier when there are several problems that can be somehow solved using BITs, and someone does excellently because he knows them well :smiley:

1 Like
10

Well, sadly for me, this contest was another one I couldnt attend properly… :frowning: I only solved 1 fully written on a Samsung Tablet with a crappy cafe wifi, but, got the logic for the second and third ones fast :smiley: Maybe Codechef is slowly starting to pay off for me, so I hope I can upsolve everything and learn cool tricks :smiley:

1 Like
11

Use merge sort for counting inversions that will reduce the time from O(N^2) to O(NlogN).

12

Hello,

Before I attempt to solve this problem using the BIT approach, I am trying to get AC using the Enhanced MergeSort trick, as described in editorial.

However, I am a bit confused on how can we do the mapping of the values and still count the number of inversions… Do we use a simple map<int, int> and do something like:

int main()
{
	intmap map;
	int Np;
	cin >> Np;
	vector<int> v;
	while(Np--)
	{
		int m,f;
		cin >> m >> f;
		map[m] = f;
	}
	cout << countsInv(map) << endl;
	return 0;
}

where, intmap stands for a map<int, int> ?

If the above main idea is correct than all I need to do is to write the countsInv procedure, where this follows the same principle of counting the number of inversions in a simple vector, but, this time using a map.

Am I thinking correctly or is there an additional detail I need to take into account?

Best,

Bruno

13

Array M is not sorted. You have to first sort them and then count the inversions. And you can use pairs. http://www.codechef.com/viewsolution/3429016

14

I have tried the following code for many test cases but codechef is still not accepting the solution. What is problem with my code?

#include<iostream>
using namespace std;

long long int Merge(int* left,int* right,int* arr,int nl,int nr)
{
    int i=0;
    int j=0;
    int k=0;
    long long int cnt=0;
    while(i<nl&&j<nr)
    {
        if(left[i]<=right[j])
        {
            arr[k]=left[i];
            i++;
        }
        else
        {
            arr[k]=right[j];
            j++;
            cnt+=nl-i;
        }
        k++;
    }
    while(i<nl)
    {
        arr[k]=left[i];
        i++;
        k++;
    }
    while(j<nr)
    {
        arr[k]=right[j];
        j++;
        k++;
    }
    return cnt;
}

long long int MergeSort(int *a,int len)
{
    long long int cnt=0;
    if(len<2)
        return 0;
    int mid=len/2;
    int* left=new int[mid];
    int* right=new int[len-mid];
    for(int i=0;i<mid;i++)
        left[i]=a[i];
    for(int i=mid;i<len;i++)
        right[i-mid]=a[i];
    cnt+=MergeSort(left,mid);
    cnt+=MergeSort(right,len-mid);
    cnt+=Merge(left,right,a,mid,len-mid);
    delete(left);
    delete(right);
    return cnt;
}

int main()
{
    int n;
    cin>>n;
    int* fm=new int[n];
    for(int i=0;i<n;i++)
        cin>>fm[i]>>fm[i];
    cout<<MergeSort(fm,n);
}
15

And what about reading this thread first?

For input:

4
4 10
1 30
2 20
3 5

it returns 4, but for

4
1 30
2 20
3 5
4 10

it returns 5…

16

@betlista I got the point and i have a strategy. Insert male number using insertion sort and then insert female number at that male spot. Is it a fine strategy? Or is there a simple strategy also?

17

why does this logic fails?

 
count=0;
     for(i=0;i&ltt;i++)
     {
         for(j=i+1;j&ltt;j++)
         {
              if(a[i][0]>a[j][0])
              {
                if(a[i][1]&lta[j][1])
                     {
                      
                         count++;
                     }
               }
               else
               {
                 if(a[i][1]>a[j][1])
                     {
                       
                         count++;
                     }  
                 }
          }
         
       }
     
     printf("%d",count);