Editorial for WC '18 Contest 4 S2 - Farming Simulator - Olympiads Online Judge

Editorial for WC '18 Contest 4 S2 - Farming Simulator

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.

At least $H$ $H$ seconds of walking time from left to right are always required, and we're interested in minimizing the number of "extra" seconds required to also get all $N$ $N$ trees planted along the way.

Upon sorting the holes in increasing order of their $P$ $P$ values (which may be done in $\mathcal O(N \log N)$ $O (N \log N)$ time), we'll consider dividing them up into one or more consecutive sequences of holes which will be handled together, such that each hole is included in exactly one sequence. For each such sequence of holes $i \dots j$ $i \dots j$ , our strategy will be to walk right from $P_i$ $P_{i}$ to $P_j$ $P_{j}$ (while planting a seed in each hole), then walk left back to $P_i$ $P_{i}$ , and finally walk right back to $P_j$ $P_{j}$ (while watering each hole's seed, and waiting in place as necessary). An optimal strategy always exists which follows this particular pattern, for some choice of sequences.

The next question is how much extra time any given sequence $i \dots j$ $i \dots j$ incurs. At least $2(P_j-P_i)$ $2 (P_{j} - P_{i})$ seconds will be spent walking left to $P_i$ $P_{i}$ and back right to $P_j$ $P_{j}$ . We can also observe that this is exactly the amount of time that will pass between the first (seed-planting) and last (seed-watering) visit to each hole in the sequence, assuming we keep moving. Extra waiting time may be required along the way if any hole has a $W$ $W$ value larger than that. Based on this, we can arrive at the number of extra seconds incurred by the interval being $\max(2(P_j-P_i), \max(W_i, \dots, W_j))$ $max (2 (P_{j} - P_{i}), max (W_{i}, \dots, W_{j}))$ .

What remains is applying the above observations to determine the optimal set of sequences, using a dynamic programming approach. We'll let $DP[i]$ $D P [i]$ be the minimum number of seconds required to divide the first $i$ $i$ holes into sequences (such that $DP[i] = 0$ $D P [i] = 0$ , and $H+DP[N]$ $H + D P [N]$ will be our answer). $DP[j]$ $D P [j]$ can be computed by considering each possible index $i$ $i$ $(1 \le i \le j)$ $(1 \leq i \leq j)$ such that the last sequence up to there is $i \dots j$ $i \dots j$ (resulting in a total extra time of $DP[i-1]+\max(2(P_j-P_i), \max(W_i, \dots, W_j))$ $D P [i - 1] + max (2 (P_{j} - P_{i}), max (W_{i}, \dots, W_{j}))$ ). As long as we compute and re-use running maximums of $W$ $W$ values rather than computing $\max(W_i, \dots, W_j)$ $max (W_{i}, \dots, W_{j})$ from scratch each time, the time complexity of this algorithm will be $\mathcal O(N^2)$ $O (N^{2})$ .

Comments

There are no comments at the moment.