Editorial for WC '18 Contest 4 S2 - Farming Simulator
Submitting an official solution before solving the problem yourself is a bannable offence.
At least 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 trees planted along the way.
Upon sorting the holes in increasing order of their values (which may be done in 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 , our strategy will be to walk right from to (while planting a seed in each hole), then walk left back to , and finally walk right back to (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 incurs. At least seconds will be spent walking left to and back right to . 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 value larger than that. Based on this, we can arrive at the number of extra seconds incurred by the interval being .
What remains is applying the above observations to determine the optimal set of sequences, using a dynamic programming approach. We'll let be the minimum number of seconds required to divide the first holes into sequences (such that , and will be our answer). can be computed by considering each possible index such that the last sequence up to there is (resulting in a total extra time of ). As long as we compute and re-use running maximums of values rather than computing from scratch each time, the time complexity of this algorithm will be .
Comments