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

Subtask 1

Let [S_1, \ldots, S_k] be non-decreasing and let [S_{k+1}, \ldots, S_N] be non-increasing.

For S_i to be non-decreasing, we want S_i\le S_{i+1}. Thus we must add \max(0, S_i - S_{i+1}) to S_{i+1}.

Similarly, for S_i to be non-increasing, we want S_i\ge S_{i+1}. Thus we must add \max(0, S_{i+1} - S_i) to S_i.

Finally, either S_k\le S_{k+1} or S_k\ge S_{k+1}, so we are done.

Doing this by iterating the array for each value of k gives an \mathcal O(N^2) solution.

Time Complexity: \mathcal O(N^2)

Subtask 2

Note that if [S_1, \ldots, S_k] is non-decreasing, then [S_1, \ldots, S_{k-1}] must also be non-decreasing. Thus we can precompute the amount of time it takes [S_1, \ldots, S_k] to become non-decreasing for all k in \mathcal O(N).

By the same argument, we can precompute the amount of time it takes [S_k, \ldots, S_N] to become non-increasing for all k in \mathcal O(N).

Iterating the array for each value of k again, we obtain an \mathcal O(N) solution.

Time Complexity: \mathcal O(N)

Alternate Solution

We present a greedy algorithm that solves the problem in \mathcal O(N). We take advantage of the fact that it is never optimal to increment a_k if a_k = \max(S).

  1. Find an index i such that S_i = \max (S).
  2. Now make [S_1,\ldots,S_i] non-decreasing and make [S_i,\ldots,S_N] non-increasing.

Note that both steps take \mathcal O(N) time and thus the overall algorithm also takes \mathcal O(N) time.

Time Complexity: \mathcal O(N)


Comments

There are no comments at the moment.