MLCHEF - Editorial

data-structure
editorial
medium
mlchef
segment-trees
sept13

#1

Problem Link:

Practice

Contest

Difficulty:

Medium

Pre-requisites:

Segment Trees, BIT

Problem:

Given a rooted tree, each of whose node is associated with an integer, “health”. You have to perform two operations:

  • decrease “health” of all descendants of a node by a given quantity.
  • Report number of descendants of a given node with positive “health”.

Explanation:

Trees are hard to think about. In many tree problems involving data structures, the first step is to form one(or several) linear structures, and phrase the problem in terms of these linear structures.

In the present problem, we need to perform some operation/query on all descendants of a node together.

When dealing with a rooted tree data-structure problem where operations/queries are made on all descendants of tree nodes, the tree can be linearised by writing the vertices down in the order given by pre-order traversal of the tree.

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. The new problem becomes:

Given an array of integers("health"s of nodes), perform the following two operations:

  • decrease the value of all elements in a given subarray by a given number.
  • report the number of positive elements in a given subarray.

There are mainly two intuitive approaches to this problem:
i) An offline solution in O(N log^2 Q + Q log Q) time,
ii) An online in O((Q + N)log N ) time.

Originally the Setter had only the offline solution in mind until others came up with an online one. For futher discussion, assume each decrement operation is given by four parameters (time, dec, l, r), where time is index of the operation(can be 1, 2, … Q), l,r give the subarray(l, r inclusive) which should be decreased by dec. Also assume that each query is represented as (time, l, r), meaning of terms being similar.

Offline solution

Lets first assume that all chefs die, by adding one more operation in the end which decreases the health of all chefs by 109. Suppose that I want to find out the death time of a single chef, chef A.

The most intuitive way to go about would be to write down all the decrement operations that effect chef A, along with the point of time at which they occur. Now, add decrement value of all those operations in chronological order until it exceeds the health of chef A. Thus I would get the time at which he died.

The method can be speeded up with binary search. That means, I would predict a point of time t1 and try to find if chef A was alive at time t1, by summing up all decrement operation before time t1. To sum up all decrement values upto a given point of time efficiently, a Binary Indexed Tree(BIT) can be used. Thus, we could find out the time at which a given chef dies in O(log2 Q) time, assuming we have build the BIT for storing all operations that effect this chef.

function get-time-of-death(int i): // index of chef
low = 1
high = Q
while(low < high)
t1 = (low + high)/2
if (healthOfChef* ≤ getDecSum(t1)) // get sum of all decrements performed upto time t1
high = t1 // I am dead at time t1
else
low = t1+1 // I am alive at t1
return low

However, we still have to get hold of all operations that effect chef A, and use them to construct our BIT. To do this efficiently, we can use the fact that all operations affect some continuous subarray of our array. If Chef A comes immediately after chef B on the array, the operations that effect chef A are going to be almost same as those that effect chef B. Only those operations whose range either ends at B, or begins at A have to be taken care of. Rest of the operations are going to be common. Here is a pseudo code showing how to accomplish this

BIT <- empty // stores no operation
for i = 1 to N
for each operation (time, dec, l, r) whose range (l,r) starts at i // that is, l=i
update-BIT(time, dec)
death-time* = get-time-of-death(i)
for each operation (time, dec, l, r) whose range (l,r) end at i // that is, r=i
update-BIT(time, -dec)

Great ! I got the time-of-death of all chefs. How do I go about answering all queries now ?
At this point, one can use ideas from a previous editorial (offline processing section) to completely solve the remaining part. However, I will reiterate the points here.

In current setting, all queries ask for number of alive chefs in a subarray at a given point of time. Suppose, for now, all queries asked for number of alive chefs in the entire array at any given point of time. This would be easy to do, because for all points of time we could store the number of chefs who died at that point of time. To answer a query at time t, we can sum up number of chefs died upto time t. Another BIT can be used to speed up this part.

Also, If I want to add one more chef to my array, who dies at time t1, it can be done easily by updating the BIT. I will borrow the following general tip from a previous editorial.

If a problem can be solved efficiently for an array, and more elements can be also be added to the array efficiently, without hurting the ability to solve the problem efficiently, then the problem can also be solved (offline) for arbitrary prefixes(or suffixes) of the array.

