Official
A - Zombie Editorial by evima
Assume \(A_1, \ldots, A_N\) are sorted in ascending order, and let \(D_i = A_{i+1} - A_i\).
The following strategy is optimal.
- For some indices \(i\) with the largest values of \(D_i\), place bait at the midpoint between zombies \(i\) and \(i+1\).
- Then, alternately place bait at the left end (position \(0\)) and the right end (position \(L\)).
It suffices to try all values \(0, 1, \ldots, N-1\) for the number of baits used in the first phase.
The time complexity is \(O(N \log N)\).
Proof of optimality
- For placing bait between \(A_i\) and \(A_{i+1}\), it is optimal to place it exactly once, at the midpoint. This can be shown from the fact that the upper bound on the time gained by these operations is \((A_{i+1} - A_i)/2\) and this is achievable, and that any operations placing bait outside the interval between \(A_i\) and \(A_{i+1}\) that were performed alongside non-midpoint placements within that interval can still be performed even if all such placements within the interval are replaced by the midpoint placement.
- For placing bait to the left of \(A_1\) or to the right of \(A_N\), it is optimal to place it at position \(0\) or \(L\), respectively. It can be shown that it is optimal to alternate between left and right for these operations, by considering their contribution to the score.
- It is better to perform the “place at an endpoint” operations after the “place at a midpoint” operations. This can be shown by an exchange argument.
- It is better to perform the “place at a midpoint” operations at positions where \(D_i\) is larger. This can be shown from the fact that the sum of the targeted \(D_i\) values contributes positively to the score.
posted:
last update: