## Editorial for DMOPC '20 Contest 1 P3 - Victor's Algorithm

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

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:

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 .

1. Find an index such that .
2. Now make non-decreasing and make non-increasing.

Note that both steps take time and thus the overall algorithm also takes time.

Time Complexity: