Editorial for WC '18 Contest 2 S1 - Laser Grid - Olympiads Online Judge

Editorial for WC '18 Contest 2 S1 - Laser Grid

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.

For convenience, let's pretend that there are two extra vertical lasers with $V$ $V$ values $0$ $0$ and $1\,000\,000$ $1 000 000$ , and similarly two extra horizontal lasers with $H$ $H$ values $0$ $0$ and $1\,000\,000$ $1 000 000$ . Then, let $x_1$ $x_{1}$ be the $x$ $x$ -coordinate of the nearest vertical laser to the left of Ethan (in other words, the largest $V$ $V$ value smaller than $X_E$ $X_{E}$ ). Similarly, let $x_2$ $x_{2}$ be the $x$ $x$ -coordinate of the nearest vertical laser to the right of Ethan (the smallest $V$ $V$ value larger than $X_E$ $X_{E}$ ), and let $y_1$ $y_{1}$ and $y_2$ $y_{2}$ be the $y$ $y$ -coordinates of the nearest horizontal lasers below and above Ethan, respectively. The values $x_1$ $x_{1}$ , $x_2$ $x_{2}$ , $y_1$ $y_{1}$ , and $y_2$ $y_{2}$ may be computed by iterating over all of the lasers' $H$ $H$ and $V$ $V$ values, in $\mathcal O(N+M)$ $O (N + M)$ time.

We can then observe that the $i$ $i$ -th microchip is reachable if and only if $x_1 < X_i < x_2$ $x_{1} < X_{i} < x_{2}$ and $y_1 < Y_i < y_2$ $y_{1} < Y_{i} < y_{2}$ . This check can be performed in $\mathcal O(1)$ $O (1)$ time per microchip, resulting in a total time complexity of $\mathcal O(N+M+K)$ $O (N + M + K)$ .

Comments

There are no comments at the moment.