## Editorial for An Animal Contest 3 P6 - Monkey Station

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ThingExplainer

We claim that is always achievable.

Let's imagine a grid with and and trains placed wherever possible.

Assume that cell is the top-leftmost cell and cell is the bottom-rightmost cell. The number in each cell denotes the time that each train in the leftmost column (first diagram) or topmost row (second diagram) will arrive, mod . Departure times are scheduled based using the following algorithm:

Assign each train on the leftmost column to depart at time and each train on the topmost row to depart at time .

The following diagrams provide a visualization:

It is clear that for all trains departing from the leftmost column, the parity of the arrival time at any cell will form a checkerboard of 's and 's across the entire grid. This also holds for the trains departing from the topmost row. This checkerboard pattern can be extended or shrunk to fit any and .

Call the checkerboard formed with the trains departing from the leftmost column and the checkerboard formed with the trains departing from the topmost row . We can see that for any cell , . Therefore, any collision among trains departing from the leftmost column and trains departing from the topmost row is impossible.

We conclude that we can always achieve an answer of .

Now, we attempt to achieve a solution.

Assume without loss of generality that .

We can observe that each train on the leftmost column will have to depart at time , or else they will arrive later than . Define the difference as . Now we can see that every train on the topmost row needs to leave in the interval inclusive or else it will not reach the end of its row in time. Therefore, it suffices to check if there is any row between rows inclusive such that for all , .

This can be done using line sweep or efficient binary search/preprocessing methods. If during this calculation we find that there are no cells that meet the above criteria, the solution for the scenario must be .

Time Complexity: or