Editorial for DMOPC '21 Contest 2 P4 - Water Mechanics


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: Riolku

Subtask 1

For this subtask, the simplest solution is probably, for all indices i, determine, if water was poured here, the endpoints of the interval L_i and R_i. Now run a dp[i] where dp[i] represents the minimum cost such that the first i cells have water in them. This should be a fairly classical DP: sort the intervals and transition in \mathcal O(N). Note that intervals can overlap.

Time Complexity: \mathcal O(N^2)

Subtask 2

We can extend the previous solution. We need to calculate L_i more efficiently. Walk through the indices and keep track of the running L value. When you are on flat ground for too long, you should update this running L value. Note that our R 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 L_i and R_i. The second is to miss this observation and throw a segment tree on top of our previous DP.

Time Complexity: \mathcal O(N) or \mathcal O(N \log N)


Comments


  • 0
    d3story  commented on Nov. 6, 2021, 3:19 a.m.

    Quick question I see how the greedy method works but can someone explain the segment tree method to me? tysm!