Problem Link:
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[i] ≤ 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[i] = 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[i]
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:
- 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
