Internet Problem Solving Contest

IPSC 2001

Solution to Problem D – Urvi Komu Urvi

This was supposed to be one of the hard problems in the contest, and, indeed, it was. The easy input could be solved by branch and bound (backtracking) techniques, but for the difficult one heavy machinery of dynamic programming was needed.

We can solve this problem by dynamic programming. We will proceed from the leaves of the tree up to the root. Consider a tree T rooted at a vertex vT. Let

If T consists of a single vertex, clearly pT[0] = 0 and pT[k] is undefined for k>0.

Now consider two trees: T with root v and S with root u. Suppose we have already computed the arrays pT[] and pS[]. We will create a new tree W out of S and T by attaching the vertex u, as a child of v. Clearly, using this operation one can build an arbitrary tree out of isolated vertices. Let's see how can we compute the array pW[].

Consider the value pW[k]. To get exactly k vertices of W be in a different team than v, it must be the case that i vertices from T and k-i vertices from S are not in team with v for some 0 ≤ i ≤ k. There are two possibilities: either u and v are in the same team, or they are not. In the first case, the amount of tension relieved is pT[i] + pS[k-i].

If u and v are in different teams, we want exactly k-i vertices of S to be in the same team as u or, put another way, nS - (k-i) vertices of S to be in different team than u. In this case, the tension of u is also relieved by tu and the total amount of tension in W is pT[i] + pS[nS -k+i] + tu.

Thus the optimal value of pW[k] is the maximum of pT[i] + pS[k-i] and pT[i] + pS[nS -k+i] + tu over all i such that pT[i] and pS[k-i]   (pS[nS -k+i] respectively) is defined.

To compute pT[] for a subtree T rooted at some vertex v, we first recursively compute the arrays pS[] for all trees S such that S is a subtree rooted at a vertex u, vhich is a child of v. Then, using the relation derived above, we add children of v one at a time and each time recompute p[] for the tree currently hanging from v.

In the end, the value of the optimal solution can be just read off from pT[N/2], where T is the whole tree and N is the number of vertices. To get the actual division of vertices into teams, one has to trace back through the pT[] arrays.