MLCHEF - Editorial

@arnabbcs08 Checked my code again and again still not able to find out any bug. Can you give me a random i/p on which this input fails .

Your program fails on input

100000

(nothing else needs to be in input), http://ideone.com/OMMM81

1 Like

I have taken a random input generator and tested several times by getting no error in the output. So,point to the part where my implementation is exceeding the expected time complexity.

your code seems wrong.


	if (x < segment_tree[idx].minHealth)
	{
		segment_tree[idx].minHealth -= x;
		segment_tree[idx].toBeSubtracted += x;
		return;
	}

does not first check if (ss,se) lies completely inside (qs, qe). You cannot do the above for arbitrary nodes :slight_smile:

You made a very careless mistake. Your inifinity was 10^8 and not 10^9. Changing that gets your code accepted :slight_smile: http://www.codechef.com/viewsolution/2684631

2 Likes

Link is not broken, please recheck.

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++
}

1 Like

Very nice solution. Thank you very much for sharing.

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…

So low? This code is trying to allocate about 75GB!

5 Likes
  1. Read about the part where the tree is first converted into a list.
  2. the parameter ‘health-of-least-healthy-chef’ helps me figure out in O(1) time if any child of a given node is dead, so I can remove dead chefs in O(log n) time per death.

Yes alex_2008, u r right…!! I figured this out later…