Editorial for WC '18 Finals S1 - Behind the Scenes

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 $N$ $N$ shots in order, right before each shot $i$ $i$ , we should move all equipment currently on stage $S_i$ $S_{i}$ to one of the other two stages.

The only remaining question for each shot $i$ $i$ is: Which of the other two stages should stage $S_i$ $S_{i}$ 's equipment be moved to? Let the two possible destination stages be $a$ $a$ and $b$ $b$ , and let $Next[i][s]$ $N e x t [i] [s]$ be the earliest shot $j$ $j$ such that $j \ge i$ $j \geq i$ and $S_j = s$ $S_{j} = s$ (or $\infty$ $\infty$ if there's no such shot). $Next[i][s]$ $N e x t [i] [s]$ indicates the next time at which equipment would need to be moved again if moved to stage $s$ $s$ right before shot $i$ $i$ , which is the only relevant consequence of the choice of destination stage. Therefore, the equipment should be moved to stage $a$ $a$ if $Next[i][a] < Next[i][b]$ $N e x t [i] [a] < N e x t [i] [b]$ , or to stage $b$ $b$ otherwise.

A simple implementation of the above approach, in which each required $Next$ $N e x t$ value is computed by iterating over the remaining shots, has a time complexity of $\mathcal O(N^2)$ $O (N^{2})$ and is fast enough. An $\mathcal O(N)$ $O (N)$ solution is also possible, by first iterating over the shots in reverse to pre-compute all of the $Next$ $N e x t$ values.

Comments

There are no comments at the moment.