Editorial for Baltic OI '09 P1 - Beetle - Olympiads Online Judge

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$ $x_{1} \leq x_{2} \leq \dots \leq x_{s} \leq \dots \leq x_{n}$ , this can be done in $\mathcal O(n \log n)$ $O (n \log n)$ . Here, $x_s = 0$ $x_{s} = 0$ is an extra added "start" drop we will find useful, and $n$ $n$ is the total number of drops with this new drop included.

Suppose that the beetle drinks $k$ $k$ drops at time moments $t_1, t_2, \dots, t_k$ $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)$ $(m - t_{1}) + (m - t_{2}) + \dots + (m - t_{k}) = k m - (t_{1} + t_{2} + \dots + t_{k})$ . Since $km$ $k m$ is fixed for fixed $k$ $k$ , we are to minimize the sum $t_1 + t_2 + \dots + t_k$ $t_{1} + t_{2} + \dots + t_{k}$ . Actually, this formula only holds if $t_1, t_2, \dots, t_k \le m$ $t_{1}, t_{2}, \dots, t_{k} \leq 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$ $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)$ $L (i, j, k)$ be the least possible "penalty sum" beetle would get if at time moment $t = 0$ $t = 0$ it started at $x_i$ $x_{i}$ and would drink exactly $k$ $k$ drops, but there were no drops $i, i+1, \dots, j$ $i, i + 1, \dots, j$ . Similarly, let $R(i, j, k)$ $R (i, j, k)$ be the least possible "penalty sum" for drinking $k$ $k$ drops starting at $x_j$ $x_{j}$ if there were no drops $i, i+1, \dots, j$ $i, i + 1, \dots, j$ .

If the beetle willing to drink $k$ $k$ drops starts at $x_i$ $x_{i}$ and there are no drops $i, i+1, \dots, j$ $i, i + 1, \dots, j$ , then it can either go for drop at $x_{i-1}$ $x_{i - 1}$ or $x_{j+1}$ $x_{j + 1}$ , which reduces the problem to either $L(i-1, j, k-1)$ $L (i - 1, j, k - 1)$ or $R(i, j+1, k-1)$ $R (i, j + 1, k - 1)$ . The penalty (time spent) for current drop will be either $x_i-x_{i-1}$ $x_{i} - x_{i - 1}$ or $x_{j+1}-x_i$ $x_{j + 1} - x_{i}$ . In any case, this penalty will count in for all other $k-1$ $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*}$ $\begin{aligned} 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{aligned}$

The boundary conditions are:

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

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

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

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

Comments

There are no comments at the moment.