Overtaking
Key observation The reserve bus's presence does not affect the non-reserve buses' mutual blocking order among themselves. A slower non-reserve bus i only blocks the reserve bus if i arrived at the previous station str...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
$N$ buses and one reserve bus (bus $N$) travel a road with $M$ sorting stations at positions $S[0] < S[1] < \cdots < S[M{-}1]$. Bus $i$ has speed $W[i]$ (time per unit distance) and departure time $T[i]$. The reserve bus has speed $X$ and variable departure time $Y$.
Between stations, each bus travels at its own speed. At each station, a bus's arrival time is the maximum of its own expected arrival and the expected arrivals of all buses that arrived at the previous station strictly before it (slower buses ahead block faster ones).
For each query value of $Y$, determine the reserve bus's arrival time at the last station.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Key observation
Observation.
The reserve bus's presence does not affect the non-reserve buses' mutual blocking order among themselves. A slower non-reserve bus $i$ only blocks the reserve bus if $i$ arrived at the previous station strictly before the reserve bus.
This holds because the reserve bus can only block buses behind it (those arriving later), but we only care about the reserve bus's own arrival time, and the buses that block the reserve bus at each station are exactly those non-reserve buses that arrived earlier.
Precomputation
Simulate the $N$ non-reserve buses through all $M$ stations (without the reserve bus). For each station $j$, store the arrival times sorted, along with prefix maxima of their expected arrivals at station $j + 1$.
Per-query processing
For a given $Y$:
Set $t_{\mathrm{res}} = Y$.
For each segment from station $j$ to $j + 1$:
Compute the reserve bus's expected arrival: $e = t_{\mathrm{res}} + X \cdot (S[j{+}1] - S[j])$.
Binary-search among non-reserve buses at station $j$ to find those arriving strictly before $t_{\mathrm{res}}$.
The blocking value is the prefix maximum of their expected arrivals at station $j + 1$.
$t_{\mathrm{res}} \gets \max(e, \text{blocking value})$.
Return $t_{\mathrm{res}}$.
Complexity
Preprocessing: $O(NM \log N)$ --- simulating $N$ buses through $M$ stations with sorting at each station.
Per query: $O(M \log N)$ --- binary search at each of $M$ stations.
Space: $O(NM)$.
Correctness.
The reserve bus does not alter non-reserve buses' arrival times in this formulation because we compute the non-reserve simulation independently. The only interaction is one-directional: non-reserve buses block the reserve bus. This is valid because the problem's blocking rule only considers buses arriving strictly before the current bus, and adding the reserve bus does not change the relative ordering among non-reserve buses.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// IOI 2023 - Overtaking
// N buses + 1 reserve bus travel through M sorting stations.
// At each station, a bus's arrival = max(own expected, max expected of all
// buses that arrived earlier at the previous station).
// For each query Y (reserve bus departure time), compute its final arrival.
//
// Precompute non-reserve buses (ignoring reserve bus's effect on them).
// For each station, maintain sorted arrival times + prefix max of expected
// arrivals. Answer each query in O(M log N) via binary search.
int L_road, N, M;
ll X_speed;
vector<ll> T_dep, W_speed, S_pos;
vector<vector<pair<ll, ll>>> sorted_station; // (arrival, expected_next)
vector<vector<ll>> prefix_max_expected;
void init(int _L, int _N, vector<ll> _T, vector<int> _W,
int _X, int _M, vector<int> _S) {
L_road = _L;
N = _N;
M = _M;
X_speed = _X;
T_dep = _T;
W_speed.assign(N, 0);
for (int i = 0; i < N; i++) W_speed[i] = _W[i];
S_pos.assign(M, 0);
for (int i = 0; i < M; i++) S_pos[i] = _S[i];
// Simulate non-reserve buses through all stations
vector<vector<ll>> bus_arrival(M, vector<ll>(N));
for (int i = 0; i < N; i++)
bus_arrival[0][i] = T_dep[i];
for (int j = 0; j + 1 < M; j++) {
ll dist = S_pos[j + 1] - S_pos[j];
// (arrival at j, expected at j+1)
vector<pair<ll, ll>> arrivals(N);
for (int i = 0; i < N; i++)
arrivals[i] = {bus_arrival[j][i], bus_arrival[j][i] + W_speed[i] * dist};
// Sort by arrival time at station j
vector<int> order(N);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
return arrivals[a].first < arrivals[b].first;
});
// Compute actual arrival at j+1 (blocked by slower buses ahead)
ll running_max = 0;
for (int idx : order) {
ll expected = arrivals[idx].second;
bus_arrival[j + 1][idx] = max(expected, running_max);
running_max = max(running_max, expected);
}
}
// For each station, precompute sorted arrivals + prefix max of expected next
sorted_station.resize(M);
prefix_max_expected.resize(M);
for (int j = 0; j + 1 < M; j++) {
ll dist = S_pos[j + 1] - S_pos[j];
vector<pair<ll, ll>> arr_exp(N);
for (int i = 0; i < N; i++)
arr_exp[i] = {bus_arrival[j][i], bus_arrival[j][i] + W_speed[i] * dist};
sort(arr_exp.begin(), arr_exp.end());
sorted_station[j] = arr_exp;
prefix_max_expected[j].resize(N);
ll mx = 0;
for (int i = 0; i < N; i++) {
mx = max(mx, arr_exp[i].second);
prefix_max_expected[j][i] = mx;
}
}
}
ll arrival_time(ll Y) {
ll t_res = Y;
for (int j = 0; j + 1 < M; j++) {
ll dist = S_pos[j + 1] - S_pos[j];
ll expected = t_res + X_speed * dist;
// Find last non-reserve bus arriving strictly before t_res at station j
auto& ss = sorted_station[j];
int lo = 0, hi = (int)ss.size() - 1, pos = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (ss[mid].first < t_res) {
pos = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
ll blocking = 0;
if (pos >= 0)
blocking = prefix_max_expected[j][pos];
t_res = max(expected, blocking);
}
return t_res;
}
int main() {
int _L, _N, _X, _M, Q;
scanf("%d %d", &_L, &_N);
vector<ll> T(_N);
vector<int> W(_N);
for (int i = 0; i < _N; i++) scanf("%lld %d", &T[i], &W[i]);
scanf("%d %d", &_X, &_M);
vector<int> S(_M);
for (int i = 0; i < _M; i++) scanf("%d", &S[i]);
init(_L, _N, T, W, _X, _M, S);
scanf("%d", &Q);
while (Q--) {
ll Y;
scanf("%lld", &Y);
printf("%lld\n", arrival_time(Y));
}
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.