Inversion count

closed account (1vf9z8AR)
Question-
https://www.spoj.com/problems/INVCNT/

Method I used-
Counting no of inversions using merge sort

Problem-
I can't figure out why my answer comes wrong.
I am adding m-i to inv in line 25

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
  #include<iostream>
using namespace std;
long long int mergearr(int arr[],int l,int m,int r)
{
    long long int inv=0;
    int n1=m-l+1;
    int n2=r-m;
    int left[n1],right[n2];
    for(int i=l;i<=m;i++)
        left[i-l]=arr[i];
    for(int i=m+1;i<=r;i++)
        right[i-m-1]=arr[i];
    int i=0,j=0,k=l;
    while(i<n1 && j<n2)
    {
        if(left[i]<=right[j])
        {
            arr[k]=left[i];
            i++;
            k++;
        }
        else
        {
            arr[k]=right[j];
            inv+=m-i;
            k++;
            j++;
        }
    }
    while(i<n1)
    {
        arr[k]=left[i];
        k++;
        i++;
    }
    while(j<n2)
    {
        arr[k]=right[j];
        k++;
        j++;
    }
    return inv;
}
long long int mergesort(int arr[],int l,int r)
{
    long long int inv=0;
    if(l>=r)
        return inv;
    int m=(l+r)/2;
    inv+=mergesort(arr,l,m);
    inv+=mergesort(arr,m+1,r);
    inv+=mergearr(arr,l,m,r);
    return inv;
}
int main()
{
    int test;
    cin>>test;
    cin.ignore();
    while(test>0)
    {
        int n;
        string blank;
        getline(cin,blank);
        cin>>n;
        int arr[n];
        for(int i=0;i<n;i++)
            cin>>arr[i];
        int inv=mergesort(arr,0,n-1);
        cout<<inv<<endl;
        test--;
    }
    return 0;
}
Last edited on
inv+=n1-i;

keep in mind what your variables represent and what values may it hold
you work on the array on the portion [l, m], you copy that range to another array so you transform [l, m] to [0, n1)
so, `i' traverses the range [0, n1) and you want to know how many elements are to the right of `i'
that's `n1-i'
Topic archived. No new replies allowed.