Editorial for DMOPC '21 Contest 2 P4 - Water Mechanics - Olympiads Online Judge

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)$ $O (N)$ . Note that intervals can overlap.

Time Complexity: $\mathcal O(N^2)$ $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)$ $O (N)$ or $\mathcal O(N \log N)$ $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!