I know it’s silly but can anyone explain the part
"Pre-order traversal of the tree gives numbering to vertices such that all descendants of any internal node get consecutive numbers, and form a single range. This is because after visiting any vertex, dfs first visits all descendants of the vertex, and then all the remaining vertices.
Therefore, once we arrange vertices by their preorder traversal order, all descendants of any node become a subarray of this array. "
probably with an example.
@h1t35h : Consider the example
Nodes : a - g
Edges :
a - b
a - c
b - d
b - e
c - f
c - g
Dfs would give following numbers :
a - 1
b - 2
d - 3
e - 4
c - 5
f - 6
g - 7
So if you look at a node say ‘b’ for example , ‘b’ and its descendants form the range 2 to 4 . Similarly , ‘c’ and its descendants form the range 5 to 7 . ‘f’ and its descendants form the range 6 to 6 and ‘a’ and its descendants form the range 1-7 .
Because when DFS visits a node , it next visits the entire subtree rooted at that node and only then proceeds to visit anything else . Hence the entire subtree gets “NAMING” or “ORDERING” or “RANKING” as a single continuous RANGE .
@vineetpaliwal
I understood that sir, but what i wanted to know was that how did we limit those number of descendents.
For example, in your case how do we decide that the descendents vary from 2 to 4 for ‘b’ and that this would be the limit(because we can lets say its 2 to 5, all are consecutive numbers here also) I didn’t understand how do we decide the sub-array’s size.
I used Post-order: http://en.wikipedia.org/wiki/Tree_traversal
I think it’s similar.
The example on wiki gives order:
A, C, E, D, B, H, I, G, F
1, 2, 3, 4, 5, 6, 7, 8, 9
note that F is the root (e.g. chef 0). So from 1 to 8 will get all the chefs below chef F.
chef G (8) has chefs I & H below. So we get the interval 6-7 for chef G.
func order(node int) {
chefs[node].a = order_count
for _, child := range chefs[node].children {
order(child)
}
chefs[node].b = order_count - 1
chefs[node].order = order_count
order_count++
}
Very nice solution. Thank you very much for sharing.
I still cannot understand the analyse of the time complexities of the online methods, which is O(N lof N + Q log N) using segment tree.
As for the update operation in segment tree structure, we use the tree[root].health-of-least-healthy-chef to tell if we should continue to update the subtree to update the health value of those who died. I think this still needs to update too many nodes.
For all, I do not know how to analyse the time complexity when it comes to segment tree. Anyone helps?
I made some modifications in the pre-order traversal function. Basically it is just counting number of descendants of a root node. First find the number of descendants in the left subtree. then find those in the right subtree.if position of root is i, then subarray will be from i+1 to nodes in left subtree + nodes in right.
every chef dies at most once, so it will be O(log n) cost for each chef who dies, giving O(n log n).
Ok… Is the java heap space so low on the server…!! Its astonishing… Thanx by the way…
I have some doubts regarding the online solution.
Does every chef will have only 2 immediate subordinate chefs? because in this pseudocode you took 2 children only :-
propagate the value of decrement to both children, set decrement of root to 0 remove-dead-chefs(root * 2); // some dead chef exists and needs to be removed remove-dead-chefs (root * 2+1); // so check both children
How could you remove dead chef and lazy propagate in O(logn) time? You are visiting each each child once by dfs. Isn’t its complexity O(n)
So low? This code is trying to allocate about 75GB!
Yes alex_2008, u r right…!! I figured this out later…
I have been trying this question since a while now. I’ve implemented the code using a single segment tree but I’m still getting TLE. Here’s the link:
http://www.codechef.com/viewsolution/3148396
Can you please help me with this and just guide me as to where I’m going wrong? Thanks. 