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 be the total number of holes on the i-th throw. Notice that b_i = t_i - a_i - 1. Hence, as the a_is are fixed, we can minimize \sum_{j=1}^i b_i by minimizing \sum_{j=1}^i t_i.

Subtask 1

For subtask 1 we can solve for each prefix separately in \mathcal O(N) for a total run-time of \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). For each i, t_i = \max(t_i,t_{i-1}).

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

Time complexity: \mathcal O(N^2)

Subtask 2

We can optimize the above approach.

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

  1. The javelin lands in the (a_i+1)-th closest hole from Alice. No new hole is made.
  2. The javelin lands between the a_i-th and (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, the current minimum possible value of \sum_{j=1}^i t_i. The minimum value of \sum_{j=1}^i b_i can easily be computed from sum as we go along.

On the i-th throw:

  • If a_i < t_{i-1}, we can take Option 1 and make no hole. In this case, t_i = t_{i-1}.
  • If 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.

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

Changing throw j from Option 1 to Option 2 would add 1 to each of t_j, t_{j+1}, \dots, t_{i-1}, hereby adding i-j to sum. Hence, to minimize 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), the overall time complexity is \mathcal O(N).

Time complexity: \mathcal O(N)

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


Comments

There are no comments at the moment.