Editorial for Baltic OI '09 P2 - Candy Machine

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.

A first, simple approach is to use dynamic programming over the wagon positions. This would lead to a run time of $\mathcal O(n^w)$ ~\mathcal O(n^w)~; $20\%$ ~20\%~ of the score should be awarded to such a solution.

When looking for a better solution, we observe that the paths of two wagons never need to cross. Two crossing paths can be replaced by two paths with the parts after the crossing exchanged. Then, we have a "smallest" wagon, i.e. a wagon such that there is no candy with a smaller position than any of the candies caught by that wagon. Now assume we can compute an optimal smallest wagon path (OSWP) such that this wagon catches as many candies as possible. Afterwards, we disregard all candies caught by the smallest wagon, compute the OSWP for the remaining candies, and so on. If the computation of the OSWP can be done in $\mathcal O(n)$ ~\mathcal O(n)~, the whole algorithm runs in $\mathcal O(n^2)$ ~\mathcal O(n^2)~.

Indeed, it is possible to compute an OSWP in $\mathcal O(n)$ ~\mathcal O(n)~. We pass through all candies by increasing output time and maintain a stack of candies; candies on the stack are caught by the wagon. The first candy is pushed on top of the stack. Furtheron, we consider the current candy $c$ ~c~ and the candy on top of the stack (the last candy to be caught by the wagon) $c_s$ ~c_s~. If the wagon can run from the position of $c_s$ ~c_s~ to the position of $c$ ~c~ such that it catches $c$ ~c~ on time, then $c$ ~c~ is put on top of the stack. Else, and if the position of $c$ ~c~ is smaller than that of $c_s$ ~c_s~, the stack is popped until $c$ ~c~ is reachable from $c_s$ ~c_s~ again. Afterwards, $c$ ~c~ is put on the stack. $60\%$ ~60\%~ of the score should be awarded to a correct $\mathcal O(n^2)$ ~\mathcal O(n^2)~ algorithm.

A more efficient algorithm builds upon the idea of non-crossing paths, too, but passes candies by position. Each candy is to be assigned to the leftmost possible wagon. If binary search is used to determine the wagon and a balanced tree is used to store each wagon's candies, a run time of $\mathcal O(n \log^2 n)$ ~\mathcal O(n \log^2 n)~ is possible. Full score should be awarded to a correct algorithm with such runtime.

Further improvements may even yield a runtime of $\mathcal O(n \log n)$ ~\mathcal O(n \log n)~.

Comments

There are no comments at the moment.