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.

Solution

---