DMOPC '20 Contest 4 P4 - Javelin Throwing

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Alice is training for an upcoming javelin-throwing competition! The javelin-throwing field can be modelled as a 1-D line, with Alice standing at the coordinate 0.

Alice throws N javelins in the positive direction. When she throws a javelin, it lands at some real-valued point on the field, making a hole there. It's possible for the javelin to land exactly in a previously made hole, in which case no new hole is made. Holes are permanent, and there are initially no holes in the field.

Right after the i^\text{th} throw, Alice counts a_i and b_i, the number of holes strictly behind and strictly in front of the javelin she just threw (respectively). She then tells you a_i. You don't know anything else about her throws.

Given the information you have right after the i^\text{th} throw, what is the minimum possible value of \sum_{j=1}^i b_j?


0 \le a_i < i

Subtask 1 [15%]

1 \le N \le 5000

Subtask 2 [85%]

1 \le N \le 2 \times 10^6

Input Specification

The first line contains an integer N, the number of throws.

The second line contains N space-separated integers, a_1, a_2, \ldots, a_N.

Output Specification

Output N space-separated integers. The i^\text{th} integer should be the minimum possible value of \sum_{j=1}^i b_j, given that you know a_1 through a_i.

Sample Input 1

0 0 2

Sample Output 1

0 0 1

Explanation for Sample 1

There are no holes in front of throw 1:

So the first answer is 0.

On throw 2, you know that a_1 = a_2 = 0. It's possible that both throws landed at exactly the same point, in which case there would be no holes in front of either throw:

So the second answer is 0 + 0 = 0.

However, you then learn that there were 2 holes behind throw 3. So the second throw must have landed behind the first, and the only solution would be

for an answer of 0 + 1 + 0 = 1.

Sample Input 2

0 1 0 3 0 2

Sample Output 2

0 0 1 2 5 6

Sample Input 3

0 1 2 1 2

Sample Output 3

0 0 0 1 1


  • 1
    Riolku  commented on March 16, 2021, 8:35 p.m. edited

    Data were updated post-contest to break some unintended solutions.