L56avg - editorial

PROBLEM LINK:

Practice
Contest

Setter: Kirill Gulin
Tester: Misha Chorniy
Editorialist: Taranpreet Singh

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Binary Search, dynamic programming on trees.

PROBLEM:

Given a tree with N nodes, a value associated with each node. We are required to find the maximum cost among all possible correct decomposition of tree.

Correct Decomposition of a tree is defined as break down of tree into mutually disjoint set of paths. Path may also consist of a single node.

Cost of a correct Decomposition is given by the minimum among cost of all paths of decomposition, the cost of each path being the average of all values of nodes in given path.

We are just required to find the Maximum cost, not the decomposition.

QUICK EXPLANATION

  • Calculating average and handling comparison of average of two paths with different number of nodes is complicated.
  • We can binary search on answer, subtract from initial values the answer and reduce the problem into breaking the tree into paths each with sum>=0.
  • Here, We can use dp on tree to check if we can decompose tree into a set of path with all the paths having sum greater or equal to zero.

EXPLANATION

Reducing Averages to sum of paths

Averages are not good. We can check if average of a set A of size S is greater or equal than x, if

\begin{equation}
{\textstyle \sum} A_i - x*S >= 0
\end{equation}

For each binary search, we Make a new array T_i = A_i - x thus, reducing the above inequality to

\begin{equation}
{\textstyle \sum}T_i >= 0
\end{equation}

Now, it suffices to check if we can decompose the given tree into a set of paths with each path sum >= 0.

Dynamic Programming on Trees

Now, for each value of X, we need to check if decomposition is possible. We have to handle three situations:

  • Path starting in sub-tree of node u and moving towards its parent.      
    ![alt text][16]
    
  • Path starting in sub-tree of node u and ending in sub-tree of node u, such that LCA of start node and end node of path is u.  
    ![alt text][17]
    

Now, we have two states for each node - Either node u can be connected to its parent, if required, or not.

So, for each node, we need to maintain two values, let denote dp[u][0] storing path sum such that u is not available, and dp[u][1] such that node u is available.

So, we assume we have solved the problem for all children of Node u and try to solve it for current node. The base case for dp recurrence would be leaf nodes for which both dp[u][0] = dp[u][1] = T[u].

Run a dfs with any arbitrary node as root, and recursively solve the problem for each node, as follows:

Create an empty list and for every Child c, we check if dp[c][0]<0, implying we cannot leave this node in this state for a correct decomposition, and add it to the list.

Now, If count denote the size of list, Four cases arise:

  1. Size == 0: This means we can even leave the nodes as it is, A likely mistake, when the correct treatment is to connect this node with the child having dp[u][1] = T[u] + max(0, dp[c1][1]) and dp[u][0] = T[u] + max(0, dp[c1][1]) + max(0, dp[c2][1]), c1 being the child with maximum dp[c1][1] and c2 being the second best child of u, excluding the nodes included in list. For reason behind this, try decomposing following tree for path sum >=0.
    4
    -5 1 4 2
    1 2
    2 3
    2 4
    You’ll see that at node 2, all its children have dp[u][0]>=0. If we don’t connect node 2 with 3, we will have problem getting path sum >=0 for node 1.

  2. Size == 1: In this case, dp[u][1] = T[u] + dp[c][1] and dp[u][0] = T[u] + dp[c][1] + max(0, dp[i][1]), i!=c, i being child of u, not being in list.
    Reason: Now, we have only one child with path sum < 0. We connect it with u and get above values. For dp[u][0] we further connect it with the best child of u, to see if we can make a path of type 2 at node u. If dp[u][0] >= 0, it would be left automatically while processing u’s parent. Else, it will be added to list.

  3. Size == 2: In this case, set dp[u][1] = MIN as we cannot in any valid position, will be able to make node u available for connecting further. Now, the only option is to connect these two child through u and check if path sum >= 0. If dp[c1][1]+dp[c2][1] + T[u] < 0, then it is not possible to decompose tree into paths with sum>=0. else dp[u][0] = T[u] + d[c1][1] + dp[c2][1]

  4. Size > 2: In this case, we cannot decompose tree into paths with path sum >= 0.

