TRFTRBEZ - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

There are N cars; the i-th car is at position X_i and has speed S_i.
All X_i are in strictly ascending order.

Each second, the cars behave as follows:

  • For i = 1, 2, \ldots, N in order, car i moves to position \min(X_i+S_i, X_{i+1}-1).

A car is unhappy if it doesn’t move in some second.
Find the number of unhappy cars after K seconds.

In this version, S_i \ge 1 for all i.

EXPLANATION:

There’s an obvious solution in \mathcal{O}(N\cdot K), which is to just simulate the process and see which cars become unhappy.
Unfortunately that’s not particularly viable because K can be quite large - upto 10^9.

However, this version has the curious constraint of all car speeds being positive, which has to matter in some way.
And indeed, it does matter a lot. In fact, it gives us a rather strong result:

Claim: If a car doesn’t become happy within the first N seconds, then it will never become unhappy.

Why?

Call car i “blocked” if X_i+1 = X_{i+1} at the beginning of some second.

If no car is initially blocked, then no car can ever be blocked; since car 1 will always be able to move, then car 2 will always be able to move (creating space for car 1), and so on.
In this case, there are no unhappy cars.

Otherwise, let r denote the largest index of an initially blocked car.
Observe that all cars to the right of r can never be blocked at any point in the future.
So, car r will itself be blocked in the first second; but never after that (since car r+1 would’ve moved in the first second, creating some space.)

Car r will be the rightmost unhappy car.

At the end of the first second, all cars \ge r can no longer become blocked ever again.

Now apply the same logic to the prefix till r-1: consider the rightmost blocked car here (if it exists), and it will be blocked this second but never again.

In general, for each second, looking at the rightmost blocked car allows us to cut out a positive-length suffix of cars that will never be blocked again.

Repeat this N-1 times, and we’ll have exhausted all cars (N-1 times is enough since car N can never be blocked), meaning they can’t ever be blocked in the future.

A car needs to be blocked to become unhappy.
Thus, any car that wasn’t already blocked by the end of N seconds will never be blocked, proving our claim.

This simple fact is extremely powerful, because it means we don’t need to simulate all K seconds of the process: we only need to simulate the first N seconds!
(Or stop at K, if K \le N.)

So, we only need to simulate \min(N, K) seconds, each of which takes \mathcal{O}(N) time.
This gives us a solution that’s \mathcal{O}(N^2) (more precisely, \mathcal{O}(N\cdot \min(N, K))), and for the given constraints that’s more than fast enough.

TIME COMPLEXITY:

\mathcal{O}(N\cdot \min(N, K)) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    s = list(map(int, input().split()))

    mark = [0]*n
    for itr in range(min(n, k)):
        for i in range(n-1):
            nxt = min(a[i] + s[i], a[i+1] - 1)
            if a[i] == nxt: mark[i] = 1
            a[i] = nxt
        a[-1] += s[-1]
    
    print(sum(mark))
TRFTRBHD - Editorial