E - Akari Editorial by evima


Simulating the illuminated cells naively for each bulb requires a total of \(\Omega((H + W)N)\), which I think is pretty hard to finish in time. Let’s consider the beams of light emitted horizontally and vertically separately, and first focus on the horizontal one. When simulating the illuminated cells naively for each bulb, we can see the following fact:

  • When processing a horizontal beam from a bulb,
    • If the cell is already illuminated, adding the bulb does not affect to whether each cell is illuminated or not
    • If the cell is not yet illuminated, all the cell that the horizontal beam from the bulb reaches is unilluminated yet

Therefore, the algorithm of “for each bulb, do nothing if the cell where that the bulb is placed is already illuminated; otherwise mark the cells as illuminated naively until it hits a block” inspects only those cells which are unilluminated yet when marking. Once inspected, the cell is marked as illuminated, so the total number of inspection is \(O(HW)\).

The totally same logic can be applied for the vertical beams, so in the end we can count the number of illuminated cells either by horizontal or vertical beam, so that it can be solved in a total of \(O(HW + N + M)\) time.

posted:
last update: