Editorial for UTS Open '21 P6 - Terra Mater


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

Binary search the minimum danger factor D that requires K or fewer operations to enforce.

Instead of finding the minimum number of hills that must be adjusted, find the maximum number of hills that can be left alone. The height difference between each consecutive hill is at most D. So if hill i and hill j are both unadjusted, |h[i]-h[j]| \le D(i-j).

Partial Solution

Let dp[i]= the maximum number of unadjusted hills up to hill i, assuming you don't adjust hill i. Let j be the last hill before i that was unadjusted. dp[i]=\max(dp[j])+1 for all |h[i]-h[j]| \le D(i-j). In total there can be \max_{1 \le i \le N} dp[i] unadjusted hills. This gives an \mathcal O(N^2 \log 10^9) solution, which doesn't give any points on DMOJ because this subtask doesn't exist.

Full Solution

The condition |h[i]-h[j]| \le D(i-j) can be converted to h[i]-h[j] \le D(i-j), h[j]-h[i] \le D(i-j), so you are trying to find the longest sequence of hills a_1, a_2, \dots such that Da_i-h[a_i] \le Da_{i+1}-h[a_{i+1}] and Da_i+h[a_i] \le Da_{i+1}+h[a_{i+1}]. This is equivalent to finding the longest nondecreasing subsequence over pairs (Di-h[i],Di+h[i]) for 1 \le i \le N which results in an \mathcal O(N \log N \log 10^9) solution.


Comments

There are no comments at the moment.