Editorial for DMOPC '20 Contest 4 P4 - Javelin Throwing

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.

Authors: AvaLovelace, lookcook

Let $t_i$ ~t_i~ be the total number of holes on the $i$ ~i~-th throw. Notice that $b_i = t_i - a_i - 1$ ~b_i = t_i - a_i - 1~. Hence, as the $a_i$ ~a_i~s are fixed, we can minimize $\sum_{j=1}^i b_i$ ~\sum_{j=1}^i b_i~ by minimizing $\sum_{j=1}^i t_i$ ~\sum_{j=1}^i t_i~.

Subtask 1

For subtask 1 we can solve for each prefix separately in $\mathcal O(N)$ ~\mathcal O(N)~ for a total run-time of $\mathcal O(N^2)$ ~\mathcal O(N^2)~.

We can not have less holes in a day than in the past, so transform the array to its prefix max in $\mathcal O(N)$ ~\mathcal O(N)~. For each $i$ ~i~, $t_i = \max(t_i,t_{i-1})$ ~t_i = \max(t_i,t_{i-1})~.

The difference of holes between two days is at most $1$ ~1~. We can do an $\mathcal O(N)$ ~\mathcal O(N)~ scan starting from the suffix to satisfy this. For each $i$ ~i~, $t_i = \max(t_{i+1}-1, t_i)$ ~t_i = \max(t_{i+1}-1, t_i)~.

Time complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

Subtask 2

We can optimize the above approach.

On the $i$ ~i~-th throw, one of only two things can happen:

The javelin lands in the $(a_i+1)$ ~(a_i+1)~-th closest hole from Alice. No new hole is made.
The javelin lands between the $a_i$ ~a_i~-th and $(a_i+1)$ ~(a_i+1)~-th holes, so a new hole is made. (It doesn't actually matter where in between.)

Since Option 1 results in fewer total holes, we want to take Option 1 as many times as possible.

We can do this greedily. Keep a running total $sum$ ~sum~, the current minimum possible value of $\sum_{j=1}^i t_i$ ~\sum_{j=1}^i t_i~. The minimum value of $\sum_{j=1}^i b_i$ ~\sum_{j=1}^i b_i~ can easily be computed from $sum$ ~sum~ as we go along.

On the $i$ ~i~-th throw:

If $a_i < t_{i-1}$ ~a_i < t_{i-1}~, we can take Option 1 and make no hole. In this case, $t_i = t_{i-1}$ ~t_i = t_{i-1}~.
If $a_i = t_{i-1}$ ~a_i = t_{i-1}~, we must take Option 2 and make a hole in front of all the current holes. In this case, $t_i = t_{i-1} + 1$ ~t_i = t_{i-1} + 1~.

But what if $a_i > t_{i-1}$ ~a_i > t_{i-1}~? Then we must take Option 2, as well as change $a_i - t$ ~a_i - t~ previous Option 1s to Option 2s, because we don't have enough holes.

Changing throw $j$ ~j~ from Option 1 to Option 2 would add 1 to each of $t_j, t_{j+1}, \dots, t_{i-1}$ ~t_j, t_{j+1}, \dots, t_{i-1}~, hereby adding $i-j$ ~i-j~ to $sum$ ~sum~. Hence, to minimize $sum$ ~sum~, we want to change the most recent Option 1s. We can do this by keeping a stack of the throws where we took Option 1, popping the most recent throws as needed.

Since each throw is pushed and popped at most once, and the rest of the computation can be done in $\mathcal O(1)$ ~\mathcal O(1)~, the overall time complexity is $\mathcal O(N)$ ~\mathcal O(N)~.

Time complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Problem credit: modified from https://codeforces.com/problemset/problem/924/c

Comments

There are no comments at the moment.