Editorial for UTS Open '21 P6 - Terra Mater
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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,
.
Partial Solution
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.
Full Solution
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.
Comments