Let . For , define , and set for convenience. Since all initial coordinates are distinct, , while for .
Let be the set of coordinates reachable by frog . Then . If , then . If , then is the set of all integers satisfying or . Moreover, every choice of pairwise distinct coordinates can be realized.
Proof of the reachable sets
Translate all coordinates by , placing frog at . The greatest common divisor of the coordinates of the frogs with indices greater than is initially and remains invariant, because replacing by preserves . Every center of a jump by frog is therefore a multiple of , so a jump can only negate its coordinate modulo . This proves necessity.
The reachable sets have a strong nesting property. If , then either or .
Proof of laminarity
For , we have , and is also a multiple of . Suppose the two sets intersect. Reducing the two residues and of modulo gives the two residues and of . Since , every coordinate of belongs to . The finite case and the singleton follow identically.
Process the frogs in the order . Place each frog at a coordinate of its reachable set that is not already used and has minimum absolute value. This greedy algorithm is optimal.
Proof of the greedy algorithm
Take an optimal assignment that already agrees with the greedy choices for all greater indices. For the current frog , let be the greedy coordinate and let be its coordinate in the optimal assignment. The coordinate is not used by any greater index, so .
It remains to find the closest unused coordinate of each . When , let and normalize a residue to . Its coordinates form the nonnegative stream and the negative stream . When , the negative stream starts at .
For the converse, freeze all frogs with greater indices at a finite set and move only one frog. We have ; let . Write reflection about as . The composition translates by . Bezout's identity therefore produces translation by , and changes the sign. Ignoring occupied landing points, this generates exactly the residue classes above.
It remains to avoid . If an orbit does not meet , this is immediate. Otherwise, the orbit is one arithmetic progression. Let and . Reflections about and move any allowed orbit point to the right of , and alternating them moves it arbitrarily far away. Fix a finite reflection word that translates by . Applied sufficiently far away, every intermediate coordinate lies outside . Hence any two unoccupied points in one orbit are connected.
Finally, induct on the number of frogs. A finite sequence that moves frogs to their targets visits only finitely many coordinates. For , is infinite, so frog can first be parked outside all of them. Move the other frogs, and then move frog to its target. The cases are immediate. Thus every tuple of distinct representatives is reachable.
If is unused in the optimal assignment, assign it to frog without increasing the maximum. Otherwise, some frog uses . Since and , laminarity gives . Hence , so the coordinates of frogs can be swapped. The set of used coordinates and its maximum absolute value remain unchanged. Repeating this exchange proves that some optimal assignment agrees with every greedy choice.
For every residue under the current modulus, store the first unchecked coordinate in each direction. Store all occupied coordinates in a hash set and advance a pointer while it points to an occupied coordinate. The two residue classes defining yield at most four candidates; choose the best one. When , simply compare and .
While iterating downwards, update . When the modulus changes, clear only the residue frontiers and keep the occupied-coordinate set. Every change between positive values replaces the gcd by a proper divisor, at most halving it. Thus there are only different moduli. For one fixed modulus, each occupied coordinate is skipped at most once. The expected time complexity is and the memory complexity is .
Solution written by GPT5.6