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 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 trees planted along the way.

Upon sorting the holes in increasing order of their P values (which may be done in \mathcal 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, our strategy will be to walk right from P_i to P_j (while planting a seed in each hole), then walk left back to P_i, and finally walk right back to 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 incurs. At least 2(P_j-P_i) seconds will be spent walking left to P_i and back right to 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 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)).

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


Comments

There are no comments at the moment.