@Terence: I dont know what a guard value error is, but by mistake I wrote R[n2] = 9999999, should be one more 9 since array value can be <=10^7. May be test cases have values less than 9999999 that got me AC.
On Thu, May 12, 2011 at 5:20 PM, Terence <technic....@gmail.com> wrote: > 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. > > -- 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.
