January 2012 Cook-off Problem Editorials

Problem Setter for the contest was Anil Kishore.
Problem Tester for the contest was Harsha.

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

COLLIDE : Collision in Space

This problem is supposed to be the easiest one in this set. Each of the earth and N asteroids start at some initial coordinates and moves in one of the 4 axis parallel directions. We are asked to find the earliest time at which the earth collides with one of the asteroids. Note that the constraints on coordinates are very small, -100 ≤ x,y ≤ 100, so we can just simulate their positions in each second. The 3rd sample case shows that the answer need not be an integer, but if you observe carefully, each object moves only along the grid lines with velocity of 1 unit per second. If you consider the one unit distance between two integer coordinates, they can meet at the end or exactly in the middle. So the answer will always be of the form t.0 or t.5, if there is a collision. One way to take care of this is to multiply the coordinates by 2. Note that all the points now start inside a 400x400 grid and its easy to see that there cannot be collisions outside this grid, and if there is any collision, it will occur no later than t = 400. You can just simulate the positions in each unit of time and do not forget to half the answer finally ( because we multiplied the coordinates by 2 ). Refer writer's solution for an implementation of this idea.

What if the coordinates were huge, say 10⁹. Given the initial coordinates of two points and their direction of movement, we can find the time at which they collide. Refer tester's solution.

Problem Setter's solution.
Problem Tester's solution.

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

FALLDOWN : Remys last tour

Given a 2D array A, find the maximum sum of a path that starts at a cell in the top row and ends at a cell in the bottom row and in each step not moving upwards. Sounds like a DP ( Dynamic Programming ) problem, but the state to be maintained can be tricky. Cells can be visited more than once here and so you need to maintain more additional information in the state than just (curRow, curCol). A situation can be like below,

 .......L*******D*******S************R........... 

Starting from S, you move right till R, reverse direction and go left till L, reverse direction again and move right till D and get down there to go to the row below. Thinking of tricky cases like this gives a good understanding of the problem and helps you decide the DP state and check if it fits in time limit or not. The grid size is very huge 2012 x 2012, so we need to optimize the memory used for dp array. Also, using memoization and going very deep in the recursion stack may create overhead. Here is a nice idea to avoid all these things.

We go from bottom to top and at each row we find the array dp[ ] , where dp[i] is the maximum sum of a path if we start the journey from cell i and get down to next row at a cell to the right of i. So the optimum path traverses some cells in the current row and move down to the next row at cell j > i, i.e., the cell at which we move down is to the right of the cell i. We can first go left and take as much as we can, this is exactly same as the maximum sum of a contiguous subarray ending at index i and then go right i.e., dp[i+1]. A linear traversal from right to left is enough. Similarly we can handle the case when j <= i. Overall complexity is O(RxC). Refer to writer's code below.

Problem Setter's solution.
Problem Tester's solution.

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

FLOORSMV : Moving between Floors

We are given a graph having n nodes and m edges and asked a lot of queries. Given a vertex u, find the sum of the shortest path distances from u to every other vertex ( actually in the problem not to all other vertices, to all floors of every other building ). There can be at most 100 buildings and each building can have a million floors, so we have a huge number of vertices in the graph. But the edges are only a few, and so the number of vertices having degree more than 2 are very less, at most 300. Consider a vertex u of degree 1. It can reach to other vertices only by going through its neighbor. What about vertices of degree 2 ? They can reach other vertices going through one of its 2 neighbors. So we don't have to worry about vertices of degree ≤ 2 while finding the shortest path distances, at least initially. We can run a simple floyd-warshall's algorithm only on the canonical vertices ( those with degree > 2 ) and every other vertex has to reach out to any other vertex by passing through these canonical vertices and the good thing is, we just need to consider at most 2 of them, one above and one below ( viewing in buildings and floors setting ).

