AIO 2024¶
We worked on AIO 2024 in class on 23 and 30 July (Twin Rivers, then Javelin, Subbookkeeper, Shopping Spree, Backpacking and Tennis Robot II), and completed the set on 5 August.
| # | Problem | Main idea | Difficulty | Related page |
|---|---|---|---|---|
| 1 | Javelin | count prefix maxima | ★ | — |
| 2 | Subbookkeeper | copy a neighbour | ★ | — |
| 3 | Shopping Spree | sort + exchange argument | ★★ | Greedy |
| 4 | Backpacking | buy just enough; use the tiny price range | ★★★ | Greedy |
| 5 | Tennis Robot II | one round, then jump over whole rounds | ★★★ | — |
| 6 | Atlantis III: Twin Rivers | cost as a function of the new bridge; slope sweep | ★★★★★ | Prefix Sum |
Suggested order
Q1 as a warm-up. Q2 and Q3 are about asking "how do you know this is best?": Shopping Spree is a perfect exchange argument. Q4 and Q5 are about making a correct slow idea fast (a weird constraint in Q4, a repeating pattern in Q5). Q6 is for reading: learn the \(2(\max - \min)\) identity and the trapezoid picture.
1. Javelin¶
Statement. \(N\) students throw in order; student \(i\) throws \(D_i\) metres (all different). A student becomes the leader if their throw beats every earlier throw. How many different students were leader at some point?
Idea. Scan once, keep the best throw so far, count how often it is beaten. 5 2 3 8 1 7: \(5\) leads, \(8\) leads, nobody else. Answer \(2\).
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// A student leads if their throw beats every earlier throw: count prefix maxima.
void solve() {
int n;
cin >> n;
vector<int> d(n);
for (int i = 0; i < n; i++) {
cin >> d[i];
}
int best = 0, ans = 0;
for (int i = 0; i < n; i++) {
if (d[i] > best) {
best = d[i];
ans++;
}
}
cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
for (int i = 0; i < T; i++) {
solve();
}
return 0;
}
2. Subbookkeeper¶
Statement. A word's score is the number of neighbouring equal letters (HELLLLLO scores 4). One letter of the word is missing and shown as ?. Fill it in to maximise the score.
Idea. Copy the letter after the ? (or the letter before it if the ? is last), then count the equal pairs.
Why this is best: the ? only touches the two pairs next to it. Any letter other than a neighbour's scores \(0\) from them. Copying a neighbour scores at least \(1\), and when both neighbours are the same letter, copying either scores \(2\) (RE?EL → REEEL). When the neighbours differ, no letter can match both, so \(1\) is the most possible.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Copy the neighbour into the '?': the letter after it, or the letter before it
// when the '?' is last. That always buys one extra adjacent pair.
void solve() {
int n;
string s;
cin >> n >> s;
for (int i = 0; i < n; i++) {
if (s[i] == '?') {
if (i < n - 1) {
s[i] = s[i + 1];
} else {
s[i] = s[i - 1];
}
}
}
int ans = 0;
for (int i = 0; i + 1 < n; i++) {
if (s[i] == s[i + 1]) {
ans++;
}
}
cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
for (int i = 0; i < T; i++) {
solve();
}
return 0;
}
3. Shopping Spree¶
Statement. A shop has \(N\) items (\(N\) even) with sorted prices \(c_1 \le \dots \le c_N\). Items must be bought in pairs and you pay for the more expensive item of each pair. You have \(K\) coupons; a coupon makes one pair cost the cheaper item instead. Minimise the total.
Idea (sample \(N = 8\), \(K = 2\), prices \(1 \dots 8\)):
- No coupons. The most expensive item must be paid anyway, so let it "carry" the second most expensive for free: pairs \((7,8), (5,6), (3,4), (1,2)\), i.e. pay every second item from the top.
- All coupons. The cheapest item is what you pay, so let it carry the most expensive: \((1,8), (2,7), \dots\), i.e. pay the cheapest half.
- Mixed. Use the \(K\) coupons on (cheapest \(K\)) × (most expensive \(K\)): \((1,8), (2,7)\) cost \(1 + 2 = 3\). Pair the middle \(3,4,5,6\) as in step 1: pay \(4 + 6 = 10\). Total \(13\).
Why optimal: swapping any two items between pairs so that a plan looks more like this one never increases the cost (exchange argument).
Overflow
\(2\cdot10^5\) items of up to \(10^4\) each: the total needs long long.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Spend the k coupons on (cheapest, most expensive) pairs, then pair what is
// left from the middle outwards and pay for every second item.
void solve() {
int n, k;
cin >> n >> k;
vector<int> c(n);
for (int i = 0; i < n; i++) {
cin >> c[i];
}
ll ans = 0;
for (int i = 0; i < k; i++) {
ans += c[i];
}
for (int i = k + 1; i < n - k; i += 2) {
ans += c[i];
}
cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
for (int i = 0; i < T; i++) {
solve();
}
return 0;
}
4. Backpacking¶
Statement. Norman walks from town \(1\) to town \(N\). Walking from town \(i\) to \(i + 1\) takes \(D_i\) days and he eats one can per day. His backpack holds at most \(K\) cans. Cans cost \(C_i\) in town \(i\), with \(C_i \le 20\). He starts empty. Minimise the total cost.
Idea.
- If prices only go up, buy as much as possible early. If the backpack were infinite, buy everything at the cheapest town seen so far.
- Greedy: in town \(i\), buy just enough to reach the next town that is cheaper than \(i\); if the backpack cannot hold that much, fill it.
- Sample 3 (\(C = 5\,3\,4\,1\,2\), all distances \(2\), \(K = 3\)): town 1 buys 2 (cost 10), town 2 wants 4 but fills to 3 (cost 9), town 3 tops up 1 (cost 4), town 4 buys the last 2 (cost 2). Total \(25\).
- Speed. "Next cheaper town" naively is \(O(N^2)\). Because \(C_i \le 20\), sweep from the right keeping
last[v]= nearest town with price \(v\); the next cheaper town is \(\min(\texttt{last}[1..C_i - 1])\), at most 19 checks. Days between towns come from a prefix sum.
Read the strange constraint
A limit like \(C_i \le 20\) in a problem with \(N = 2\cdot10^5\) is almost always the key to the full solution.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// At every town buy just enough to reach the next strictly cheaper town, or
// fill the backpack if that is not enough. Since c[i] <= 20 we can find the
// next cheaper town with one backwards pass over the 20 possible prices.
void solve() {
int n, k;
cin >> n >> k;
vector<ll> d(n, 0);
for (int i = 0; i + 1 < n; i++) {
cin >> d[i];
}
vector<int> c(n);
for (int i = 0; i < n; i++) {
cin >> c[i];
}
// pre[i] = number of days from town 0 to town i
vector<ll> pre(n, 0);
for (int i = 1; i < n; i++) {
pre[i] = pre[i - 1] + d[i - 1];
}
// nxt[i] = first town after i that is cheaper than i, else the last town
vector<int> nxt(n, n - 1);
vector<int> last(21, n - 1);
for (int i = n - 1; i >= 0; i--) {
int best = n - 1;
for (int v = 1; v < c[i]; v++) {
best = min(best, last[v]);
}
nxt[i] = best;
last[c[i]] = i;
}
ll ans = 0, cur = 0;
for (int i = 0; i < n; i++) {
ll need = min(pre[nxt[i]] - pre[i], (ll) k);
ll buy = max(0LL, need - cur);
ans += buy * c[i];
cur += buy;
if (i + 1 < n) {
cur -= d[i];
}
}
cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
for (int i = 0; i < T; i++) {
solve();
}
return 0;
}
5. Tennis Robot II¶
Statement. \(N\) bins start with \(X_i\) balls each. A robot repeats \(M\) instructions forever; instruction \(j\) moves one ball from bin \(A_j\) to bin \(B_j\). It crashes when told to take a ball from an empty bin. How many instructions succeed, or does it run FOREVER?
Sample 1: bins \(2\,1\,1\,3\), instructions \(1\to2\), \(3\to1\), \(2\to4\). The robot completes 4 instructions and crashes on the fifth (\(3 \to 1\) with bin 3 empty).
Idea.
- Simulate the first round. If it crashes, print the count.
- After a complete round, bin \(i\) has changed by a fixed amount: it loses \(\Delta_i = X_i - (\text{count after round 1})\) balls per round, and every later round repeats exactly the same moves.
- A bin with \(\Delta_i \le 0\) never gets emptier than in round 1, so it never causes a crash. If no bin has \(\Delta_i > 0\):
FOREVER. - Let \(m_i\) be the lowest level bin \(i\) reached during round 1 (right after a take). In round \(r\) that low point is \(m_i - (r-1)\Delta_i\), and the robot crashes in the first round where it would drop below \(0\): \(r_i = \lfloor m_i / \Delta_i \rfloor + 2\).
- The crash happens in round \(r = \min_i r_i\). Jump straight to the start of that round (bin \(i\) holds \(X_i - (r-1)\Delta_i\)) and simulate it; the answer is \((r-1)M + (\text{successful steps in round } r)\).
Two simulated rounds: \(O(N + M)\). The answer can exceed \(2^{31}\), so use long long.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n, m;
cin >> n >> m;
vector<ll> x(n + 1), cur(n + 1), mn(n + 1);
for (int i = 1; i <= n; i++) {
cin >> x[i];
cur[i] = mn[i] = x[i];
}
vector<int> a(m + 1), b(m + 1);
for (int j = 1; j <= m; j++) {
cin >> a[j] >> b[j];
}
// First turn
for (int j = 1; j <= m; j++) {
if (cur[a[j]] == 0) {
printf("%lld\n", (ll) j - 1);
return 0;
}
cur[a[j]]--;
cur[b[j]]++;
mn[a[j]] = min(mn[a[j]], cur[a[j]]);
}
ll r = LLONG_MAX;
vector<ll> D(n + 1);
for (int i = 1; i <= n; i++) {
D[i] = x[i] - cur[i];
if (D[i] > 0) r = min(r, mn[i] / D[i] + 2);
}
if (r == LLONG_MAX) {
cout << "FOREVER";
return 0;
}
// Jump to the beginning of the r-th turn
for (int i = 1; i <= n; i++) cur[i] = x[i] - (r - 1) * D[i];
for (int j = 1; j <= m; j++) {
if (cur[a[j]] == 0) {
cout << (r - 1) * m + j - 1;
return 0;
}
cur[a[j]]--;
cur[b[j]]++;
}
return 0;
}
This is the version from class. Besides the official samples, we checked it against a direct simulation on 300 random small cases.
6. Atlantis III: Twin Rivers¶
Statement. The city is three parallel strips separated by two rivers, each \(1\) km wide; the city is \(L\) km long. \(N\) bridges exist, bridge \(i\) crosses river \(R_i\) at position \(B_i\). \(T\) trips each go from strip 1 at position \(X_j\) to strip \(S_j\) (2 or 3) at the same position. You may build one more bridge at a whole-number position over either river. Minimise the total shortest-trip length.
The identity everything rests on. A trip from \(X\) crossing river 1 at \(a\) and river 2 at \(b\) walks \(|X - a| + 1 + |a - b| + 1 + |b - X|\). The three distances \(|X-a| + |a-b| + |b-X|\) are always twice the spread of the three points, so
Idea.
- \(a\) and \(b\) play symmetric roles, so write the solution for "new bridge on river B" once and run it twice with the rivers swapped.
- For one trip, as the new bridge \(p\) slides left to right, its cost using the nearest existing river-A bridge on the left (or right) is a trapezoid: flat at the bottom between that bridge and \(X\), rising by \(2\) per km on both sides. Take the better of the two trapezoids and cap it by the trip's cost without the new bridge.
- The resulting cost curve only has slopes \(-2\), \(0\), \(+2\). So instead of recomputing all \(T\) trips for every \(p\), record where each trip's slope changes in a difference array and sweep \(p\) once, accumulating slope and value. \(O(N + T + L)\).
In class we focused on the identity and the trapezoid picture; the full code below is for reading (about 190 lines). It was checked against brute force on 1100 random small cases and runs in \(0.64\) s on the largest input.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll) 4e18;
// Distance from x to the nearest bridge at or left / right of x, -1 if none.
ll dlt(const vector<int> &b, ll x) {
int p = (int) (upper_bound(b.begin(), b.end(), (int) x) - b.begin());
if (p == 0) {
return -1;
}
return x - b[p - 1];
}
ll drt(const vector<int> &b, ll x) {
int p = (int) (lower_bound(b.begin(), b.end(), (int) x) - b.begin());
if (p == (int) b.size()) {
return -1;
}
return b[p] - x;
}
// A trip at x crossing both rivers at u and v costs 2*(max-min)+2.
ll span(ll x, ll u, ll v) {
return 2 * (max(x, max(u, v)) - min(x, min(u, v))) + 2;
}
// Sweep over every position of the new bridge, assuming it goes on river B.
// a / b are the existing bridges on river A / B, and xa / xb / xc are the trips
// crossing only A, only B, or both rivers.
ll run(ll L, const vector<int> &a, const vector<int> &b,
const vector<int> &xa, const vector<int> &xb, const vector<int> &xc) {
if (a.empty() && (!xa.empty() || !xc.empty())) {
return INF;
}
ll lo = -L - 1, hi = 2 * L + 1;
// upd[p] is how much the slope changes on the step from p to p+1
vector<int> upd((size_t) (hi - lo + 2), 0);
ll base = 0, slope = 0;
for (int x : xa) {
ll p = dlt(a, x), q = drt(a, x);
ll d = min(p < 0 ? INF : p, q < 0 ? INF : q);
base += 2 * d + 1;
}
for (int x : xb) {
ll p = dlt(b, x), q = drt(b, x);
ll d = min(p < 0 ? INF : p, q < 0 ? INF : q);
if (d == INF) {
// The new bridge is the only way across: cost is a plain V shape.
base += 2 * (x - lo) + 1;
slope -= 2;
upd[x - lo] += 4;
} else {
base += 2 * d + 1;
upd[x - d - lo] -= 2;
upd[x - lo] += 4;
upd[x + d - lo] -= 2;
}
}
for (int x : xc) {
ll dl = dlt(a, x), dr = drt(a, x);
// cur = best trip length using only the existing bridges
ll cur = INF;
if (!b.empty()) {
ll e1 = dlt(b, x), e2 = drt(b, x);
for (int s = 0; s < 2; s++) {
ll av = (s == 0 ? dl : dr);
if (av < 0) {
continue;
}
ll ap = (s == 0 ? x - av : x + av);
for (int t = 0; t < 2; t++) {
ll bv = (t == 0 ? e1 : e2);
if (bv < 0) {
continue;
}
cur = min(cur, span(x, ap, t == 0 ? x - bv : x + bv));
}
}
}
// Using the new bridge with the closest A bridge on each side gives two
// trapezoids with floors vl and vr; cur clamps them from above.
ll vl = (dl < 0 ? INF : 2 * dl + 2);
ll vr = (dr < 0 ? INF : 2 * dr + 2);
bool ul = (vl != INF && vl < cur);
bool ur = (vr != INF && vr < cur);
if (cur == INF) {
ll m = INF;
if (dl >= 0) {
m = min(m, span(x, x - dl, lo));
}
if (dr >= 0) {
m = min(m, span(x, x + dr, lo));
}
base += m;
slope -= 2;
if (ul) {
upd[x - dl - lo] += 2;
}
upd[x - lo] += 2;
if (ul && ur) {
upd[x + dr - dl - lo] -= 2;
}
if (ur) {
upd[x + dr - lo] += 2;
}
} else {
base += cur;
if (ul && ur) {
ll ol = (cur - vl) / 2, orr = (cur - vr) / 2;
upd[x - dl - ol - lo] -= 2;
upd[x - dl - lo] += 2;
upd[x - lo] += 2;
upd[x + dr - dl - lo] -= 2;
upd[x + dr - lo] += 2;
upd[x + dr + orr - lo] -= 2;
} else if (ul) {
ll ol = (cur - vl) / 2;
upd[x - dl - ol - lo] -= 2;
upd[x - dl - lo] += 2;
upd[x - lo] += 2;
upd[x + ol - lo] -= 2;
} else if (ur) {
ll orr = (cur - vr) / 2;
upd[x - orr - lo] -= 2;
upd[x - lo] += 2;
upd[x + dr - lo] += 2;
upd[x + dr + orr - lo] -= 2;
}
}
}
ll val = base, rate = slope, ans = INF;
for (ll p = lo; p <= hi; p++) {
if (p >= 0 && p <= L) {
ans = min(ans, val);
}
rate += upd[p - lo];
val += rate;
}
return ans;
}
void solve() {
int n;
ll L;
cin >> n >> L;
vector<int> r1, r2;
for (int i = 0; i < n; i++) {
int p, r;
cin >> p >> r;
if (r == 1) {
r1.push_back(p);
} else {
r2.push_back(p);
}
}
sort(r1.begin(), r1.end());
sort(r2.begin(), r2.end());
int t;
cin >> t;
vector<int> one, both;
for (int j = 0; j < t; j++) {
int x, s;
cin >> x >> s;
if (s == 2) {
one.push_back(x);
} else {
both.push_back(x);
}
}
vector<int> emp;
// The two rivers are symmetric, so run the same sweep twice: once with the
// new bridge on river 2, once with it on river 1.
ll ans = min(run(L, r1, r2, one, emp, both), run(L, r2, r1, emp, one, both));
cout << ans << "\n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
for (int i = 0; i < T; i++) {
solve();
}
return 0;
}
Credits & sources
Statements summarised from the official AIO 2024 papers on ORAC (Australian Mathematics Trust); approaches cross-checked with the ORAC editorials. Explanations and code are ours.