@Topojoy Biswas:
If A = [3, 1, 5, 2, 4] then CT (A) is:
1
/ \
3 2
/ \
54
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 t
@Terence:
I dont know what a guard value error is, but by mistake I wrote R[n2] =
999, should be one more 9 since array value can be <=10^7. May be test
cases have values less than 999 that got me AC.
On Thu, May 12, 2011 at 5:20 PM, Terence wrote:
> Guard value error.
>
>> L[n1]=999
Cartesian trees could also help.
Cartesian tree takes O(n) time to build, and if you have the count of how
many nodes are there in a tree rooted at any node, by just having the index
of the element also stored there. Once the cartesian tree is built, just
traverse from the root and find how many
Guard value error.
L[n1]=;
R[n2]=999;
R[n2] may be merged and counted, if L[1..n1-1] has 999.
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
count
When I replaced cout with printf in my code, I got AC!! I Should have tried
it earlier itself..
On Fri, May 13, 2011 at 11:51 AM, anshu mishra wrote:
> no all these data structure also take time O(nlogn)
>
> solving this problem using segment tree
>
> map all elements to its index on the sorted a
no all these data structure also take time O(nlogn)
solving this problem using segment tree
map all elements to its index on the sorted array.
ex. 2 3 8 6 1 --> 1 2 4 3 0
intialiize all element in segment tree wid zero
start from the last index of array
whenever u visit a node increase its va
@Anshu:
My logic:
during merge step, lets say you have two array left and right (both are
sorted) and you are going to merge it.
l[i] represent the element of left arrray
r[j] represent the element of right array
if (r[j] < l[i]) {
increase the inversion count by the number of elements lefts in
explain your logic instead of posting code, use binary index tree or segment
tree or bst to solve this problem.
--
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 fr
