May 2010 Contest Prolem Editorials

1) Generalized Spanning Trees (written by Zac)

Approach Taken:
This can be solved via network flow.  First, say we have already verified the trivial condition that the total fraction is |V|-1.  For the moment, fix two nodes u and v.  Construct the following directed graph H on node set V.  Use the following notation. For a node a let f(a) denote the total fraction assigned to edges having a as an endpoint. For a set S let f(S) denote the total fraction assigned to edges having both endpoints in S. Finally, for a set S let f*(S) denote the total fraction assigned of edges having exactly one endpoint in S.

1) For each edge (a,b) of the original graph with value f(a,b) add two opposing directed arcs each with capacity f(a,b)/2
2) For each node a in V\{u,v}, add a directed arc from a to v with capacity 1
3) For each node a in V\{u}, add a directed arc from u to a with capacity equal to f(a)/2

The claim is that there is a violated set S with u in S and v not in S if and only if the maximum flow from u to v in the graph H described above is strictly less than |V|-1.  For one direction, say S is a violated set containing u but not v.  Let's examine the capacity of the corresponding cut S in H:
- |S|-1 total capacity is from edges created in step 2 (1 from each node except u)
- f*(S)/2 total capacity is from edges created in step 1
- (f(a_1) + f(a_2) + ... + f(a_k))/2 total capacity is from edges created in step 3 where a_1, ..., a_k are the nodes not in S

Now, f(a_1) + f(a_2) + ... + f(a_k) = 2f(V) - f(s_1) - f(s_2) - ... - f(s_|S|) where the s_i are the nodes in S (each edge contributes to two vertices).  Therefore, the total capacity of the cut is:

|S| - 1 + f*(S)/2 + f(V) - f(a_1)/2 - f(a_2)/2 - ... - f(a_k)/2

Now, each edge with exactly one endpoint in S has half its value counted among f*(S)/2 and half its value counted among the f(a_i)/2.  Each edge with both endpoints in S is counted twice among the f(a_i)/2.  Therefore, f*(S)/2 - f(a_1)/2 - f(a_2)/2 - ... - f(a_k)/2 = f(S).  Thus, the capacity of the cut is:

|S| - 1 + f(V) - f(S) = |S| - 1 + |V| - 1 - f(S)

Under the assumption f(S) > |S|-1, we have the cut capacity being strictly less than |V|-1.  Therefore, by the max-flow/min-cut theorem the maximum flow between u and v is less than |V|-1.

On the other hand, if the maximum flow between u and v is less than |V|-1 then consider a cut S containing u with capacity less than |V|-1.  The arguments made above can be easily reversed to yield a non-trivial set S with f(S) > |V|-1.

So, if we know two nodes u and v such that u is in a violated set S and v is not, then we can recover such a set using the flow-based algorithm mentioned above.  Fix a node u and try all |V|-1 other nodes v.  We know that either u is in S or u is not in S so for some guess v we have u is in S and v is not, or vice-versa.  So, we just need to run the above algorithm at most 2|V|-2 times: once from u to each node v and once from each node v to u.

While converting to doubles would probably not cause any rounding errors in any reasonable implementation, the bound on the denominators of the rational numbers was chosen such that a careful implementation of rational numbers and either the Edmonds-Karp or Dinic's flow algorithm would not result in overflow if 64 bit integers were used.

2) Rendezvous (written by Akhil Ravidas)

Solution: Tree traversal Complexity: O(N) Difficulty: Easy/Medium

Consider the rooted tree T, with the 1 as the root. Now the required node C for a pair (A,B) is the lowest common ancestor of A and B in this tree. Direct implementation of a text book algorithm leads to a O(N^2logN) or a O(N^2) solution to the problem depending on whether its O(logN) lca or O(1) lca algorithm. Since N <= 1e4, and there are 25 test cases, we need something better than O(N^2) to pass.

Consider a non-leaf node u in the tree. Now we have to compute the number of pairs of nodes whose lca is u. Let u have k children c1,c2,...,ck. Now the subtree rooted at each child c_i is independent. For all combinations of vertices (a,b) with a in c_i and b in c_j , i!=j , have u as their lca. So we must find 2*(|c1| * |c2| + |c1|*|c3| + .. |c1| * |ck| + |c2| * |c3| + |c2| * c4 + ...  + |ck| * |ck-1|) , ie. all C(k,2) combinations of |c_i|s where |c_i| represents the number of nodes in the subtree rooted at c_i. The two factor is because each pair (a,b) appears in the matrix twice as (a,b) and (b,a).

