PROBLEM LINK:
Author: A Surya Kiran
Tester: Shiplu Hawlader and Mahbubul Hasan
Editorialist: Lalit Kundu
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Segment trees
BIT
DFS, BFS, Graphs
PROBLEM:
Given a rooted tree, each of whose node is associated with an integer, “wealth”. You have to perform two operations:
* A,X ie. decrease “wealth” of all nodes B by, by X/2d where d is distance between the node B and node A.
* Report number of descendants of a given node with non-positive “wealth” (further referred to as “dead” in editorial).
EXPLANATION:
Someone said in a previous editorial:
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.
Here, if we do a BFS on the tree, all the immediate children of node are numbered consecutively. We can use this to our advantage, but a bomb dropped on a node A effects all nodes in the tree according to distance.
Intuition here would be define a new kind of bomb, say NBomb, which when dropped on node A effects all it’s descedants according to the distance from node. Also, it should effects A’s parent by X/2. But now, since A is immediate child of it’s parent, it would be effected more than X. To normalise that, we drop a NBomb of -(X/4) on A.
So, we drop two NBombs on A, one whose power is X and the other whose power is -(X/4) and an NBomb of power (X/2) on parent of A.
For dropping a NBomb on A, at every step we go down the tree level by level and damage cities in every level until 2d>X. How we do this is by keeping for each node the leftest and rightest nodes. So, if we update an interval [i,j] by T, we will update [leftest[i],rightest[j]] by T/2.
So each query of type one is broken down in logX*logX queries, where each query is updating in a subarray(in the array we build after performing a BFS on the tree).
Now, we can have two approaches to solve this problem:
i.) Offline solution
ii.) Online solution
Offline solution:
Let’s keep, for each query a time t, according to the sequence they arrived in input.
The approach here is to find for each node, the time of death. Once we get time of death for each node, it’s very simple to find the answer for query two. Let’s just say, we have times of death for now.
We have query of type two, which asks for number of descendants of a node which are dead at time=t. Again, we map the tree to an array using DFS, where all descendants of a node lie in one subarray.
We traverse over time now and keep on marking in BIT those indexes which have died before that time. For a query of type two, we just have to print the number of marked elements in L to R inclusive.
set BIT <- 0
for t=1 to Q:
for each node whose death time=t:
update(BIT,t,1)
for query of type-two at time=t
print read(BIT,R)-read(BIT,L-1)
Now, we come to the part of finding the death times. Again, a very classic approach called binary search comes into play here :).
For each node, I suppose that it died at time T. If it is dead at time T, it will be dead at time T+1 too. So, we can use binary search here, as it’s a non increasing function.
So:
def get_death_time(node n):
if sum of decrement queries till Q < wealth[n]:
return INF // didn't die till the end
low=1
high=Q
while(low < high)
t1 = (low + high)/2
if (wealth[n] <= getDecSum(t1)) //get sum of all decrement queries performed upto time t1 that effect node n
high = t1 // node is dead at time t1
else
low = t1+1 // node is not dead at t1
return low
However, we still have to get hold of all operations that effect node n, 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:
set BIT <- 0
for i=1 to N:
for each query of type1 ie. (dec,i,r) at time t: \\ that is, l=i
update(BIT,t,dec)
death[i]=get_death_time(i)
// This part can also be calculated in O(1) by reading
// the actual frequency at a position in BIT. See topcoder tutorial.
for each query of type1 ie. (dec,l,i) at time t: \\ that is, r=i
update(BIT,t,-dec)
Hence, we get death times of all nodes.
Online solution:
In, online solution, you update all subarrays that need to be updated due to query of type1. And, then it figures out all the dead nodes in the tree. So, the only difference here, is that while updating the damages, we find the nodes which have died and update them in our BIT. And similar to offline solution, we can print using BIT, the number of dead nodes at any time.
I don’t think I can do any better than this editorial by Utkarsh Lath. So, I am taking the segment tree lazy propagation part from this editorial.
To efficiently decrease all values in a subarray, we would need lazy propagation. Also, to efficiently determine nodes 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-wealthy-node__, __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-wealthy-node 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-nodes(int root)
if tree[root].health-of-least-wealthy-node > 0
return // no dead node below me
if is-leaf(root)
set __alive-count__ of root to 0, __health-of-least-wealthy-node__ to infinity
else
propagate the value of __decrement__ to both children, set __decrement__ of root to 0
remove-dead-nodes(root * 2); // some dead chef exists and needs to be removed
remove-dead-nodes(root * 2+1); // so check both children
update __health-of-least-wealthy-node__ and __alive-count__ parameters of root
Query and update operations are very standard.
AUTHOR’S AND TESTER’S SOLUTIONS:
To be updated soon.
