Editorial for DMOPC '21 Contest 2 P4 - Water Mechanics
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
For this subtask, the simplest solution is probably, for all indices , determine, if water was poured here, the endpoints of the interval and . Now run a dp[i]
where dp[i]
represents the minimum cost such that the first cells have water in them. This should be a fairly classical DP: sort the intervals and transition in . Note that intervals can overlap.
Time Complexity:
Subtask 2
We can extend the previous solution. We need to calculate more efficiently. Walk through the indices and keep track of the running value. When you are on flat ground for too long, you should update this running value. Note that our values are the same, but done in reverse.
With these intervals, we can do two things. The first is to run a greedy solution where we take the interval with the farthest right point that still covers the leftmost uncovered cell, which works because the intervals are monotonically sorted by both and . The second is to miss this observation and throw a segment tree on top of our previous DP.
Time Complexity: or
Comments
Quick question I see how the greedy method works but can someone explain the segment tree method to me? tysm!