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$ ~i~, determine, if water was poured here, the endpoints of the interval $L_i$ ~L_i~ and $R_i$ ~R_i~. Now run a dp[i] where dp[i] represents the minimum cost such that the first $i$ ~i~ cells have water in them. This should be a fairly classical DP: sort the intervals and transition in $\mathcal O(N)$ ~\mathcal O(N)~. Note that intervals can overlap.

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

Subtask 2

We can extend the previous solution. We need to calculate $L_i$ ~L_i~ more efficiently. Walk through the indices and keep track of the running $L$ ~L~ value. When you are on flat ground for too long, you should update this running $L$ ~L~ value. Note that our $R$ ~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$ ~L_i~ and $R_i$ ~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)$ ~\mathcal O(N)~ or $\mathcal O(N \log N)$ ~\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!