Editorial for DMOPC '20 Contest 1 P3 - Victor's Algorithm
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Let be non-decreasing and let
be non-increasing.
For to be non-decreasing, we want
. Thus we must add
to
.
Similarly, for to be non-increasing, we want
. Thus we must add
to
.
Finally, either or
, so we are done.
Doing this by iterating the array for each value of gives an
solution.
Time Complexity:
Subtask 2
Note that if is non-decreasing, then
must also be non-decreasing. Thus we can precompute the amount of time it takes
to become non-decreasing for all
in
.
By the same argument, we can precompute the amount of time it takes to become non-increasing for all
in
.
Iterating the array for each value of again, we obtain an
solution.
Time Complexity:
Alternate Solution
We present a greedy algorithm that solves the problem in . We take advantage of the fact that it is never optimal to increment
if
.
- Find an index
such that
.
- Now make
non-decreasing and make
non-increasing.
Note that both steps take time and thus the overall algorithm also takes
time.
Time Complexity:
Comments