April 2010 Contest Problem Editorials

1) Travelling Salesman Again ! (written by Varun Jalan aka Syco)

If a trip from i to j is taxed, so is a trip from i-1 to j+1, i - 1 to j, and i to j + 1. We can use this to show that g[i][j] + g[i+1][j+1] <= g[i+1][j] + g[i][j+1]. Thus, the cost matrix is Monge.

A monge array can be shown to satisfy the Demidenko conditions. These conditions are necessary and sufficient conditions that a cost matrix should satisfy in order that the optimal tour be bitonic (first
increasing and then decreasing) For example an optimal tour can be something like : 1 3 4 5 9 8 7 6 2 1.

This allows a DP solution, with state (i,j) which is the value of the optimal tour passing through all nodes between indices i to j. (Treat the optimal tour as two paths, one from 0 to n - 1, and the other from
n - 1 to 0, having no vertices except 0 and n - 1 in common). Time complexity : O(n^2 + K)

There is also an O(n) solution to the problem too, once the g matrix is known. Each entry of the g matrix can be computed in O(log ^2 K) time using a data structure such as a segment tree. This leads to an
O(n log ^2 K + K) solution.

2) Adding Fractions ((written by Varun Jalan aka Syco)

Consider plotting the points (yi,xi) on the plane. For each point i we add, we wish to know what is the point j, along with which the point i makes the maximum slope line when the two points are joined. Note that this point lies on the convex segment of the points p0..p(i-1). Thus we keep a convex segment of the points on a stack as we proceed. When we encounter the point i, we keep popping points from the stack till the current point does not form a concave segment with the last two
points on the stack. The last point on the stack is the optimal j we were looking for. Push i on the stack, and proceed. Since each point is pushed/popped at most once, we have a linear time algorithm.

3) Trip (written by Varun Jalan aka Syco)

It is easy to see that in order to make the least number of stops, one should cover as much distance as possible each time. We can compute this in linear time, by maintaining two pointers p1 and p2 such that a[p2] - a[p1] <= M, but a[p2+1] - a[p1] > M. We can decrement p1 and adjust p2 accordingly.

Thus we get get for each point i, dp[i], which is the minimum number of steps to reach the destination from location i. To count the number of ways,  we have dp[i] = sum dp[j], such that dp[j] = dp[i+1], and a[j] - a[i] <= M. We can easily compute the dp[] array in linear time as well.

4) Lighting (written by Duc)

Construct a bipartite graph in which one set of vertices corresponds to the rows and the other corresponds to the columns of the board. There is an edge from i to j if a[i,j] = 1. The problem asks to find the minimum edge coloring of the graph, i.e. to find the minimum number of colors to color the edges such that none of adjacent edges have the same color.

Minimum edge coloring in general graph is shown to be NP-hard, although an interesting result (Vizing's theorem) says that the minimum number of colors needed (or edge chromatic number) is either D or D+1, for D is the maximum degree of the graph.

However, on bipartite graph, minimum edge coloring is shown to be in P. A theorem by Konig says that in bipartite graph, edge chromatic number is equal to maximum degree. The theorem also suggests an O(VE) algorithm to find the minimum edge coloring.

A proof about Konig's theorem can be found here http://www.kurims.kyoto-u.ac.jp/~iwata/dmi/dmi01e.pdf. There is O(ElogE) time algorithm has been developed, for example http://ecommons.cornell.edu/handle/1813/6283. Some contestants manage to optimize the O(VE) to run into the time limit.

5) Reversed (written by Zac)

There is a linear-time solution to the problem.  The details can get quite technical, so I'll just explain the high-level ideas.  As a warm-up, consider the following problem.  Say we just want to find the least integer C' using the digits of C such that C' > A and C' > B (don't worry about the reversed part yet).  Assume A >= B so we just need to worry about C' > A.  The basic idea is the following.  For any such arrangement C' of C such that C' > A, we can break C' into three parts.  First is the common prefix of C' and A.  Next is the single digit following this prefix which must be greater than the corresponding digit of A.  Finally, we have the remaining digits.  A key observation is that if C'_1 and C'_2 are both greater than A and C'_1 < C'_2, then then length of the common prefix of C'_1 and A is at least the length of the common prefix of C'_2 and A.

A linear-time algorithm for solving this simpler problem is as follows.  Create the longest possible string out of the digits of C that is a prefix of A.  Call this prefix P and say it's length is |P|.  Now, if all remaining digits of C are less than the (|P|+1)st digit (from the left) of A, then iteratively delete the last digit of P until there is a digit of C not used in P that exceeds the (|P|+1)st digit of A.  Once we have found such a digit, append it to P.  Finally, now that P exceeds the length |P| prefix of A, we are free to assign the remaining digits in any way.  The least such way is to first append the remaining 0s to P, then the remaining 1s, and so on.

For the more general problem, finding the longest common prefix of a solution is still a good guiding principle.  For a string S such that S > (both length |S| prefixes of A and B), we can append the remaining n-|S| digits of C in any order to have the resulting string exceed A and B.  Let S' be obtained by appending the remaining 9s to S, then the remaining 8s, and so on.  Then there exists a C' that extends S with C' > A, C' > B, C'^R < A^R, and C'^R < B^R if and only if this string S' is such a solution.  An algorithm proceeds as in the previous paragraph, except we iteratively delete digits of the prefix P until both the condition in the preceding paragraph is satisfied and appending the remaining digits to P in decreasing order results in a valid solution.  This is possible to do in linear time (i.e. constant time per deletion of the last digit of P) with the right bookkeeping.

Now, we are left with a string P such that P > (both length |S| prefixes of A and B) and such that there is a way to append the remaining digits to P to satisfy the conditions on the reversed numbers.  A similar algorithm can be employed to append these digits in such a way as to form the least possible C' that satisfies both the original and reversed inequalities.

6) Flood (written by Duc and Zac)

This problem can be seen as an instance of the Node Weighted Steiner Tree problem in a grid graph. It is proven that in general graphs, no approximation algorithm can guarantee an approximation ratio that is asymptotically better than log n. However, we do have c log n approximation algorithm for some fixed constant c, for example a 2 log n approximation algorithm exists. An even stronger result is available. That is, there exists some constance for which no c log n approximation algorithm exists, unless P=NP [1]. The same result probably also holds in a grid graph too. However, there may also be better approximation algorithms for grid graphs.

Nonetheless, the 2 logn approximation algorithm is not time efficient enough for our problem. So we need to resolve to other heuristics. Here we present an approximation algorithm by Zac:
- Let all the cells be nodes in a graph
- For each cell/node, add edges to the surrounding (up to) eight cells/nodes
- For each edge, set the weight of this edge to be the sum of the weights of the endpoint cells (an island has weight 0)
- From now on, ignore the node weights and consider only the edge weights
- Find a minimum spanning tree of this graph
- Iteratively prune all leaves until only islands are leaves
- Each non-island node remaining in this tree is to be used in the final solution

Of course, there are other tricks (e.g. local search improvements) that one can employ to try to improve this solution. The solution is valid since the sub-tree we find is connected and spans all islands.  The weights of the edges are supposed to somehow capture the cost of using the endpoints in the final solution. Of course, this is not a great approximation as there are some bad examples exist.  However, it did work fairly well on the randomly generated instances.

References
[1] Philip N. Klein, R. Ravi: A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees. J. Algorithms 19(1): 104-115 (1995)

If you would like to see how the final verion of the editorial for 'FLOOD' was created check out the following conversation at Zac and Duc's conversation on Flood