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.
Any piece of filmmaking equipment should only be moved when necessary, immediately before a shot will be filmed on its current stage (the total cost cannot be reduced by instead moving it earlier). Furthermore, whenever multiple pieces of equipment are to be moved away from a given stage, they should all be moved together to a single other stage. Therefore, when simulating the sequence of
shots in order, right before each shot
, we should move all equipment currently on stage
to one of the other two stages.
The only remaining question for each shot
is: Which of the other two stages should stage
's equipment be moved to? Let the two possible destination stages be
and
, and let
be the earliest shot
such that
and
(or
if there's no such shot).
indicates the next time at which equipment would need to be moved again if moved to stage
right before shot
, which is the only relevant consequence of the choice of destination stage. Therefore, the equipment should be moved to stage
if
, or to stage
otherwise.
A simple implementation of the above approach, in which each required
value is computed by iterating over the remaining shots, has a time complexity of
and is fast enough. An
solution is also possible, by first iterating over the shots in reverse to pre-compute all of the
values.
Comments