AIO 2020¶
AIO 2020 was our 19 August lesson. The first four review greedy, simulation, counting and binary search; Q5 and Q6 are the hard ones.
| # | Problem | Main idea | Difficulty | Related page |
|---|---|---|---|---|
| 1 | Baubles | case analysis on shortfalls | ★★ | — |
| 2 | Cookies | only five plans; buy as early as possible | ★★ | — |
| 3 | Ghost Encounters | each ghost fixes one start time; most common value | ★★ | std::set |
| 4 | Tennis Robot | binary search the round of the \(N\)-th ball | ★★★ | Binary Search |
| 5 | Ladybugs II | contiguous blocks + range minimum | ★★★★ | Binary Search |
| 6 | Beach Umbrellas | merge intervals, greedy umbrellas, binary search | ★★★★★ | Binary Search, Greedy |
Suggested order
Q1–Q4 in one go: case analysis, enumerating a few plans, turning geometry into a count, and "binary search for the \(N\)-th". Spend the rest on Q6, which we worked through in class.
1. Baubles¶
Statement. Olaf has \(R_O\) red, \(B_O\) blue and \(S\) spare baubles (spares can be painted either colour). The palace orders \(R_P\) red and \(B_P\) blue. Destroy as few of Olaf's baubles as possible so that he cannot fill the order.
Idea.
- Let \(e_r = \max(0, R_P - R_O)\) and \(e_b = \max(0, B_P - B_O)\) be the shortfalls. Olaf can fill the order exactly when \(e_r + e_b \le S\).
- Already \(e_r + e_b > S\): destroy nothing.
- Destroying a spare lowers \(S\) by \(1\): the most efficient move. Destroying a red bauble only starts to help after its surplus \(R_O - R_P\) is gone.
- If \(e_r + e_b \ge 1\), destroying \(S + 1 - e_r - e_b\) spares is enough.
- If both shortfalls are \(0\): destroy all \(S\) spares, then one more bauble beyond the surplus of a colour: \(S + 1 + \min(\text{surplus})\). Only colours the order actually asks for count: if \(R_P = 0\), no number of destroyed red baubles can ever matter.
Sample 4 gives \(0 + 1 + \min(5, 2) = 3\).
The trap we fell into
The first version took the minimum surplus over both colours even when that colour was ordered \(0\) times. The input 1 10 0 0 5 exposes it: the answer is \(6\) (via blue), not \(2\). The fixed version below was checked against brute force over all small inputs.
Baubles.cpp
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
// Olaf can fulfil the order iff er + eb <= s, where er/eb are the red/blue
// shortfalls he has to cover with spares. So we must destroy enough to push
// er + eb above the number of spares he has left.
// Destroying a spare is the most efficient move: cost 1, and it lowers the
// spares he can use by 1. Destroying a red (or blue) bauble only starts to
// help once his surplus of that colour is gone, so it costs surplus + 1 for
// the first useful unit -- never better than a spare, only a fallback for
// when the spares run out.
void solve() {
ll ro, bo, s, rp, bp;
cin >> ro >> bo >> s >> rp >> bp;
ll er = max(0LL, rp - ro); // red baubles Olaf is short of
ll eb = max(0LL, bp - bo); // blue baubles Olaf is short of
if (er + eb > s) {
cout << 0 << "\n"; // already impossible, destroy nothing
return;
}
if (er + eb >= 1) {
cout << s + 1 - er - eb << "\n"; // destroy spares only, that is enough
return;
}
// er == eb == 0: destroying every spare still leaves him exactly able to
// fulfil the order, so we also need one bauble of real shortfall. Take the
// colour with the smaller surplus -- but only a colour the order actually
// asks for, since destroying reds is pointless when rp == 0.
ll red = (rp >= 1 ? ro - rp : INF);
ll blue = (bp >= 1 ? bo - bp : INF);
cout << s + 1 + min(red, blue) << "\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. Cookies¶
Statement. Factory 0 makes \(C_0\) cookies a day. You may buy factory 1 (costs \(P_1\) cookies, adds \(C_1\) per day) and factory 2 (\(P_2\), \(C_2\)), each at most once, paying after a day's production. Maximise cookies after \(D\) days.
Idea. There are only five plans: buy nothing, only 1, only 2, 1 then 2, 2 then 1. In each plan, buying a factory as soon as you can afford it is best (more days of extra production). Simulate each plan for \(D \le 10^4\) days and take the best.
Cookies.cpp
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Simulate a given buying plan: buy the listed factories in order, each as soon
// as it is affordable (which is always optimal). Return cookies after d days.
ll simulate(int d, ll c0, vector<pair<ll, ll>> plan) {
ll cookies = 0, rate = c0;
int idx = 0;
for (int day = 0; day < d; day++) {
cookies += rate;
while (idx < (int) plan.size() && cookies >= plan[idx].first) {
cookies -= plan[idx].first;
rate += plan[idx].second;
idx++;
}
}
return cookies;
}
// Only five plans exist: buy nothing, buy one, or buy both in either order.
void solve() {
int d;
ll c0;
cin >> d >> c0;
ll p1, c1, p2, c2;
cin >> p1 >> c1;
cin >> p2 >> c2;
pair<ll, ll> f1 = {p1, c1}, f2 = {p2, c2};
ll ans = 0;
ans = max(ans, simulate(d, c0, {}));
ans = max(ans, simulate(d, c0, {f1}));
ans = max(ans, simulate(d, c0, {f2}));
ans = max(ans, simulate(d, c0, {f1, f2}));
ans = max(ans, simulate(d, c0, {f2, f1}));
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. Ghost Encounters¶
Statement. Tulpa leaves at time \(s\) (any integer, maybe negative) and walks so that she reaches position \(x\) at time \(s + Kx\). Ghost \(i\) appears at position \(X_i\) exactly at time \(T_i\). Choose \(s\) to meet as many ghosts as possible.
Idea. Meeting ghost \(i\) means \(s + KX_i = T_i\), i.e. \(s = T_i - KX_i\). Every ghost fixes one value of \(s\), so the answer is how often the most common value of \(T_i - KX_i\) occurs. Count with a map<ll, int>.
Ghost Encounters.cpp
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Tulpa reaches location x at time s + k*x. She meets ghost i iff s + k*Xi == Ti,
// i.e. s == Ti - k*Xi. So each ghost pins one value of s; the answer is the most
// common value of Ti - k*Xi.
void solve() {
int n;
ll k;
cin >> n >> k;
map<ll, int> cnt;
int ans = 0;
for (int i = 0; i < n; i++) {
ll x, t;
cin >> x >> t;
ll s = t - k * x;
cnt[s]++;
ans = max(ans, cnt[s]);
}
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. Tennis Robot¶
Statement. \(B\) bins have capacities \(A_i\). A robot passes over bins \(1..B\) again and again, dropping one ball into every bin that is not full. Which bin gets the \(N\)-th ball? (\(N, A_i \le 10^9\).)
Idea.
- After \(r\) full passes bin \(i\) holds \(\min(A_i, r)\) balls, so \(f(r) = \sum_i \min(A_i, r)\) balls have been dropped. \(f\) never decreases.
- Binary search the smallest \(r\) with \(f(r) \ge N\): the \(N\)-th ball falls in pass \(r\).
- Before that pass, \(f(r-1)\) balls were dropped, so we need the \((N - f(r-1))\)-th drop of pass \(r\). In pass \(r\) only bins with \(A_i \ge r\) receive a ball; count through them in order.
\(O(B \log \max A)\).
Tennis Robot.cpp
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// After r full passes, bin i holds min(a_i, r) balls, so f(r) = sum min(a_i, r)
// balls are placed. Binary search the pass r in which the Nth ball lands, then
// scan that pass to find which not-yet-full bin gets it.
void solve() {
int b;
ll n;
cin >> b >> n;
vector<ll> a(b);
for (int i = 0; i < b; i++) {
cin >> a[i];
}
ll lo = 1, hi = 0;
for (ll x: a) {
hi = max(hi, x);
}
while (lo < hi) {
ll mid = (lo + hi) / 2;
ll f = 0;
for (ll x: a) {
f += min(x, mid);
}
if (f >= n) {
hi = mid;
} else {
lo = mid + 1;
}
}
ll r = lo;
ll before = 0;
for (ll x: a) {
before += min(x, r - 1);
}
ll need = n - before; // index of the wanted ball within pass r
for (int i = 0; i < b; i++) {
if (a[i] >= r) { // bin i is not full at the start of pass r
need--;
if (need == 0) {
cout << i + 1 << "\n";
return;
}
}
}
}
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. Ladybugs II¶
Statement. \(N\) ladybugs sit at sorted positions. For each of \(Q\) queries starting at position \(D\), find the least walking distance to collect \(K\) different ladybugs' signatures.
Idea.
- You collect everything you walk past, so the \(K\) ladybugs are always a contiguous block \([L, R]\) of the sorted order. Its cost from \(D\) is \((R - L) + \min(|D - L|, |D - R|)\).
- Trying all blocks per query is \(O(NQ)\).
- Blocks entirely to the right of \(D\): the first one is best (cost \(R - D\)); entirely to the left: the last one (cost \(D - L\)). Both are found by binary search.
- For blocks containing \(D\) the cost is \(\min(D + (R - 2L),\ -D + (2R - L))\). Precompute \(R - 2L\) and \(2R - L\) per block; the blocks containing \(D\) form a contiguous index range, so a sparse table gives each minimum in \(O(1)\).
\(O((N + Q) \log N)\), checked against brute force on 50 000 random cases.
Ladybugs II.cpp
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Sparse table for range minimum.
struct RMQ {
vector<vector<ll>> t;
vector<int> lg;
void build(vector<ll> &a) {
int n = a.size();
lg.assign(n + 1, 0);
for (int i = 2; i <= n; i++) {
lg[i] = lg[i / 2] + 1;
}
int levels = lg[n] + 1;
t.assign(levels, vector<ll>(n));
t[0] = a;
for (int j = 1; j < levels; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
t[j][i] = min(t[j - 1][i], t[j - 1][i + (1 << (j - 1))]);
}
}
}
ll qry(int l, int r) {
if (l > r) {
return LLONG_MAX;
}
int j = lg[r - l + 1];
return min(t[j][l], t[j][r - (1 << j) + 1]);
}
};
// You always collect a contiguous block of K ladybugs. For a block with ends
// L (=p[i]) and R (=p[i+K-1]), starting at drop point d the time is
// (R-L) + min(|d-L|, |d-R|). We minimise over all blocks per query.
// If d is between L and R this equals min(d + (R-2L), -d + (2R-L)); combined with
// range-min sparse tables over those two expressions this answers each query in
// O(log n). Blocks entirely left/right of d are two extra binary-searched cases.
void solve() {
int n, k, q;
cin >> n >> k >> q;
vector<ll> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
}
int m = n - k; // last valid block start index
vector<ll> L(m + 1), R(m + 1), A(m + 1), B(m + 1);
for (int i = 0; i <= m; i++) {
L[i] = p[i];
R[i] = p[i + k - 1];
A[i] = R[i] - 2 * L[i];
B[i] = 2 * R[i] - L[i];
}
RMQ ra, rb;
ra.build(A);
rb.build(B);
for (int query = 0; query < q; query++) {
ll d;
cin >> d;
ll ans = LLONG_MAX;
// block entirely right of d: first i with L[i] >= d, cost R[i]-d
{
int lo = 0, hi = m, res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (L[mid] >= d) {
res = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
if (res >= 0) {
ans = min(ans, R[res] - d);
}
}
// block entirely left of d: last i with R[i] <= d, cost d-L[i]
{
int lo = 0, hi = m, res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (R[mid] <= d) {
res = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
if (res >= 0) {
ans = min(ans, d - L[res]);
}
}
// blocks straddling d: i in [imin, imax]
int imax;
{
int lo = 0, hi = m, res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (L[mid] <= d) {
res = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
imax = res;
}
int imin;
{
int lo = 0, hi = m, res = m + 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (R[mid] >= d) {
res = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
imin = res;
}
int lo = max(0, imin), hi = min(m, imax);
if (lo <= hi) {
ans = min(ans, min(d + ra.qry(lo, hi), -d + rb.qry(lo, hi)));
}
cout << ans << (query + 1 < q ? ' ' : '\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;
}
6. Beach Umbrellas¶
Statement. A beach has \(N\) segments; \(U\) umbrellas already cover intervals \([A_i, B_i]\). You have \(K\) more umbrellas, each covering \(X\) consecutive segments. Find the longest run of consecutive covered segments you can make.
Idea.
- Merge the existing umbrellas into disjoint covered intervals.
- Checking a run \([l, r]\): from \(l\), jump to the first uncovered segment \(q\), put an umbrella on \([q, q + X - 1]\), continue after it, until you pass \(r\). Placing each umbrella as far left as necessary is optimal. Careful: one umbrella can cover the gap on both sides of a narrow covered strip, so you cannot just add \(\lceil \text{gap} / X \rceil\) per gap.
- For a fixed left end the covered run only grows with more umbrellas, so binary search the farthest \(r\).
In class (file below) we kept everything at the level of merged intervals (memory \(O(U)\), long long everywhere since \(N\) is up to \(10^9\)) and handled \(X = 1\) with a prefix count of uncovered segments. This scores the first four subtasks (88 points); the last subtask needs only \(O(U)\) candidate left ends instead of all \(N\).
20_6.cpp
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
ll n, k, x;
int u;
cin >> n >> u >> k >> x;
vector<pair<int, int> > segments(u);
for (int i = 0; i < u; i++) {
cin >> segments[i].first >> segments[i].second;
}
std::sort(segments.begin(), segments.end());
vector<pair<int, int> > seg;
int l = segments[0].first;
int r = segments[0].second;
for (int i = 1; i < u; i++) {
int p = segments[i].first;
int q = segments[i].second;
if (p > r + 1) {
seg.push_back({l, r});
l = p;
r = q;
} else {
r = max(r, q);
}
}
seg.push_back({l, r});
int m = seg.size();
if (k == 0) {
ll ans = 0;
for (int i = 0; i < m; i++) {
ans = max(ans, (ll) seg[i].second - seg[i].first + 1);
}
cout << ans;
return;
}
// pref[i] = number of covered positions inside seg[0..i-1]
vector<ll> pref(m + 1);
for (int i = 0; i < m; i++) {
pref[i + 1] = pref[i] + (seg[i].second - seg[i].first + 1);
}
// index of the last segment with l <= p, or -1
auto find_seg = [&](ll p)-> int {
int lo = 0, hi = m - 1, res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (seg[mid].first <= p) {
res = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return res;
};
// number of covered positions in [1, p]
auto covered = [&](ll p)-> ll {
int i = find_seg(p);
if (i < 0) return 0;
return pref[i] + min((ll) seg[i].second, p) - seg[i].first + 1;
};
// leftmost position >= p that is NOT covered
auto next_free = [&](ll p)-> ll {
int i = find_seg(p);
if (i < 0) return p;
if (p <= seg[i].second) return seg[i].second + 1;
return p;
};
auto check = [&](ll L, ll R)-> bool {
// return true when [L,R] can be fully covered using at most k extra umbrellas
if (x == 1) {
ll need = (R - L + 1) - (covered(R) - covered(L - 1));
return need <= k;
}
ll p = L, cnt = 0;
while (p <= R) {
ll q = next_free(p);
if (q > R) return true;
cnt++;
if (cnt > k) return false;
p = q + x;
}
return true;
};
ll ans = 0;
for (ll L = 1; L <= n; L++) {
// binary search for R
ll lo = L, hi = n, R = 0;
while (lo <= hi) {
ll mid = (lo + hi) / 2;
if (check(L, mid)) {
R = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
if (R >= L) {
ans = max(ans, R - L + 1);
}
}
cout << ans;
}
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;
}
The prepared version is simpler, \(O(N \cdot K)\), and also covers \(N \le 10^5\):
Beach Umbrellas.cpp
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Mark covered segments, then slide the booked block. For every run-start l (a
// segment whose left neighbour is uncovered), greedily place up to K width-X
// umbrellas on the uncovered segments and see how far right the fully-covered
// run reaches. This is O(N*K) and covers N up to 100000 (the large-N subtask
// needs a gap-level speed-up instead).
void solve() {
int n, u;
ll k, x;
cin >> n >> u >> k >> x;
vector<char> cov(n + 2, 0);
for (int i = 0; i < u; i++) {
int a, b;
cin >> a >> b;
for (int s = a; s <= b; s++) {
cov[s] = 1;
}
}
// nxt[i] = smallest index >= i that is uncovered (n+1 if none)
vector<int> nxt(n + 2);
nxt[n + 1] = n + 1;
for (int i = n; i >= 1; i--) {
nxt[i] = cov[i] ? nxt[i + 1] : i;
}
ll best = 0;
for (int l = 1; l <= n; l++) {
if (l > 1 && cov[l - 1]) {
continue; // l is not the left edge of a run
}
ll reach = l - 1, cnt = 0;
int cur = l;
while (true) {
int uu = nxt[cur > n ? n + 1 : cur];
if (uu > n) {
reach = n; // no more uncovered segments
break;
}
if (cnt == k) {
reach = uu - 1; // out of umbrellas
break;
}
cnt++;
reach = uu + x - 1;
cur = uu + (int) x;
if (cur > n) {
reach = n;
break;
}
}
reach = min(reach, (ll) n);
best = max(best, reach - l + 1);
}
cout << best << "\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 2020 papers on ORAC (Australian Mathematics Trust); the Baubles fix was checked against the full-score reference in Australian-Informatics-Problems. Explanations and code are ours.