Since we can terminate any path at node u, we should set d[u][0] = max(dp[u][0], dp[u][1].

We can maintain a global boolean to check if valid is not set false. Also remember to check that if dp[root][0] < 0, decomposition is not valid as type 1 path is not possible and type 2 path give path sum < 0.

Complexity:
Since each DFS take O(N) time, The final time complexity of solution is O(Nlog(max(A) - min(A))), where min(A) and max(A) are the maximum value in given array, the bounds of binary search.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution
Editorialist’s solution

what does it mean when we say u is available or not?

let denote dp[u][0] storing path sum such that u is not available, and dp[u][1] such that node u is not available. Can someone explain this statement ?

for those who scared with dp (like me lol !) :

Now, just need to find a way to decompose the tree for a given average efficiently i.e. in O(N) !

First finding averages is little tedious so, let’s convert it to finding sum i.e. given a particular ‘x’ we have to find whether the decomposed path has values(averages) <= x. So, intuitively it denotes that each path has the value ‘x’ and which in turn means that each node in the path has the value ‘x’ . Now, here is a trick "Every node has a value ‘x’ atleast So, if we subtract ‘x’ from each node and then if we sum up the nodes in the path then we must get value >= 0 and that’s it ! We have now the problem reduced to : Given a tree with each node a value(val[j] - x), we have to decompose it such that path have sum >= 0 ! (concept of original editorial thanks to @taran_1407)

Now, we will focus to solve the reduced problem : For this what we can do? First think that the nodes with values >= 0 are themselves stable (as they can be exist separately). And they have the power to stabilize other nodes. Now, suppose we have something (what is this something…we try to find now) for all the children below the curr_root and we have to stabilize the children (if any one of them is not stable (i.e path sum < 0)). Now, think about how many maximum children you can stabilize? Atmost 2 because stabilizing any one of the child requires that the path has to go to root and it is required that every node is present in exactly one path ! So, at max what you can do take two negative children and merge them with root (if it works then OK otherwise it’s simply impossible). So, if more than two children have values < 0 then it’s simply impossible.

Now, if exactly two children have value less than 0 : we know that in this case we have exactly one possible way out !
If cnt (count of number of negative valued children) == 1 : then we have to take this path and combine it with root and remember we first try to fix it here only (if not possible at all than only we propagate minimal negative value to be handled by upper roots). So, we take the root (val[root] + val[child]) If this sum is itself > 0 then we can see that it can help in stabilizing upper nodes. So, instead of closing the path in the subtree of root we propagate the value to upper levels ! Now, if this is < 0 : can we just pass it to upper level in hope that they will fix it? NO : remember we have to minimize the load for upper levels. So, we first try to fix it in this level itself i.e. in the subtree of the root. For this what is the best possible we can get ? : take another children with maximum positive value. If it fixes the unstable child then OK else we have no chance to fix it here and so, have to propagate to upper levels (in the hope that they will make a try to fix it !)

Now final case, cnt == 0 : in this case we don’t have to fix any children they are well stabilized and so we can simply pass the value to upper level to help them in stabilizing others ! But wait we are not thinking of the situation when the curr_root is itself negative ! : In this case we have two possibilities : first, combining it with the maximum child will fix it and in this case we simply pass it to upper level for help (as we can’t do better than this !). Now, if it won’t fix the root : What to do? same approach first try to reduce the load to upper layers and if completely impossible to fix at this level then and only then pass it to upper layers. So, how to fix in this level itself? : we find the second largest child and combine second largest and first largest through root and if it does our work then awesome else just pass the (max_child + val[curr_root]) (minimal value to fix) to upper level in hope that they will fix it !

3 Likes

sorry forgot to add base cases : For leaf nodes it is just val[curr_node] !

For the first time i have written something please forgive me for my bad english!

And if anyone found some counter case then please share !

A node in a path may be connected to one or two other nodes.

A node is available, when it is connected to 0 or one other node. A node is not available, if it is connected to two other nodes.

1 Like

A node in a path may be connected to one or two other nodes.

A node is available, when it is connected to 0 or one other node. A node is not available, if it is connected to two other nodes.

1 Like

Link to your AC code with your idea ?

@pk301 “Atmost 2 because stabilizing any one of the child requires that the path has to go to root and it is required that every node is present in exactly one path” I didn’t understand this point ? Why atmost 2 ? Or am I missing the definition of path ?

A path is defined as the simple path between two vertices u and v.

It is understood that in this path, node u and node v will be connected to exactly one other node, and all other nodes are connected to exactly 2 other nodes. Path specifically included by this problem in problem statement is path of length 1, consisting of single node.

This way, in no scenario, will a node in a path be connected to more than 2 nodes. So, if more than 2 nodes need to be connected, ans become impossible.

2 Likes