Editorial for UTS Open '21 P6 - Terra Mater
Submitting an official solution before solving the problem yourself is a bannable offence.
Binary search the minimum danger factor that requires 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 . So if hill and hill are both unadjusted, .
Let the maximum number of unadjusted hills up to hill , assuming you don't adjust hill . Let be the last hill before that was unadjusted. for all . In total there can be unadjusted hills. This gives an solution, which doesn't give any points on DMOJ because this subtask doesn't exist.
The condition can be converted to , so you are trying to find the longest sequence of hills such that and . This is equivalent to finding the longest nondecreasing subsequence over pairs for which results in an solution.