Editorial for WC '16 Contest 2 J2 - EHC
Submitting an official solution before solving the problem yourself is a bannable offence.
We should start by sorting all existing holographic emitters in increasing order of distance from the mess hall. We can then iterate over them while maintaining the maximum distance
down the hall that the EHC is so far able to reach.
is initially equal to
, as there's an additional emitter at the entrance to the mass hall. When we consider emitter
, which covers the inclusive range from
to
, the EHC can already reach this range if
, in which case no additional emitters must be installed right before emitter
. Otherwise, there's an intervening distance of
which must be filled in with emitters. Each emitter spans a distance of
metres, and so the additional emitters should be evenly spaced out at intervals of
metres in order to minimize the number of them that are required.
Therefore, new emitters must be installed in order for the EHC to be able to reach emitter
. Either way, we can then set
to
and proceed to the next emitter. Finally, the EHC must still reach the end of the hallway from the end of the range of the furthest emitter. If we pretend that there's a dummy final emitter at a distance of
metres from the mess hall, then this is equivalent to the EHC reaching this dummy emitter, allowing the algorithm to avoid having any other final step.
Comments