Given vq = (bq,fq), we can't go through each vertex u and sum its distance to vq, as there are huge number of vertices. Lets go building by building and with in each building, we look at the segments between the canonical nodes. Consider one such segment A--u1--u2--u3--...--uk--B, where A and B are the canonical nodes and the vertices ui form a chain joining them. We know the distance from A to vq ( = dA ) and B to vq ( = dB ) and each of ui can either each vq through A or B only. Also, if a vertex ui prefers A over B, then all the vertices between A and ui also prefers A over B. This observation leads to a binary search based approach. We actually want to find the maximum index i such that the vertex ui prefers A over B and then we can just sum up the distances ( dA+1, dA+2, ..., dA+i ) using a simple formula. Index i is (dB-dA+k)/2 if dA <= dB else k - (dA-dB+k)/2. Some variation of ideas in this problem and a simpler version of it is used in ACM-ICPC Regionals of Amritapuri this year.

Problem Setter's solution.
Problem Tester's solution.

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

KSUBSUM : Makx Sum

Given an array A of N integers, we are asked to find the Kth maximum sum of a contiguous subarray of elements. Finding the Maximum sum of a subarray is a well known problem. If the array elements are all non-negative, we can use binary search to find the answer in O(n log S) time, where S is the maximum sum of a subarray. In this problem, the values can be negative. As with the other problems in this set, look at the constraints carefully, N ≤ 10,000 and K ≤ 2012. We go through the array from left to right and at each index i, we find all K maximum sums of subarrays, ending at index i. If S is the prefix sum array, where S[i] = A[1] + A[2] + ... + A[i], then all subarray sums ending at index i can be computed using S[i] - S[j], for j = 0 to i-1 and considering S[0] = 0. But we only need top K of them, so we can subtract S[j] s in non-decreasing order and only K of them. This requires us to maintain the array S in sorted order and this can be done similar to insertion sort in O(K) time per insertion.

Now that we have the top-K subarray sums ending at index i, we can compare them with the current top-K best answers so far and pick some of them and drop others. Note that at each step you only need to maintain K minimum prefix sums and K maximum subarray sums so far. Given the best K sums so far and the current K sums, we can merge the two sorted arrays and get the updated best K sums. This can also be done in O(K) time. The overall time complexity is O(NK). Maintaining a set ( or heap ) in which each insertion is additional O(log K) only increases the running time by more than 10x and may not fit in the given time limit.

Problem Setter's solution.
Problem Tester's solution.

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

TAKEAWAY :Zeta-Nim Game

This one is a typical algorithmic game theory problem. Those who are not familiar with this topic may read this excellent tutorial on topcoder. We can solve this using basic Grundy and NIM theory. We can pre-compute the grundy values of all possible states the game can be in and then for each testcase, xor the corresponding grundy values and if the result is non-zero, Nancy ( first player ) wins, else Zeta wins. First thing to note is, K ≤ N, as allowing a player to remove more stones than actually present is useless, so K = minimum(N,K). Let G(N,K) be the grundy value of the state where N stones are present in the pile and at most K stones can be removed. If we remove 1 ≤ p ≤ K stones in this step, the resultant state is G(N-p,p). We have the following recurrence,

G(N,K) = mex{ G(N-1,1), G(N-2,2), G(N-3,3), . . . , G(N-K,K) }

But this doesn't look good, as it may take O(N) time to find each of the all N² grundy values, leading to O(N³) time. If you visualize this on the grid, G(N,K) and G(N+1,K) are closely related.

G(N,K+1) = mex{ G(N-1,1), G(N-2,2), G(N-3,3), . . . , G(N-K,K), G(N-K-1,K+1) }, depends on just one more additional value than G(N,K).

We can find the grundy values of each row of G by maintaing the same boolean visited array and values may only increase as we move left to right. This can be done in O(N) time per row, so the overall complexity is O(N*N). Draw a grid on paper and see how this works.

Problem Setter's solution.
Problem Tester's solution.

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