Editorial for DMOPC '20 Contest 1 P3 - Victor's Algorithm
Submitting an official solution before solving the problem yourself is a bannable offence.
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.
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.
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.