Editorial for An Animal Contest 3 P6 - Monkey Station - Olympiads Online Judge

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 $\max(R+1, C+1) + 1$ $max (R + 1, C + 1) + 1$ is always achievable.

Let's imagine a grid with $R = 3$ $R = 3$ and $C = 3$ $C = 3$ and trains placed wherever possible.

Assume that cell $(0,0)$ $(0, 0)$ is the top-leftmost cell and cell $(R+1, C+1)$ $(R + 1, C + 1)$ 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 $2$ $2$ . Departure times are scheduled based using the following algorithm:

Assign each train on the leftmost column to depart at time $a_i \bmod 2$ $a_{i} mod 2$ and each train on the topmost row to depart at time $(b_i + 1) \bmod 2$ $(b_{i} + 1) mod 2$ .

The following diagrams provide a visualization:

$\text{[math]}$

It is clear that for all trains departing from the leftmost column, the parity of the arrival time at any cell $(i, j)$ $(i, j)$ will form a checkerboard of $1$ $1$ 's and $0$ $0$ '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 $R$ $R$ and $C$ $C$ .

Call the checkerboard formed with the trains departing from the leftmost column $A$ $A$ and the checkerboard formed with the trains departing from the topmost row $B$ $B$ . We can see that for any cell $(i, j)$ $(i, j)$ , $A_{i, j} \ne B_{i, j}$ $A_{i, j} \neq B_{i, j}$ . 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 $\max(R+1, C+1) + 1$ $max (R + 1, C + 1) + 1$ .

Now, we attempt to achieve a $\max(R+1, C+1)$ $max (R + 1, C + 1)$ solution.

Assume without loss of generality that $R \le C$ $R \leq C$ .

We can observe that each train on the leftmost column will have to depart at time $0$ $0$ , or else they will arrive later than $\max(R+1, C+1)$ $max (R + 1, C + 1)$ . Define the difference as $D = C-R$ $D = C - R$ . Now we can see that every train on the topmost row $b_i$ $b_{i}$ needs to leave in the interval $[0, D]$ $[0, D]$ inclusive or else it will not reach the end of its row in time. Therefore, it suffices to check if there is any row $x$ $x$ between rows $[b_i - D, b_i]$ $[b_{i} - D, b_{i}]$ inclusive such that for all $a_j$ $a_{j}$ $(1 \le j \le N)$ $(1 \leq j \leq N)$ , $a_j \ne x$ $a_{j} \neq x$ .

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 $\max(R+1, C+1) + 1$ $max (R + 1, C + 1) + 1$ .

Time Complexity: $\mathcal{O}(N + M)$ $O (N + M)$ or $\mathcal{O}(N + M \log N)$ $O (N + M \log N)$

Additional Notes

The checker for this problem was included in the problemset as An Animal Contest 3 P4 - Monkey Mayhem.

Comments

There are no comments at the moment.