Now to compute this, there are multiple approaches:

1. The sum is equal to (sum of |c_i|)^2 minus sum of |c_i|^2

An alternate and neater approach to compute this sum is to keep the partial sum of c_i's until a point and to multiply the next c value to the present partial sum. ie.

long long partialsum = 0 , res = 0;
for ( int i=1;i<=k;i++ )
{
res += partialsum * C[i];
partialsum += C[i];
}

res*2 is the required sum. Now all the pairs of the form (u,some node in subtree rooted at u) are not considered as we are only considering the pairs among the children of u. So we must add twice the size of subtree rooted at u (excluding u) to the solution. (u,u) also appears in the matrix, so this is another entry for Im(u). So Im(u) = res * 2 + 2* (size of subtree rooted at u) + 1.

Note: If partialsum is initialized to 1, then the subtree term can be ignored completely, since the size of subtree rooted at u excluding u is equal to sum of |c_i|s.

Once the Im values are calculated, the required sum S can easily be computed.

3) Summing Slopes (written by Varun Jalan)

The problem can be solved using Dynamic Programming. We try and form the number starting at the most significant digit and moving towards the least significant digit. We can compute the answer as S(B) - S(A-1), where S(X) is the sum of the slopes of all numbers <= X.

The state can be represented as :

F(k, d1, d2, eq) where

k : The current digit to be filled
d1 : The second last digit
d2 : The last digit
eq : Boolean parameter which is 1 if the partial number formed is equal to the corresponding digits in X, 0 otherwise. It means that we have not placed a smaller digit yet and thus restricts the possible digits we can place next, in order that we do not exceed X.

We try to place all possible digits d3 at index k. If d2 > d1 and d2 > d3, it means that d2 is a maxima and we add to the answer the total numbers which can be formed there onwards. Similarly for a minima.

Finally, we can optimize by noting that the actual value of d1 is not needed. It suffices to know if d1 <= d2 or d1 = d2 or d1 > d2.

4) Nice Quadrangles (written by Ivan Mistreamu)

To detect whether the quadrangle has an integer area we will use the Pick theorem which states that the area of a grid polygon can be calculated in the following way S = W + I/2 - 1. Where W is the amount of lattice points strictly inside the polygon and I is the amount of lattice points on its edge. So the area S will be integer if the amount of lattice points on its edge will be even. Now how we will count the amount of lattice points on the edge of a given quadrangle.

Let us consider any quadrangle ABCD the edges of which don’t intersect. Let’s look at its edge AB. The amount of lattice points lying on that edge can be calculated as gcd(|Ax – Bx|, |Ay – By|) + 1, where gcd is the greatest common divisor. Or it will be gcd(|Ax - Bx|, |Ay - By|) – 1 if we don’t count the points on the ends of segment AB.

So now if we count the same value for each edge we will have the following expression for I = gcd(|Ax - Bx|, |Ay - By|) + gcd(|Bx - Cx|, |By - Cy|) + gcd(|Cx - Dx|, |Cy - Dy|) + gcd(|Dx - Ax|, |Dy - Ay|) (1). But we only need to each if that value is odd or even. For two given non-negative integers gcd(a, b) is even iff a and b are both even. So gcd(|Ax - Bx|, |Ay - By|) is even iff |Ax – Bx| and |Ay – By| are both even. Now |Ax – Bx| is even iff Ax and Bx are both even of both odd. So gcd(|Ax - Bx|, |Ay - By|) is even when the Ax and Bx have the same remainder modulo 2 and Ay and By have the same remainder modulo 2. That means that we don’t need to know the exact value of Ax, Ay, Bx, By, but only their remainders modulo 2. That is true for all other points as well. After we find if any of the gcds in (1) are odd or even we can easily determine if I is odd or even.

Next is how to count all the quadrangles with the stated quality. First we need to split the given point into four groups: the first group with x > 0 and y > 0, the second – x > 0 and y < 0, the third x < 0 and y < 0 and the fourth – x < 0 and y > 0. Then in each group we need to split all points of the group into four groups again: the first group with x even and y even, the second – x even and y odd, the third – x odd and y even and the fourth – x odd and y odd. We will count the amount of points in each group and each subgroup as well. After that we can iterate over all possible variants of taking points from the group. Surely to form a triangle we have to take one point from each group of the first type. Then we try all possible assignment of points from the subgroups.

