April 2010 Contest Problems

1) Travelling Salesman Again !

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

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

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.