PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Medium
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 0 for all i.
EXPLANATION:
The easy version had a single strong observation: when all speeds are positive, no car can become unhappy beyond the N-th second.
This, however, fails once 0 speed is allowed.
Still, we can use that solution as a base and build from there.
Let i be the leftmost index such that S_{i} = 0.
(If no such i exists then all speeds are positive; so we can fallback to simulating the first N seconds.)
Car i will never move, so it’s definitely unhappy itself.
Looking at cars 1, 2, \ldots, i-1, we also observe that they are completely independent of all cars beyond i, because car i will never move.
So, for cars 1, 2, \ldots, i-1, there are two possibilities:
- They can become unhappy within the first N seconds; or
- They can become unhappy when a “pile-up” of several cars not moving happens.
This can only be some suffix of cars ending at i.
The first case is trivial to handle; we just simulate N seconds and are done.
If K \le N, this is also the end of the solution; so we work with only K \gt N from now on.
As for the second case, observe that for such a pile-up to happen, the only possible way is: first car i-1 must reach position X_i-1 and get stuck there, then car i-2 must reach X_i-2 and get stuck there, and so on.
In general, for each 1 \le j \lt i, car i-j must reach position X_i-j and will get stuck there.
This will, of course, happen eventually since speeds till i-1 are positive.
The only concern is whether it will happen within K seconds - or more precisely, K-1 seconds; since we’ll then need another second to pass for the unhappiness to kick in.
Let’s try to process cars backwards, i.e. in the order i-1, i-2, \ldots, 1.
Car i-1 is easy: it will simply keep moving forward S_{i-1} units at a time till it reaches its final position, and then stop.
The time taken for this is trivial to compute.
Next, consider car i-2.
There are two possibilities:
- S_{i-2} \le S_{i-1}, i.e. car i-2 is slower.
In this case, car i-2 will just keep moving forward S_{i-2} units every time till it reaches its final position of X_i-2. - S_{i-2} \gt S_{i-1}, i.e. car i-2 is faster.
In this case, there’s a chance car i-2 might reach car i-1.
However, once if this happens, it will never be blocked since car i-1 is also never blocked (till it reaches its final position.)
So, once this car reaches the next one, it will continue to move forward but with a speed of S_{i-1} instead - since its movement is now limited by the space created by car i-1.
The second case here can be further generalized.
Note that since we’re past N seconds, cars with positive speed can never get blocked (till they reach a completely stationary car.)
This in turn means that when some car ‘catches up’ to the next car, it will continue to move - but with its speed reduced to that of the car it caught up to.
Note that this effective speed reduction can chain.
For example, if we have four cars, car 1 can catch up to car 2 first and reduce its effective speed; then car 2 can catch up to car 3 and reduce its own effective speed; which will then cause car 1’s effective speed to also reduce (but after one second.)
Similarly, if car 3 catches up to car 4 in the future, that effect will eventually propagate backwards to cars 2 and 1 as well.
However, this chaining takes time.
Specifically, it can only propagate backwards one car at a time; so the time needed for it to reach another car is proportional to the distance between them.
Let’s use this fact to build a model of what’s happening.
Consider some car j \lt i.
Observe that for any j \le m \lt i, car j will eventually be limited by the speed of \min(S_j, \ldots, S_m).
This, along with the fact that car m’s information needs m-j seconds to propagate back to j, gives us a lower bound of
seconds for this car to reach its final position.
This applies to every j \le m \lt i.
So, one lower bound on the time needed is the maximum of this expression across all such m.
This lower bound is indeed attainable, and hence is the time at which car j reaches its final position and becomes stationary.
That is, car j will reach its final position at
Note that this is additional time needed after simulating the first N seconds.
Also note that these values of X_i are after simulating the first N seconds; and not the input values.
This can be computed in \mathcal{O}(N) time for a fixed j, and so remains \mathcal{O}(N^2) overall - still fast enough.
We technically discussed only the leftmost 0-speed car.
However, the idea is easily extended to all other indices, since for each car with positive speed, only the nearest zero-speed car to its right matters.
Thus, the entire problem is solved in \mathcal{O}(N^2) again.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Tester's code (C++)
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ceil(int x,int y){
return (x+y-1)/y;
}
void solve(){
int n, k; cin >> n >> k;
vector<int> x(n);
vector<int> s(n);
for(int i = 0;i < n;i++){
cin >> x[i];
}
for(int i = 0;i < n;i++){
cin >> s[i];
}
vector<bool> f(n);
for(int i = 0;i < n;i++){
if(s[i] == 0)f[i] = 1;
}
for(int t = 1;t <= min(n,k);t++){
for(int i = 0;i < n-1;i++){
int tx = x[i];
x[i] = min(x[i]+s[i],x[i+1]-1);
if(x[i] == tx)f[i] = 1;
}
x.back() += s.back();
}
k -= min(n,k);
int mn[n][n];
for(int i = 0;i < n;i++)mn[i][i] = s[i];
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
mn[i][j] = min(mn[i][j-1],s[j]);
}
}
vector<int> nx(n,-1);
vector<int> t(n);
for(int i = n-1;i >= 0;i--){
if(s[i] == 0)nx[i] = i;
else if(i+1 < n)nx[i] = nx[i+1];
if(nx[i] == -1)continue;
if(nx[i] == i)continue;
int d = x[nx[i]] - x[i] - (nx[i]-i);
for(int j = i;j <= nx[i];j++){
if(j == nx[i])t[i] = max(t[i],0ll);
else t[i] = max(t[i],j-i+ceil(d-(x[j]-x[i])+(j-i),mn[i][j]));
if(t[i] <= j-i)break;
}
if(t[i] < k)f[i] = 1;
}
int ans = 0;
for(auto x : f)ans += x;
cout << ans << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t; cin >> t;
while(t--)
solve();
return 0;
}