DMOPC '20 Contest 1 P3 - Victor's Algorithm

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type

I can sort in \mathcal O(1) ~ Victor, 2019

Victor has invented a brand new sorting algorithm that promises an \mathcal O(1) upper bound! However, there is a catch: this algorithm will only work on a nice sequence of numbers. Victor considers a sequence S of length N nice if it is first non-decreasing, then non-increasing. (i.e. S is nice if there exists some position i in the sequence such that S_1 \le S_2 \le \dots \le S_{i-1} \le S_i \ge S_{i+1} \ge \dots \ge S_{N-1} \ge S_N).

You have subsequently found that Victor's algorithm can be extended to any arbitrary sequence of numbers A by converting that sequence of numbers into a nice sequence A', such that A'_i \ge A_i for all i. Sadly, because counting is very difficult, you can only tell Victor to increment one element in the sequence by 1 once a second.

Write a program that finds the minimum number of seconds required to convert any given A into a valid A'!


For all subtasks:

-10^9 \le S_i \le 10^9 for all i.

Subtask 1 [20%]

The length of the sequence N is bounded by 1 \le N \le 1\,000.

Subtask 2 [80%]

The length of the sequence N is bounded by 1 \le N \le 500\,000.

Input Specification

The first line will contain N, the length of the sequence.

The next line will contain N space-separated integers S_1, S_2, \dots, S_N.

Output Specification

Output the minimum number of seconds required to convert the given sequence into a nice sequence.

Sample Input 1

-6 8 6 -1 3 -8 -6 -2 5 -2

Sample Output 1


Explanation of Sample Output 1

We can make this a nice sequence by incrementing S_4 by 6, S_5 by 2, S_6 by 13, S_7 by 11, and S_8 by 7. Since 6+2+13+11+7=39, the answer is 39. It can be shown that this is the minimum possible answer.

Sample Input 2

1 2 3 4 5

Sample Output 2


Explanation of Sample Output 2

This is already a nice sequence.

Sample Input 3

7 6 5 -1 -3 -4 -5

Sample Output 3



There are no comments at the moment.