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

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

##### 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