Editorial for IOI '02 P1 - The Troublesome Frog
Submitting an official solution before solving the problem yourself is a bannable offence.
A naïve time algorithm for the problem iterates through all line segments induced by the point set , and determines how far each segment spacing can be extended to either direction within the point set ().
An efficient time algorithm for the problem is based on an algorithm for finding an equally-spaced collinear subset of a set. The algorithm works by "overlapping" all equally spaced triples in order to determine all maximal equally-spaced collinear subsets. The "overlapping" is performed by constructing an undirected graph where for each equally-spaced triple we create nodes and and the edge ; connected components in this graph correspond to maximal equally-spaced collinear subsets in the original set. Observe that a frog path is simply a linear chain of connected nodes (with at least one edge and two nodes, meaning at least flattened plants) in this graph. Each node in this graph has degree at most two, so the edge set and vertex set both have size . Hence we can find all maximal equally-space collinear subsets in time from the graph.
The only detail here is how to efficiently find the equally-spaced triples from which the graph is created. The obvious method of iterating over all triples of flattened plants would worsen the complexity to . If instead the field is stored as a two-dimensional array (every plant has an entry) giving the identity of the landing on that plant (e.g., if the flattened plant was at , then the array value at is ), you can loop over pairs of flattened plants and , and then look up from the array in constant time since you know what the location of must be if it exists. This strategy takes time but uses memory – in particular, it needs entries of a short integer each, or 50MB. Because the above graph also needs space to store it, this strategy unfortunately would exceed the memory limit of 64MB. However, as this array is very sparse, it may be stored in memory as a hash table, which in the expected case does not affect the time complexity (but which in the worst case does). The third and best option is to construct the graph in linear time and constant memory by sorting the locations (e.g., row major, column minor) and keeping pointers into the list (, , and for pointing to , , and , ) as follows; loop over all values, and for each march and down the list, moving either or forward at each step so as to try to maintain as close to equal spacing as possible; when exactly equal spacing is found, enter the nodes and edge into the graph.
There is also an dynamic programming algorithm to solve this problem, which is plagued by the same memory problems as illustrated above. In addition to storing the identity matrix described above, store another matrix containing whose rows are indexed by ; along the row are entries, one per plant giving the number of landings in a candidate frog path which goes through and but which only uses points which sort before in the ordered list (i.e., pretend the field ends at , and look for frog paths of any length in that smaller field – the idea is to find partial frog paths which violate none of the frog path conditions in the region of the field already examined). Assuming the table is filled up to row , row is filled by considering all flattened plants before , and if there is a flattened plant such that , , and are equally spaced, look up in the array the number of landings in the candidate frog path through from , increment by , and store as the entry in the row for . If would be outside the field, then enter it as having flattenings. At the same time check to see if the next flattened plant () would be outside the graph, and if so, you have a completed frog path. To efficiently determine , the same 50MB array as above is needed; a hash table can again be used, with no increase in average-case time complexity, but an increase in worst-case time complexity.
Background
The problem "The Troublesome Frog" is related to the problem of detecting spatial regularity in images. Spatial regularity detection is an important problem in a number of domains such as computer vision, scene analysis, and landmine detection from infrared terrain images. The AMESCS (All Maximum Equally-Spaced Collinear Subset) problem is defined as follows. Given a set of points in , find all maximal equally-spaced, collinear subset of points. Kahng and Robins [1] present an optimal quadratic time algorithm for solving the AMESCS problem.
Reference
[1] A B. Kahng and G. Robins, Optimal algorithms extracting spatial regularity in images, Pattern Recognition Letters, 12, 757-764, 1991.
Comments