PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
N people buy tickets for an event in the order 1, 2, \ldots, N.
Person i arrives at the event at time A_i.
A person can enter only after everyone with a smaller ticket number has entered already. As soon as this condition is satisfied, they can enter immediately; otherwise they must wait.
You’re allowed to change the arrival time for any one person to any integer in [1, 10^9].
Find the minimum possible total wait time across all N people.
EXPLANATION:
From the easy version, we know that if the arrival times are fixed by the array A, then the total waiting time equals
We’re allowed to change one person’s arrival time.
Suppose we want to change person i’s time.
What should we change it to?
First, let’s define M_i = \max(A_1, \ldots, A_{i-1}) to be the maximum arrival time across every person before i.
If we are to change A_i, observe that setting it to any value below M_i is clearly useless: we could just set it to M_i instead, which would make person i wait less and not change anything for people after i.
In the same vein, setting it to a larger value than M_i is also not going to be optimal - it’s just going to potentially increase wait time for future people.
Thus, if we’re changing it, it’s always optimal to set person i’s arrival time to exactly
M_i = \max(A_1, \ldots, A_{i-1}).
The one exception is for i = 1 since M_1 is not really well defined yet.
However, for i = 1 it’s obvious that if we change it, the optimal arrival time is just 1, i.e. the minimum possible time.
The above observation immediately gives us a solution that works in \mathcal{O}(N^2) time: for each i independently, change A_i to M_i and then recompute the answer.
However, this is too slow so we need to figure out a way to optimize it a bit.
Let’s start with some easy fixes.
If we’re changing person i, then this change won’t affect any people before i at all.
Thus, we don’t have to bother recomputing the part before i if we simply store it.
Next, we look at what exactly changes when we modify A_i.
First, suppose A_i \le M_i.
Then, when we modify A_i to M_i, note that the delay time of people after i doesn’t change at all!
This is because, both before and after the modification, we’ll have M_i = M_{i+1} anyway; since in both cases person i isn’t contributing to changing the maximum arrival time to far.
Thus, in this case the only change is that person i’s waiting time becomes 0, compared to it earlier being (M_i - A_i).
So, a person with A_i \le M_i can be processed in \mathcal{O}(1) time rather than \mathcal{O}(N) time.
Next, consider a person with A_i \gt M_i.
In this case, reducing A_i to M_i can definitely help in reducing the wait times of some future people.
However, if we let j \gt i be the smallest index such that A_j \ge A_i, then observe that changing A_i to M_i will only possibly affect the wait times of persons i, i+1, \ldots, j-1.
For j onwards there will no longer be any effect (since A_j is larger than anything before it anyway.)
So, when A_i \gt M_i, we only need to find the changes for persons i, i+1, i+2, \ldots, j-1 (where j is as defined above the nearest person to the right with not smaller arrival time.)
At first glance, the second optimization doesn’t seem all that useful - it’s still linear, after all.
However, it’s in fact a very powerful optimization!
Observe that this case triggers only when A_i \gt M_i, i.e. A_i is strictly larger than every element before it.
Then, we iterate till the next instance of an element that’s \ge A_i.
Say we iterate till index j.
Then, note that all elements in the range [i+1, j-1] are definitely not going to be larger than everything before them (in particular, they’re not larger than A_i), which means they won’t ever trigger this case!
This means we’ll only iterate over each element of the array at most once via the second case.
This makes our algorithm run in \mathcal{O}(N) time, which is now fast enough.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
base, mx = 0, 1
wait = [0]*n
for i in range(n):
mx = max(mx, a[i])
wait[i] = mx - a[i]
base += wait[i]
mnch, mx = 0, 1
for i in range(n):
curch = - wait[i]
curmx = mx
if a[i] > mx:
for j in range(i+1, n):
if a[j] >= a[i]: break
curmx = max(curmx, a[j])
curch += curmx - a[j] - wait[j]
mnch = min(mnch, curch)
mx = max(mx, a[i])
print(base + mnch)