AIO 2019¶
AIO 2019 was our 22 August lesson. Two ideas run through the set: binary search on the answer (Q4, Q6) and exchange arguments (Q2, Q3). In class we wrote Evading Capture together; it has its own page, BFS with Parity States.
| # | Problem | Main idea | Difficulty | Related page |
|---|---|---|---|---|
| 1 | Vases | smallest case first, then construct | ★ | — |
| 2 | RPS | score \(= 2W + D - N\); wins first | ★★ | Greedy |
| 3 | Hiring Monks | two exchange arguments; split point | ★★★★ | Greedy, Two Pointers |
| 4 | Medusa's Snakes | binary search + greedy check | ★★★ | Binary Search |
| 5 | Evading Capture | BFS over (city, parity) | ★★★★ | BFS with Parity States |
| 6 | Lollipops, Sweets and Chocolates II | monotone total; binary search \(R\) | ★★★★★ | Binary Search |
Suggested order
Vases (5 minutes) → Medusa's Snakes (the cleanest binary search on the answer) → RPS (rewrite the score) → Evading Capture → Hiring Monks (most thinking per line) → Lollipops II (start from the brute force and let the monotonicity appear).
1. Vases¶
Statement. Put \(N\) identical flowers into three vases: use all flowers, at least one per vase, all three counts different. Print any way, or 0 0 0.
Idea. The smallest three different positive counts sum to \(1 + 2 + 3 = 6\), so \(N < 6\) is impossible. Otherwise 1 2 N-3 works because \(N - 3 \ge 3\). Find the extreme case before writing loops.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// The three smallest distinct positive counts are 1 + 2 + 3 = 6,
// so anything below 6 is impossible; otherwise 1, 2, n - 3 always works.
void solve() {
int n;
cin >> n;
if (n < 6) {
cout << "0 0 0\n";
return;
}
cout << 1 << " " << 2 << " " << n - 3 << "\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. RPS¶
Statement. \(N\) rounds of rock-paper-scissors. The opponent throws \(R_a\) rocks, then \(P_a\) papers, then \(S_a\) scissors. You must throw \(R_b\), \(P_b\), \(S_b\) of each in any order. A win is \(+1\), a loss \(-1\). Maximise the score.
Idea.
- Since you choose your order, only the six counts matter.
- With \(W\) wins, \(D\) draws and \(L\) losses, \(W + D + L = N\), so the score is \(W - L = 2W + D - N\). Maximise \(2W + D\).
- The three winning pairings (paper–rock, scissors–paper, rock–scissors) use different piles, so all can be maxed at once: \(W = \min(P_b, R_a) + \min(S_b, P_a) + \min(R_b, S_a)\).
- Giving up a win frees one throw on each side, which buys at most two draws: \(-2 + 2 = 0\). So wins first never loses. Then make as many draws as possible; the rest are losses.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// The opponent's order does not matter, only how many of each throw they make.
// Score = wins - losses. Grab every win first (the three winning pairs use
// disjoint piles, so they never compete), then soak up the rest with draws.
// Giving up one win frees one throw on each side, which buys at most two
// draws, so the trade is never profitable.
void solve() {
int n;
cin >> n;
// index 0 = rock, 1 = paper, 2 = scissors
vector<int> a(3), b(3);
for (int i = 0; i < 3; i++) {
cin >> a[i];
}
for (int i = 0; i < 3; i++) {
cin >> b[i];
}
int win = 0;
for (int i = 0; i < 3; i++) {
// my throw i beats their throw (i + 2) % 3
int j = (i + 2) % 3;
int c = min(b[i], a[j]);
win += c;
b[i] -= c;
a[j] -= c;
}
int draw = 0;
for (int i = 0; i < 3; i++) {
int c = min(b[i], a[i]);
draw += c;
b[i] -= c;
a[i] -= c;
}
cout << 2 * win + draw - n << "\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. Hiring Monks¶
Statement. \(N\) monks have skills \(x_i\). There are \(S\) student jobs (job \(j\) needs skill \(\le s_j\)) and \(M\) master jobs (job \(k\) needs skill \(\ge m_k\)). Each monk takes at most one job and each job at most one monk. Maximise the number of hired monks.
Idea.
- Weak students, strong masters. If a strong monk has a student job and a weak monk a master job, swapping them keeps both valid. So some optimal answer has every student weaker than every master.
- No gaps. An unhired monk weaker than some student can replace that student; similarly on the master side.
- So after sorting the monks there is a split point \(p\): monks \([0, p)\) compete for student jobs, \([p, N)\) for master jobs. Try every \(p\).
f[p]= best student matching among the first \(p\) monks: give each monk (in increasing skill) the smallest job that fits, with a pointer over sorted jobs.g[p]= the same for masters from the strongest monk down. Answer \(\max_p (f[p] + g[p])\).
\(O(N \log N)\) for sorting. \(S\) or \(M\) can be \(0\).
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Exchange argument: if a weak monk takes a master job and a strong monk takes
// a student job, swapping them is still legal. So some optimal answer sends a
// prefix of the sorted monks to student jobs and the matching suffix to master
// jobs. f[p] = best student matching using monks 0..p-1 (greedy, smallest job
// that fits), g[p] = best master matching using monks p..n-1. Answer = max sum.
void solve() {
int n;
cin >> n;
vector<int> x(n);
for (int i = 0; i < n; i++) {
cin >> x[i];
}
int sn;
cin >> sn;
vector<int> s(sn);
for (int i = 0; i < sn; i++) {
cin >> s[i];
}
int mn;
cin >> mn;
vector<int> m(mn);
for (int i = 0; i < mn; i++) {
cin >> m[i];
}
sort(x.begin(), x.end());
sort(s.begin(), s.end());
sort(m.begin(), m.end());
vector<int> f(n + 1, 0), g(n + 1, 0);
int j = 0, cur = 0;
for (int i = 0; i < n; i++) {
while (j < sn && s[j] < x[i]) {
j++;
}
if (j < sn) {
cur++;
j++;
}
f[i + 1] = cur;
}
int k = mn - 1;
cur = 0;
for (int i = n - 1; i >= 0; i--) {
while (k >= 0 && m[k] > x[i]) {
k--;
}
if (k >= 0) {
cur++;
k--;
}
g[i] = cur;
}
int ans = 0;
for (int p = 0; p <= n; p++) {
ans = max(ans, f[p] + g[p]);
}
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. Medusa's Snakes¶
Statement. A snake's DNA is a string of S N A K E letters. It has venom level \(x\) if it is exactly \(x\) S, then \(x\) N, \(x\) A, \(x\) K, \(x\) E. You may delete any letters. Maximise the venom level.
Idea.
- If level \(x\) is possible, so is \(x - 1\) (delete one letter from each block): binary search the largest \(x\) in \([0, N/5]\).
check(x): scan once, take the first \(x\)S, then the next \(x\)Nafter that, and so on. Taking letters as early as possible never leaves less room for later blocks.
The answer can be \(0\) (KANSAS). The code uses our "largest valid value" template.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Feasibility is monotone in x (drop one of each letter), so binary search for
// the largest valid x. The check greedily takes the earliest letters: finishing
// a block sooner never leaves less room for the blocks after it.
void solve() {
int n;
string t;
cin >> n >> t;
string p = "SNAKE";
auto check = [&](int x) -> bool {
int i = 0;
for (int c = 0; c < 5; c++) {
int need = x;
while (i < n && need > 0) {
if (t[i] == p[c]) {
need--;
}
i++;
}
if (need > 0) {
return false;
}
}
return true;
};
int l = 0, r = n / 5, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1; // mid works, try bigger
} else {
r = mid - 1;
}
}
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. Evading Capture¶
Statement. From city \(X\) make exactly \(K\) hops along roads (\(K \le 10^9\)). How many cities can you finish in?
Idea. You can waste hops two at a time by walking to a neighbour and back, so a city is reachable in exactly \(K\) hops iff its shortest walk with the same parity as \(K\) is at most \(K\). Run BFS over states (city, parity). The full explanation, a trace of sample 1 and the code we wrote in class are on BFS with Parity States.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// A walk of length exactly k ending at v exists iff we can reach v by a walk of
// length d <= k with d = k (mod 2): the spare k - d steps are burned by
// bouncing back and forth along one incident edge. So BFS over states
// (city, parity) and count cities whose distance of the right parity is <= k.
void solve() {
int n, e, x;
ll k;
cin >> n >> e >> x >> k;
vector<vector<int>> g(n + 1);
for (int i = 0; i < e; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
const int INF = INT_MAX;
vector<vector<int>> d(n + 1, vector<int>(2, INF));
d[x][0] = 0;
queue<pair<int, int>> q;
q.push({x, 0});
while (!q.empty()) {
int u = q.front().first, p = q.front().second;
q.pop();
for (int v : g[u]) {
if (d[v][p ^ 1] == INF) {
d[v][p ^ 1] = d[u][p] + 1;
q.push({v, p ^ 1});
}
}
}
int p = (int) (k % 2);
int ans = 0;
for (int v = 1; v <= n; v++) {
if (d[v][p] != INF && d[v][p] <= k) {
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;
}
6. Lollipops, Sweets and Chocolates II¶
Statement. A street has blocks \(1..L\), \(N\) shops and \(M\) houses at distinct positions. Each house got a leaflet saying how many shops are within walking distance \(R\) of it. The leaflets were shuffled, so you only know the multiset of numbers. Find a possible \(R\) (\(0 \le R \le L\)), or \(-1\).
Idea.
- Checking one \(R\): compute every house's true count (two binary searches over sorted shops: shops in \([h - R, h + R]\)), sort, and compare with the sorted leaflets. The shuffle disappears once both lists are sorted.
- Monotone: a larger \(R\) never decreases any house's count, so the total never decreases either.
- Binary search the smallest \(R\) whose total reaches the leaflet total. If that total overshoots, no \(R\) hits it exactly: \(-1\). Otherwise check this \(R\).
- Why one check is enough: if two values \(R < R'\) have the same total, no house's count changed in between (any change would raise the total), so they give identical lists. All \(R\) with the right total succeed or fail together.
In sample 1 both \(R = 3\) and \(R = 4\) give counts \(2, 3, 3, 2, 0\), which is why the statement accepts either.
long long
The total can reach \(M \cdot N = 10^{10}\), and \(h - R\) can be negative.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll> shop;
// How many shops lie within distance r of block h.
int cntAt(ll h, ll r) {
int hi = (int) (upper_bound(shop.begin(), shop.end(), h + r) - shop.begin());
int lo = (int) (lower_bound(shop.begin(), shop.end(), h - r) - shop.begin());
return hi - lo;
}
// Every house's count is non-decreasing in r, so the total is too. Binary
// search the smallest r whose total reaches the pamphlet total. Equal totals
// force equal sorted count vectors, so any other r is hopeless -- we only have
// to verify this one.
void solve() {
int n, m;
ll l;
cin >> n >> m >> l;
shop.assign(n, 0);
for (int i = 0; i < n; i++) {
cin >> shop[i];
}
vector<ll> h(m);
for (int i = 0; i < m; i++) {
cin >> h[i];
}
vector<int> s(m);
ll need = 0;
for (int i = 0; i < m; i++) {
cin >> s[i];
need += s[i];
}
sort(shop.begin(), shop.end());
sort(s.begin(), s.end());
ll lo = 0, hi = l;
while (lo < hi) {
ll mid = lo + (hi - lo) / 2;
ll sum = 0;
for (int i = 0; i < m; i++) {
sum += cntAt(h[i], mid);
}
if (sum >= need) {
hi = mid;
} else {
lo = mid + 1;
}
}
vector<int> got(m);
for (int i = 0; i < m; i++) {
got[i] = cntAt(h[i], lo);
}
sort(got.begin(), got.end());
if (got == s) {
cout << lo << "\n";
} else {
cout << -1 << "\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 2019 papers on ORAC (Australian Mathematics Trust). ORAC now uses standard input/output for these problems; the originals used files. Explanations and code are ours; RPS, Hiring Monks, Medusa's Snakes and Lollipops II were checked against brute force on thousands of random cases.