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, the imaginary line is at height \frac{N}{M}\cdot (i-1), and on the right edge, it is at height \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 to \left\lceil \frac{N}{M}\cdot i \right\rceil in column i. We can print all of these pixels in \mathcal{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, so the overall time complexity is \mathcal{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)


Comments

There are no comments at the moment.