May 2011 Contest Problem Editorials

PRUNING (written by Zac Friggstad)

This can be solved with dynamic programming. Let w(u,v) denote the weight of the edge between u and v. Root the tree at an arbitrary node r. For nodes v,c within distance d of each other, let m(v,c) denote the maximum total weight of edges in the subtree rooted at v among all solutions that have c being the center of the component containing v. Then m(v,c) satisfies the following recurrence. To simplify notation, let k(u) denote the maximum over all m(u,c) where c ranges over nodes in the subtree rooted at u whose distance to u is at most d (i.e. not considering possible centers c that are not included in the subtree rooted at u).

- if v is a leaf, then m(v,c) = 0

- if v is not a leaf and either c = v or the path from v to c goes through the parent of v, then m(v,c) is the sum, over all children u of v, of the quantities

1) max(k(u), m(u,c) + w(u,v)) if the distance from u to c is at most d

2) k(u) if the distance from u to c exceeds d

- if v is not a leaf and c is in a subtree rooted at some child u' of v, then m(v,c) is the sum of w(u',v) + m(u', c) plus the sum, overall children u != u' of v, of the quantities listed in the previous point.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

HARMONY (written by Zac Friggstad)

Given an assignment of 0/1 values to edges of the graph, let w(C) be the number of edges on a cycle C that are assigned a 1 and let f(C) be the number of faces contained in C. Say that a cycle C is harmonious if w(C) = f(C) mod 2. If C is a cycle that bounds a single face, then f(C) = 1 so a necessary condition for all cycles being harmonious is that w(C) is odd for every cycle C that bounds a single face.

One of the main observations in this question is that this is also sufficient. Consider a cycle C and say it contains k = f(C) faces F_1, …, F_k. Let C_1, …, C_k denote the cycles that bound the respective faces. Then w(C) = W(C_1) + … + W(C_k) (mod 2) because every edge on C is counted only once and every edge contained in the region bounded by C is counted twice in the sum (once for each of the faces F_i, F_j that include the edge on C_i, C_j). Because the graph is has no bridges, then there is no edge that has the same face touching both sides. We have W(C_1) = … = W(C_k) = 1 (mod 2) since each C_i is the cycle bounding a single face so then w(C) = k = f(C) (mod 2), which is what we wanted to show.

If n was smaller, then we could simply set up a system of linear equations mod 2 where we have variables for the edges an one equation for each interior face and solve this using Gaussian elimination. However, n can be much larger so a better algorithm is needed. First, find any spanning tree T of the graph. Consider the "dual complement" of T. This is a graph T' whose nodes correspond to faces in the drawing of G (including the unbounded face) and two nodes in T' are adjacent if their corresponding faces in the drawing of G share a common edge that is not in the tree T. Let r be the node in T' that corresponds to the unbounded face of the drawing of G.

Now, T' is also connected and acyclic. The intuitive idea behind this is that if T' is not connected then faces in the drawing of G that are not in the same component as r in T' are separated from the other faces by a cycle whose edges are in T, which contradicts the fact that T is acyclic. Also, if T' has a cycle then we can draw a closed curve in the plane that stays entirely contained in the faces corresponding to such a cycle and passes only through edges that are not in T. But then these edges form a cut of G which contradicts the fact that any cut of a connected graph must contain at least one edge of any particular spanning tree.

To exploit this, assign arbitrary values to the edges in T (e.g. 0 for each such edge) and root T' at r. A leaf node x (excluding r if r has degree 1 in T') corresponds to a face in the drawing of G for which exactly one edge on the boundary has not been assigned a value. So, pick any such leaf x and assign whatever value is needed to have the corresponding face f(C) odd where C is the bounding cycle of this face. Then remove x from T' and recurse until T' consists of only the root r, in which case we are done. With care, this can be implemented to run in O(n log n) time.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

BICKER (written by Zac Friggstad)

This is an NP-hard problem more commonly known as sparsest cut. One observation is that in each test case it is always possible to find an answer with value 2 according to the scoring mechanism. This follows from the observation that we can always cut at least 1/2 of the total d-values through a simple greedy algorithm. Process the nodes one at a time and, at each step, we can either place the current node in S or in T. Choose the one that separates the most d-value among the edges from v to nodes appearing in S or T; at least half of the d-value of these edges is then separated. Since each edge is "introduced" once and at least half of the d-value is separated at each step, then at least half of the total d-value is cut. This is a good starting point for a heuristic, but it completely ignores the q-values. There are examples (with optimum score close to 0) where this heuristic performs very poorly.

In general, the best approximation algorithm is O(sqrt(log n) * loglog n) [1]. If all d-values are 1 (i.e. d(u,v) = 1 for all u != v in V) then there is a slightly better O(sqrt(log n)) [2]approximation. However, they both require techniques from "semidefinite programming", a generalization of linear programming. More practically, there are linear programming based O(log n) approximations that are quite easy to implement given an LP solver [3,4].

1) S. Arora, J.R. Lee, and A. Naor, Euclidean distortion and the sparsest cut. Journal of the American Mathematical Society, 21:1-21, 2008.

2) S. Arora, S. Rao, and U. Vazirani, Geometry, flows, and graph-partitioning algorithms. Communications of the ACM, 51:96-105, 2008.

3) T. Leighton and S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to  approximation algorithms. In proceedings of IEEE Foundations of Computing Science, 422-431, 1988.

4) N. Linial, E. London, and Y. Rabinovich, The geometry of graphs and some of its algorithm applications. Combinatorica, 15:215-245, 1995.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

TPRODUCT (written by AnhDQ)

The statement has directly shown the way to solve (by formulas) the problem, but it is not very easy to do since the result could be a very  large number. It is hardly to use big-number calculating to fit the given time-limit. The problem needs only the result by modulo of 1,000,000,007 but we can not compare the numbers by their remainders.

Fortunately we have an effective way to solve it by combining some mathematical theories as follows:

- At first, we can store the value of P_i by storing its logarithm instead;

- Then instead of doing a lot of multiplications (which causes very large results), we just do a series of additions between their logarithms (which are quite small real numbers);

- At last, we do tracing and calculate the needed result by modulo of 1,000,000,007; this work does not need big-number processing since we can take the remainders after every multiplication.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

PRDIVSUM (written by Anton Lunyov)

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

BWALL (written by Snigdha Chandan)

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------