There are in total 4^4 different types of quadrangles we can form. For each type we know the amount of quadrangles of that type and we can determine if the area of quadrangles of such type is an integer. So we try all those types and if the area is an integer we add the amount of those quadrangles to the answer.
The complexity of the described algorithm is O(n).

5) Lights Out (written by Michael Dorfling)

To see how to solve this problem, let's take an example:

5 3
10100
01100
10011
00010
00100
3 5
5 1
5 3

First, let's pretend all lights can be pressed.

Note that the order in which the lights are pressed doesn't matter, and pressing a light twice is the same as not pressing it at all. Therefore a solution consists of a set of lights.

A solution is determined by which lights in the top row are pressed: Since the order doesn't matter, we can press those first, and then "chase the lights": For every light in the top row that is on, we have to press the light below it, and we can't press any other lights in the second row. Then, for every light in the second row that is on, we have to press the light below it. The same for the third row, and so on.

If we press lights on the top row, not corresponding to a solution, and then chase the lights, only the bottom row will have lights on. What's more, the effect of pushing some lights at the top, say k of them, and chasing the lights, then pressing another light at
the top and chasing the lights again, is the same as first pressing all k+1 lights (some of them possibly the same) and then chasing the lights. Also, whether a light is pressed an odd or even number of times doesn't change.

To solve the puzzle, first chase the lights, to reduce the problem to the case where only the bottom row has any lights on. In our example, we get

00000
00000
00000
00000
10001

Now, for each light on the top row, start with all lights off, press that light, chase the lights, and see what the effect on the bottom row is. For instance

11000
10000
00000
00000
00000

becomes

00000
00000
00000
00000
01101

So, pressing (1,1) and chasing the lights will toggle lights 2, 3 and 5 on the bottom row. We want a set of lights in the top row, such that the combined effect on the bottom row is to toggle lights 1 and 5. In other words we have to solve five equations in five unknowns, where arithmetic is performed modulo 2. In Matrix notation: Ax=b, where:

| 0 1 1 0 1 |         | 1 |
| 1 1 1 0 0 |         | 0 |
A = | 1 1 0 1 1 | and b = | 0 |
| 0 0 1 1 1 |         | 0 |
| 1 0 1 1 0 |         | 1 |

Column j of A is the bottom row after pressing (1,j) on a blank grid and chasing the lights. b is the bottom row after chasing the lights in the original configuration.

But some lights can't be pressed. This adds some additional constraints to the system of equations. Starting with a blank grid, pressing one button at the top, and chasing the lights, we look at which faulty lights are pressed in the process. For instance, starting with (1,1), no faulty lights are pressed. Starting with (1,3), we press (3,5) and (5,3). Going through all five lights at the top, we have the constraints

| 0 0 1 0 1 |     | 0 |
| 0 0 0 0 1 | x = | 1 |
| 0 0 1 0 0 |     | 1 | 

The rows correspond to (3,5), (5,1) and (5,3), in that order. The column on the right corresponds to faulty buttons that are pressed in the first step of the solution, when we chase the lights to clear everything except the last row. Putting these equations together, we must solve

| 0 1 1 0 1 |     | 1 |
| 1 1 1 0 0 |     | 0 |
| 1 1 0 1 1 |     | 0 |
| 0 0 1 1 1 | x = | 0 |
| 1 0 1 1 0 |     | 1 |
| 0 0 1 0 1 |     | 0 |
| 0 0 0 0 1 |     | 1 |
| 0 0 1 0 0 |     | 1 | 

Using Gauss elimination, this reduces to

| 1 0 0 0 0 |     | 0 |
| 0 1 0 0 0 |     | 1 |
| 0 0 1 0 0 |     | 1 |
| 0 0 0 1 0 | x = | 0 |
| 0 0 0 0 1 |     | 1 |
| 0 0 0 0 0 |     | 0 |
| 0 0 0 0 0 |     | 0 |
| 0 0 0 0 0 |     | 0 | 

So there is a unique solution, which is to press lights 2, 3, and 5 in the top row, and chase the lights, giving the solution set {(1,2),(1,3),(1,5),(2,3),(2,5),(3,2),(3,3),(4,3)}.