April 2011 Contest Problem Editorials

L2GRAPH (written by Zac Friggstad)

This is a special instance of the "metric embedding" problem. Recall that a metric space is a collection of points with a distance function d(x,y) satisfying d(x,x) = 0, d(x,y) = d(y,x), and d(x,y) <= d(x,z) + d(z,y) for any points x,y,z in the metric. The shortest-paths-in-a-graph distance is a metric as is the Euclidean distance in any d-dimensional Euclidean space. A well-studied problem is how well we can embed one metric space in another. Here, an embedding from a metric X to a metric Y is simply a mapping of the points in X to the points in Y. The quantity L/K in the problem is called the "distortion" of the embedding.

An important result is that any metric on n points can be embedded in some Euclidean space of dimension d with distortion L/K where d*L/K = O(log^2 n). More specifically, one can obtain distortion O(log n) in O(log n)-dimensional space. There are graphs (constant-degree expanders) whose shortest-path metric has distortion Omega(log n) with any embedding into Euclidean space of any dimension. Furthermore, these graphs cannot be embedded into o(log^2 n)-dimensional space with constant distortion, so these results are essentially tight. The algorithm for finding such an embedding is actually quite simple and can be easily implemented in polynomial time. Strictly speaking, it is a randomized algorithm and the expected distortion is O(log n), but a deterministic variant can be developed. The interested reader is referred to [1] and [2]. In particular, theorem 3.1 in [1] contains many useful and interesting facts regarding embedding a finite metric into more structured spaces.

1) J. Bourgain, "On Lipschitz embedding of finite metric spaces in Hilbert space", Israel J. Math, 52, 1985, p. 46-52.

2) N. Linial, E. London, and Y. Rabinovich, "The geometry of graphs and some of its algorithmic applications", Combinatorica, 15(2), 1995, p. 215-245.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

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

GENIND (written by Zac Friggstad)

The problem breaks down into checking cycles of even length and cycles of odd length in different ways. Cycles of even length are easy once the following fact is established. Say a cycle C is bad if the sum of the f(v) values of nodes in the cycle exceeds floor(|C|/2). Then we have that no cycle of even length is bad if and only if no cycle of length 2 is bad. One direction is obvious so let's assume we have a bad cycle v_1, v_2, ..., v_k of even length. That is, assume the total of the f(v_i) values exceeds k/2. Consider the edges (v_1,v_2), (v_3, v_4), ..., (v_{k-1}, v_k). There are k/2 edges and the total weight of the f(v_i) values exceeds k/2, so then there must be edge (v_i, v_{i+1}) with f(v_i) + f(v_{i+1}) > 1 so that edge is bad. Thus, we only have to check f(u) + f(v) for edges u,v to see if there are any bad cycles of even length which takes O(m) time (discounting the cost of fractional arithmetic, though using floating point numbers would probably be safe enough for this problem).

Finding bad cycles of odd length takes a bit more effort. Once we have verified that f(u) + f(v) <= 1 for each edge e = (u,v), let's add weights to the edges of G where edge e = (u,v) gets weight g(e) = 1-f(u)-f(v) (which is non-negative). Let C = v_1, v_2, ..., v_k be an odd length cycle and notice that the weight of the edges in C is k - 2*(f(v_1) + f(v_2) + ... + f(v_k)). If C is a bad cycle then the sum of the f(v_i) values exceeds (k-1)/2 so the sum of the edge weights of C is strictly less than k-2*(k-1)/2 = 1. On the other hand, if C is a good cycle then the sum of the edge weights of C is at least 1. So, we have reduced the problem of finding a bad odd length cycle to that of finding an odd length cycle whose total edge weight is strictly less than 1.

Now, form a bipartite graph B with a copy of each node in V on each side. For an edge e = (u,v) with weight g(e), connect u on the left to v on the right and also connect v on the left to u on the right with a weight g(e) edge. It isn't too hard to argue the following. For any node v, there is an odd length cycle in G of total edge weight strictly less than 1 if and only if the shortest path from the copy of v on the left of B to the copy of v on the right of B is strictly less than 1. So, we just have to compute the length of the shortest path between the two copies of each node using Dijkstra's algorithm which, when using the standard implementation of Dijkstra's in contest settings, is n calls to an O(m*log m + n) algorithm.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

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

RECTCNT (written by AnhDQ)

The key point of this problem is: there is not any three of the points sharing a same X-coordinate; and the given points are all separate. So we can manage all "vertical" segments in a list by their X-coordinate and length. Then we group the same segments in length by sorting, for every group of K segments, we have K*(K-1)/2 respective rectangles. Sum up all results and print out!

Complexity: O(N x log2 N)

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

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

CPOINT (written by AnhDQ)

We can solve this problem by using Ternary Search algorithm:

- At first, we take a look at a sub-problem: Finding an integer point on the line y=c satisfying its sum of distances to N given points (S') is mininum. In this sub-problem, every integer point on the line y=c will lead to a respective value of S', and all of that values together make a parabolic-like curve on the plane. So we can use Ternary Search algorithm to find the respective mininum value of S'.

- Just imagine that the problem we have to solve is upgraded from the above one, since all the minimum values of S' will together make a parabolic-like curve from which we can find the minimum value of S. Our task is applying Ternary Search algorithm again!

- On the other hand, we can also imagine that all values of S (for respective integer points) will together make a parabola in 3D-space, so our work is using Ternary Search in certain layers when we try to cut it by a plane!

See the source code for details and find more information about the Ternary Search algorithm at: http://en.wikipedia.org/wiki/Ternary_search

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

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

SPREAD (written by AnhDQ)

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

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

NUMGAME2 (written by Snigdha Chandan)

For this particular combinatorial game theory problem the the values of N for which the first player looses are 1,5,9,13,17,21,25 etc.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

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