Inversion Count - SPOJ

Feroz Ahmad bio photo By Feroz Ahmad Comment
In the Question Inversion Count - INVCNT on spoj, you need to print the no. of inversion pairs. The question defines it as - "Let A[0...n - 1] be an array of n distinct positive integers. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A". So basically an inversion pair is the one in which if indices and the values have invert relation. ( if one is > the other is < ). The first basic approach which comes to mind is simple Brute Force algo. That is selecting one element(let it be i th) in the array and then checking all the elements ( j index for that matter) after the selected element for the condition Arr[i]> Arr[j], if such pair occurs then count++. But time complexity of this approach is O(n2). But submitting this solution will lead to TLE (time limit exceeded). So we need to use some other algo, and the solution uses Merge Function in Merge Sort Algorithm. Actually when we merge the two sorted array, while comparing elements we can perform the counting of inversion pairs. This can be done as : (for ascending order sorting) When the current element under consideration in right sub-array is smaller than current element under consideration in left sub-array the no of inversion pairs equals to the no. of all the elements after the current element in left sub-array (including itself), in each level of merge sort. Sum of all these pairs will be equal to inversion pairs. This can be understood using following : IMG_20150411_231458239_HDR Here is the following pseudo-code :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream> 
typedef long long int typex;
using namespace std;
long long int count,arr[200001];
void merge(typex p,typex q,typex r)
{
	//first array has indices from p to q
	//second array has indices from q to p
    typex i,li,ri,n1,n2;
    n1=q-p+1;
    n2=r-q;
    typex *lt= new typex [n1];
    typex *rt= new typex [n2];//[q-(r+1)+1]
    // HERE copy both the arrays in the newly dynamically allocated array.
    //left and right array is ready which is all ready sorted
    //now we will merge
    //indices fr left copy and right copy respectively
    li=ri=0;
    i=p;//index for array being sorted
    while(li< n1 && ri< n2)
    {
        if(lt[li]> rt[ri])
        {
            arr[i++]=rt[ri++];
            count=count+n1-li;// MAIN STEP
        }
         else //right hand side elemnt is greater that is inversion pair
        {
            arr[i++]=lt[li++];
        }
    }
//inversion pairs have been counted till this stage, do not count again;
    while(li<n1)
        arr[i++]=lt[li++];
    while(ri<n2)
        arr[i++]=rt[ri++];
}
void mergesort(typex p,typex r)
{
    if(p<r)
    {
        typex q=(p+r)/2;
        mergesort(p,q);
        mergesort(q+1,r);
    }
}
int main()
{
   ////Write code accordingly
        count=0;
        mergesort(0,n-1);
        cout<<"\n"<<count;
	////
}
Complete Solution : https://ideone.com/UBCpT9
comments powered by Disqus