Indian Computing Olympiad

Geometry→Frogs (IOI 2002)

There is a grid with plants at each point. Frogs jump across in straight lines entering the grid from one side and leaving the grid from the other side, landing at grid points. Each frog jumps with a fixed periodicity and flattens the plant that it lands on.

For instance, here is a 7 × 7 grid with four frog paths. Here "o" represents a good plant and "x" is a plant flattened by a frog. There are two horizontal paths in rows 3 and 7, one vertical path in column 4 and one diagonal path going through points (5,2),(4,4),(3,6). Note that a frog need not start its path at the edge of the grid.

             ^
             |
    o  o  o  o  o  o  o
    o  o  o  x  o  o  o
<-- x  o  x  o  x  x  x -->
    o  o  o  x  o  o  o
    o  x  o  o  o  o  o
    o  o  o  x  o  o  o
<-- x  x  x  x  x  x  x -->
             |
             v
      

In this task, you are given the set of grid points where plants have been flattened. From this, you have to compute the longest sequence of plants that could have been flattened on by a single frog. It is sufficient to find sequences of length 3 or more.

There are N flattened plants on an N × N grid, where N is up to 5000. Memory limit is 64 MB.

Brute force:

For each pair of frog points, extend it to a line and see if it is a valid frog path. Keep track of the longest one.

How do we extend the line formed by two frog points to check if it is a frog path? If we maintain the grid as an 0/1 array and check whether the next point in the line is a 0 or 1. This uses up about 25MB of space.

Testing each point is a constant. There could be upto N points on this line, so this takes N steps per pair of points, or (N²)*N = N^3 time overall.

How can we improve this?

When we extend a pair to a line and check that it is a frog path, we can mark all the following pairs of points as having been checked. For instance, if we are checking (x,y) and (x+d,y+d'). Then, we will examine (x+2d,y+2d'), (x+3d,y+3d') .... We then need not try to extend the pairs {(x+d,y+d'),(x+2d,y+2d')}, {(x+2d,y+2d'),(x+3d,y+3d')} to lines.

We still have to examine N² pairs of points, but for some pairs, we have to do no work extending them. How do we measure the complexity taking into account this reduction in work?

For the first pair of points {(x,y),(x+d,y+d')}, suppose we cover M additional points when extending it to a path. This marks M-1 new pairs where no work has to be done. Thus, overall, we take M steps to cover these M pairs. Overall, this averages to 1 step per pair, so the algorithm takes only N² steps.

To record whether a pair of points has already been checked, we need a second boolean array of size N × N (here the entry (i,j) does not correspond to the coordinate of a point on the field but rather to a pair of points (xi,yi) and (xj,yj) that have been flattened by frogs). This takes another 25M of memory, so we are within the overall limit.

How do we look at a pair of flattened points (xi,yi) and (xj,yj) and determine the indices i and j to look up in the second array? Sort the points, first by x and they by y. Find the index of a point by binary search. This adds a log N factor to each iteration, making it N² log N overall.

How do we eliminate the log N factor?

Consider the sorted array of plant positions. Notice that a frog path corresponds to a maximal arithmetic progression in this array.

How do we efficiently find arithmetic progressions in this sorted array? Construct a graph whose vertices are pairs (I,J) where I and J are plant positions in the array. For each triple (I,J,K) of consecuctive plants on a line (i.e., distance+slope(I,J) = distance+slope(J,K)), add an edge from vertex (I,J) to vertex (J,K). In the resulting graph, the degree of each vertex is at most 2 (each pair of plants on a line can be connected to at most one neighbour on either side), we have a graph with N² vertices and N² edges. Observe that each path in the grid is a connected component in this graph. So, run DFS repeatedly to identify the connected components and report the largest component. One minor point is that we need frog paths to be maximal arithmetic progressions within the grid, so for each component in the graph, we need to check that if we extend the minimum and maximum pairs in that component, we will go outside the grid.

To construct this graph, we need to compute equally spaced triples (I,J,K). Naively, this takes time N² log N — for each value I and J, we know the K we need, so we use binary search to check if it exists.

We can do it in time N² as follows. For each value of I, start two pointers J and K to the right of I. For a fixed value of J, move K forward till you find a point equally spaced. If you overshoot, stop the K pointer and move J forward till it is midway between I and K. In this manner, move J and K right in one scan. Whenever you find an equally spaced triple (I,J,K), update the graph to add an edge between (I,J) and (J,K).

---