Editorial for DMPG '18 G2 - Gardening Fun - Olympiads Online Judge

Editorial for DMPG '18 G2 - Gardening Fun

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.

Author: r3mark

The key idea is that when watering a subarray, do not consider the entire subarray. Instead, consider the number of times a certain plant is watered as a result of these subarrays. Let $dp[i][j]$ $d p [i] [j]$ be the minimum cost to water the first $i$ $i$ plants and such that the $i^\text{th}$ $i^{th}$ plant has been watered by $j$ $j$ subarrays. Then we add $B$ $B$ for each new subarray at this step and $A$ $A$ for each subarray at this step. So we obtain the following recurrence:

$\displaystyle dp[i][j] = \min\left(\min_{k \le j} \left(dp[i-1][k] + B(j-k) + Aj + C(v_i-j)^2\right), \min_{k \ge j} \left(dp[i-1][k] + Aj + C(v_i-j)^2\right) \right)$ $d p [i] [j] = min (min_{k \leq j} (d p [i - 1] [k] + B (j - k) + A j + C (v_{i} - j)^{2}), min_{k \geq j} (d p [i - 1] [k] + A j + C (v_{i} - j)^{2}))$

Call $V$ $V$ the largest value of $v_i$ $v_{i}$ . It is not hard to see that we only need to consider $j$ $j$ up to $V$ $V$ . The constraints for the first subtask allow this recurrence to pass in time.

Time Complexity: $\mathcal O(NV^2)$ $O (N V^{2})$

For the second subtask, we will perform an optimization so that the transition becomes $\mathcal O(1)$ $O (1)$ instead of the original $\mathcal O(V)$ $O (V)$ . Rewrite the recurrence by rearranging the terms which do not depend on $k$ $k$ :

$\displaystyle dp[i][j] = \min\left(Bj + Aj + C(v_i-j)^2 + \min_{k \le j} (dp[i-1][k]-Bk), Aj + C(v_i-j)^2 + \min_{k \ge j} dp[i-1][k]\right)$ $d p [i] [j] = min (B j + A j + C (v_{i} - j)^{2} + min_{k \leq j} (d p [i - 1] [k] - B k), A j + C (v_{i} - j)^{2} + min_{k \geq j} d p [i - 1] [k])$

We can precompute $\displaystyle \min_{k \le j} (dp[i-1][k]-Bk)$ $min_{k \leq j} (d p [i - 1] [k] - B k)$ and $\displaystyle \min_{k \ge j} dp[i-1][k]$ $min_{k \geq j} d p [i - 1] [k]$ in $\mathcal O(V)$ $O (V)$ for all $j$ $j$ and for each $i$ $i$ by doing a running minimum. So we can now do the transition in $\mathcal O(1)$ $O (1)$ .

Time Complexity: $\mathcal O(NV)$ $O (N V)$

Comments

There are no comments at the moment.