Editorial for DMOPC '20 Contest 5 P2 - On The Clock - Olympiads Online Judge

Editorial for DMOPC '20 Contest 5 P2 - On The Clock

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: AvaLovelace

Notice that on the left edge of column $i$ $i$ , the imaginary line is at height $\frac{N}{M}\cdot (i-1)$ $\frac{N}{M} \cdot (i - 1)$ , and on the right edge, it is at height $\frac{N}{M}\cdot i$ $\frac{N}{M} \cdot i$ . Hence, it fully intersects all the pixels from rows $\left\lfloor \frac{N}{M}\cdot (i-1) \right\rfloor + 1$ $⌊ \frac{N}{M} \cdot (i - 1) ⌋ + 1$ to $\left\lceil \frac{N}{M}\cdot i \right\rceil$ $⌈ \frac{N}{M} \cdot i ⌉$ in column $i$ $i$ . We can print all of these pixels in $\mathcal{O}(1)$ $O (1)$ per pixel, then repeat this process for all other columns to find every lit pixel. One can show that the total number of lit pixels cannot exceed $N + M - 1$ $N + M - 1$ , so the overall time complexity is $\mathcal{O}(N + M)$ $O (N + M)$ .

To avoid rounding errors, you may want to use integer division instead of the floating-point floor/ceiling functions.

Time complexity: $\mathcal{O}(N + M)$ $O (N + M)$

Comments

There are no comments at the moment.