@Topojoy Biswas:
If A = [3, 1, 5, 2, 4] then CT (A) is:
1
/ \
3 2
/ \
5 4
counting the number of nodes in the tree rooted at each node,
1(5)
/ \
3(1) 2(3)
/ \
5(1) 4(1)
where the numbers in () denotes the number of nodes in tree rooted at that
node.
"Once the cartesian tree is built, just traverse from the root and find how
many nodes are there in the left subtree from its left child node, and that
is the number of inversions for the root node"
Now, the number of inversions for each node according to you is:
1 -> 1
3 -> 0
2 -> 1
5 -> 0
4 -> 0
so in total, 2 inversion pairs. But thats not correct. Correct me if I am
wrong.
On Sat, May 14, 2011 at 11:19 AM, Akshata Sharma
<akshatasharm...@gmail.com>wrote:
> @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.
