Editorial for Baltic OI '09 P1 - Beetle


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.

We will assume that x_1 \le x_2 \le \dots \le x_s \le \dots \le x_n, this can be done in \mathcal O(n \log n). Here, x_s = 0 is an extra added "start" drop we will find useful, and n is the total number of drops with this new drop included.

Suppose that the beetle drinks k drops at time moments t_1, t_2, \dots, t_k respectively. The total amount of water drunk will be (m-t_1) + (m-t_2) + \dots + (m-t_k) = km-(t_1 + t_2 + \dots + t_k). Since km is fixed for fixed k, we are to minimize the sum t_1 + t_2 + \dots + t_k. Actually, this formula only holds if t_1, t_2, \dots, t_k \le m, because the beetle does not really get any "penalty points" for passing a drop that is no more. However, letting these penalty points will not change the maximal possible amount, as there is always an optimal route in which the beetle stops before t > m (and it is clever to do so!).

Also notice that the next drop the beetle will drink is always either the closest from left or from right, because there's no point in not drinking a drop if one is passing it anyway.

From here on we use dynamic programming. Let L(i, j, k) be the least possible "penalty sum" beetle would get if at time moment t = 0 it started at x_i and would drink exactly k drops, but there were no drops i, i+1, \dots, j. Similarly, let R(i, j, k) be the least possible "penalty sum" for drinking k drops starting at x_j if there were no drops i, i+1, \dots, j.

If the beetle willing to drink k drops starts at x_i and there are no drops i, i+1, \dots, j, then it can either go for drop at x_{i-1} or x_{j+1}, which reduces the problem to either L(i-1, j, k-1) or R(i, j+1, k-1). The penalty (time spent) for current drop will be either x_i-x_{i-1} or x_{j+1}-x_i. In any case, this penalty will count in for all other k-1 drops the beetle is going to drink. Therefore the following equations hold:

\displaystyle \begin{align*}
L(i, j, k) &= \min\{L(i-1, j, k-1)+k(x_i-x_{i-1}), R(i, j+1, k-1)+k(x_{j+1}-x_i)\} \\
R(i, j, k) &= \min\{L(i-1, j, k-1)+k(x_j-x_{i-1}), R(i, j+1, k-1)+k(x_{j+1}-x_j)\}
\end{align*}

The boundary conditions are:

\displaystyle L(i, j, 0) = R(i, j, 0) = 0, \quad 1 \le i \le j \le n

Now we can check what is the maximal amount of water the beetle can drink if starts at time moment t = 0 at x_s and there is no drop s:

\displaystyle \max\{km-L(s, s, k) : 0 \le k < n\}

We find it by consequently calculating L and R values in \mathcal O(n^3) time and \mathcal O(n^2) memory.


Comments

There are no comments at the moment.