PROBLEM LINK
DIFFICULTY
hard
PREREQUISITES
dp, transforming dp state parameters to optimize dp solution
PROBLEM
You are given a rooted tree consisting of n nodes. For each non-leaf node, you are required to mark exactly one of the its edge to some child heavy, and all the remaining ones should be marked light.
Consider a path from root to leaf node. We can decompose it into maximal sequence of segments such that each segment is of same marking (either heavy or light). Cost of a heavy segment of length L is \lceil \log{L} \rceil + 1, and that of light segment is L.
Let us define cost of the tree by the maximum cost path from the root to a leaf. You have to assign the heavy and light edges in such a way that the cost of the tree is minimized.
SOLUTION:
It is always a good idea to try to understand the problem statement by trying simple cases of trees. For example, if the tree is just a line, i.e. i is connected to i+1 for each i < N and node 1 is the root. In this case, we have no choice other than marking all the edges heavy. The cost of the tree will be \lceil \log{(N - 1)} \rceil + 1.
Assume we have a star tree with root node being 1. Only one edge of the tree will be marked as heavy, rest should be marked light. The cost of path from root to any leaf will be 1. So, the minimum possible cost of the tree is 1.
Write simplest possible dp formulation
It is always a good idea to think about dynamic programming solutions for tree problems. The structure of tree usually yields nice dp solutions. Simplest dp formulation that we can have for a node u is as follows.
Let g(u) denote the answer for the subtree rooted at u, i.e. the minimum cost of the subtree rooted at node u we can get by marking its edges heavy or light. Then, the answer to our original problem will be g(1). Let us try to define the function g recursively.
If u is a leaf node, then g(u) = 0.
If u has just a single child node which is a leaf, then g(u) = 1, as we will have to make that edge connecting u and its child as heavy node, and it will cost 1.
Now remains the case when u has more than one child. We need to which edge should be made heavy? We should pick the child w with highest g value, and try to make edge u, w heavy, so as to reduce overall cost of our subtree rooted at u. All the other edges will be light. This is because the light edge will always incur a cost of 1, but adding a heavy edge may or may not. See the next paragraph for details.
g[u] = max(g[v] + 1) over v \neq w. As, for all children v of u (such that v \neq w), we should have the cost of subtree rooted at u at least g[v] + 1.
What should be the contribution of node w and the added heavy edge (between u and w) in the cost of u? The most important observation is to realize is that it might be possible that adding this heavy edge might not incur/increase the cost at all. This can happen because cost addition due to adding heavy edge doesn’t increase linearly but increases logarithmically (which is discontinuous over integers), so it could potentially remain the same on addition of some heavy edges. For example, consider a line tree which has 5 vertices: 1, 2, 3, 4 and 5 connected in that order. The value of g(2) = \lceil \log{3} \rceil + 1 = 3. The value of g(1) is \lceil \log{4} \rceil + 1, which is also 3. In fact, you can easily see that for a line tree, the g values will be at most \log(n), so they will potentially remain same for quite a few instances while adding a heavy node.
So, g[u] = \max(g[u], g[w] + \delta) where \delta can be either zero or one, depending on whether it is possible to add an edge between w and its parent without incurring any cost. Let f(u) denote the minimum cost of the subtree rooted at u such that you can add a parent edge at vertex u. Note that the cost of adding the parent edge is incorporated in f(u).
Now, we must find a recurrence for function f. We add a heavy edge between vertex u and w where w is a child of u with highest g value. So, f value for u will be the the g(w) + \delta', where \delta could potentially be 0, 1 or 2 (as it means that we are adding two edges from w, one from w to u, and another from u to its parent). Now we should know how to find the cost of node w where you can add two parents too. If we go into the children of w, this will require us to find the cost when you can add three parents and so on. This forces us to think of a more general dp state, i.e. f(u, k) denoting the cost of the subtree rooted at u, along with k parent edges above u.
The first term f(w, k + 1) corresponds to the case where we are adding a heavy edge between u and w. So the cost due to it will correspond to minimum cost that can be achieved at w while adding k + 1 parent edges, i.e. f(w, k + 1).
The second term corresponds to the minimum possible cost for all other vertices v \neq w, where we are adding a light edge. Notice that addition of a light edge will always contribute of cost 1. Now, adding k parents edges on u will cost you minimum \lceil log(k) \rceil + 1 (i.e. make all these edges heavy).
Direct implementation of this approach will take \mathcal{O}(n^2) time, which will only be able to solve first subtask.
Optimize the solution
You can notice that f(u, k) will increase when you increase value of k from 0 to n. This is simple because more edges you add, more cost you will need to pay. Also notice that f(u, k) can take at most \log{n} different values, because you can always make these k parent edges heavy edges and make their cost go up by \lceil log(k) \rceil + 1. This suggests that we might not need to maintain values of f(u, k) for each k, instead we can store the values of f as a collection of points where value of f(u, k) changes. i.e. store the set of values of k's such that f(u, k) \neq f(u, k - 1).
We want to find minimum cost for f(u, k). The range of values of f is limited, we proved that it can contain at max \mathcal{O}(\log{n}) values. In such cases, it is a good idea to switch the parameters. Is it possible to make cost, a parameter of the dp? Let us define a function h(u, c) that will denote the maximum possible value of k that you can get such that cost remains within c. This helps in optimizing the time complexity of the dp program as the number of c's are very small.
Formally, let h(u, max_{cost}) denote the maximum number of parents that you can attach above node u such that maximum cost you are allowed to incur is max_{cost}.
def h(u, max_cost):
diff = max_cost - g[u] // we can spare this much cost at node u.
if diff < 0:
return -1; // impossible situation.
if diff > 18:
return 1<<18; // You can attach around 1<<18 nodes.
if u doesn't have a child.
if diff == 0:
return 0; // You can't add any edge
else:
return 1 << diff;
// Find the child w with highest value of g.
// You can add at max h(w, max_cost) - 1 parent edges.
ans = h(w, max_cost) - 1
mx = 0;
for v in child(u) such that v != w:
mx = max(mx, g[v] + 1);
rem = max_cost - mx; // How many parent edges you can add in this cost?
ans = min(ans, rem == 0? 0 : (1 << min(rem, 18));
return ans;
As you can notice that value of diff in the pseudo code won’t go more than 18 (i.e. \log{n} for n = 10^5). Overall time complexity of this algorithm will be \mathcal{O} (n \log{n}).
Takeway point
Some formulation of dp are not easier to optimize, try switching the parameters. If the formulation of dp is yes, no type question, you can try to convert it into a min/max kind of formulation.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Will be uploaded soon.
.png)