Guard value error.
L[n1]=99999999;
R[n2]=9999999;
R[n2] may be merged and counted, if L[1..n1-1] has 9999999.
On 2011-5-12 19:18, Akshata Sharma wrote:
I tried to solve this problem using merge sort logic, the algorithm is
same as merge sort, only change is in the merge step where i am
counting the inversion_count.
I tested some test cases and I am getting correct answer, but I am
getting WA on spoj. Is the code incorrect or any test case whr it fails?
http://www.spoj.pl/problems/INVCNT/
#include<iostream>
using namespace std;
long inversion_count = 0;
void merge(long arr[], long p, long q, long r)
{
long n1 = q-p+1;
long n2 = r-q;
long L[n1];
long R[n2];
for(long i=0;i<n1;i++)
{
L[i]=arr[p+i];
}
L[n1]=99999999;
for(long i=0;i<n2;i++)
{
R[i]=arr[q+1+i];
}
R[n2]=9999999;
long i=0;
long j=0;
long k=p;
while(k<=r)
{
if(L[i]<=R[j])
{
arr[k]=L[i];
i++;
k++;
}
else if(L[i]>R[j])
{
arr[k]=R[j];
j++;
k++;
inversion_count+=n1-i;
}
}
}
void merge_sort(long arr[], long p, long r)
{
if(p<r)
{
long q = (p+r)/2;
merge_sort(arr,p,q);
merge_sort(arr,q+1,r);
merge(arr,p,q,r);
}
}
int main()
{
int t;
char a;
long n,i;
long arr[200002];
scanf("%d",&t);
while(t--)
{
scanf("%ld",&n);
for(i=0;i<n;i++)
scanf("%ld",&arr[i]);
merge_sort(arr,0,n-1);
cout<<inversion_count<<"\n";
inversion_count=0;
}
return 0;
}
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