We can use the above to find the number of dead chefs at time t in arbitrary prefixes of the array. But this would be sufficient to answer queries about arbitrary subarrays as well, because any query can be written down as two prefix queries: query(time, l, r) = prefix-query(time, r) - prefix-query(time, l-1). That means to report number of chefs alive at time time in the subarray given by (l,r), find the number of alive chefs in the prefix ending at r at time time, and number of alive chefs in the prefix ending at l-1 at time time.

To find number of alive chefs in arbitrary prefixes:

sort all queries (time, i) in increasing order of i.
Initialize a BIT, will all zeros
for i = 1 to N
update BIT with death-time*
for all queries of the form (time, i):
report answer of query = BITquery(time)

Refer to setter’s solution for further etails on implementation.

Online Solution

Online solution goes exactly how you would expect it to. For each update, it first decreases all values in the subarray, and then figures out which Chefs have died because of this update. It also maintains all alive chefs in order to answer all queries. A single segment tree can be used to solve this problem.

To efficiently decrease all values in a subarray, we would need lazy propagation. Also, to efficiently determine chefs who have died due to an update, each node(of our segment tree) should store the descendant leaf of minimum health(this leaf will be the first to die if all descendants are poisoned). The overall structure of a node of our segtree is:

struct node {
int health-of-least-healthy-chef, decrement , alive-count;
// Actual health of a leaf(in segtree) can obtained by subtracting decrement value of all its ancestors(in segtree).
// This is called lazy propagation.
}

A node can be updated by simply updating decrement and health-of-least-healthy-chef parameters. decrement would need to be propagated down before updating any node.
After performing a normal update, the following function can be used to remove dead chefs:

function remove-dead-chefs(int root) if tree[root].health-of-least-healthy-chef > 0 return // no dead chef below me if is-leaf(root) set __alive-count__ of root to 0, __health-of-least-healthy-chef__ to infinity else 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 update __health-of-least-healthy-chef__ and __alive-count__ parameters of root

Query and update operations are very standard. Refer Editorialist’s solution for details. The complexity of this method is O(N lof N + Q log N), because each update/query takes O(log N), and whenever a chef dies, O(log N) time to spent to figure out who has died and update the tree to reflect this.

Setter’s Solution:

Can be found here

Tester’s Solution:

  1. Mahbub’s

(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester1/MLCHEF.cpp)  
 2. Sergey's 

(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester2/MLCHEF.cpp)

Editorialist’s Solution:

Can be found here

Similar Problems:

To learn BIT:

To learn segment trees


#2

links to code are all missing.


#3

Can anyone check why the following code (online processing with segment tree and lazy propagation) gives TLE verdict?
http://www.codechef.com/viewsolution/2650556


#4

Can anyone expalin why this solution of mine yielded TLE (using segment tree and lazy propogation)
http://www.codechef.com/viewplaintext/2649148


#5

there is also O(N * sqrt(N) * log(sqrt(N))) solution with sqrt decomposition ,


[1]


  [1]: http://www.codechef.com/viewsolution/2603323

#6

In the offline solution, there’s a way to calculate the death time of a chef in O(log Q) time instead of O(log2 Q), by “aligning” the binary search with the BIT, so that getDecSum can be calculated in O(1) per step in the binary search.

This reduces the overall solution by a log factor.


#7

I havent used segment tree instead used 2 2d matrices , one matrix that links all the chefs to its supervisor and another matrix which links all the chef to to its inferiors. My program gives right o/p for my test cases but somehow I get a runtime error(NZEC), which is very annoying. Can anyone tell me what is the bug in my program…?? The link for my program is:
http://www.codechef.com/viewsolution/2674843


#8

Please upload Setters solution.
Link is broken


#9

Can someone please help me find why my solution is getting WA?

http://www.codechef.com/viewsolution/2684669


#10

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.


#11

@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 .


#12

@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.


#13

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?


#14

I have some doubts regarding the online solution.

  1. 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

  2. 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)


#15

@utkarsh_lath

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. :slight_smile:


#16

Feel aswesome after solving this problem and learn segment tree with lazy propogation for solving this problem.


#17

I’m so pissed off at myself when I knew for certain it’s a segment tree problem but I could not transform the tree structure to segment tree. Shame on me. Nice problem anyway.


#18

Solutions are being moved. Till then you can get them from

www.codechef.com/download/Solutions/2013/September/Editorialist/MLCHEF.cpp

Similarly transform other links.


#19

Very nice editorial. Thanks!


#20

Even if you are able to sort the time issue, there is a bug in your query. If a node encountered is flagged while querying u need to keep updating as you move down. However your query misses that part.