AIO 2018¶
AIO 2018 was part of our 23 August lesson. That year had overlapping Intermediate and Senior papers, so there are only five different problems: Intermediate had Street Construction, Castle Cavalry, Cloud Coverage and Janitor; Senior had Street Construction, Cloud Coverage, Janitor and Detective.
| # | Problem | Main idea | Difficulty | Related page |
|---|---|---|---|---|
| 1 | Street Construction | split evenly, round up | ★ | — |
| 2 | Castle Cavalry | count per requested size | ★★ | — |
| 3 | Cloud Coverage | prefix positions, fixed window minimum | ★★★ | Prefix Sum, Two Pointers |
| 4 | Janitor | count local maxima; update 5 cells | ★★★ | — |
| 5 | Detective | same/different edges, 2-colouring, test each thief | ★★★★★ | Graph Basics, DSU |
Suggested order
Street Construction (a formula), Castle Cavalry (one good question cracks it), Cloud Coverage (the strict inequality), then Janitor: write the slow version first, then notice only 5 cells change. Detective: aim for the 60-point version.
1. Street Construction¶
Statement. A street has \(N\) plots; exactly \(K\) become parks and the rest houses. A block is a maximal run of houses. Place the parks to make the largest block as small as possible.
Idea. \(K\) parks cut the street into \(K + 1\) gaps (some may be empty) holding the \(N - K\) houses however we like. Spread them evenly: \(\lceil (N - K) / (K + 1) \rceil\), computed as (h + g - 1) / g without floating point.
Samples: 3 1 → \(\lceil 2/2 \rceil = 1\); 3 3 → \(0\); 7 2 → \(\lceil 5/3 \rceil = 2\).
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// K parks cut the street into exactly K + 1 gaps (some may be empty), and the
// N - K houses can be spread over those gaps however we like. Spreading them as
// evenly as possible gives the smallest largest block: ceil((N - K) / (K + 1)).
void solve() {
ll n, k;
cin >> n >> k;
ll h = n - k;
ll g = k + 1;
cout << (h + g - 1) / g << "\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. Castle Cavalry¶
Statement. Knight \(i\) only wants to be in a squad of exactly \(a_i\) knights. Can every knight be made happy?
Idea. Ask: can a knight who wants size 2 share a squad with one who wants size 3? No: all members of a squad want its size. So knights wanting size \(v\) only group among themselves, and each squad takes exactly \(v\) of them. Answer YES iff, for every \(v\), the number of knights wanting \(v\) is a multiple of \(v\).
2 3 2 3 3 → two want 2, three want 3: YES. 2 2 2 → three want 2: NO.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Knights that ask for size v can only ever share a squad with each other, and
// every squad they form holds exactly v of them. So the answer is YES iff the
// number of knights asking for v is a multiple of v, for every v.
void solve() {
int n;
cin >> n;
vector<int> cnt(n + 1, 0);
for (int i = 0; i < n; i++) {
int a;
cin >> a;
cnt[a]++;
}
for (int v = 1; v <= n; v++) {
if (cnt[v] % v != 0) {
cout << "NO\n";
return;
}
}
cout << "YES\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. Cloud Coverage¶
Statement. \(N\) people stand on a line; the \(N - 1\) gaps between neighbours are given. A cloud covered at most \(K\) people at any moment, where people exactly a cloud-length apart can not both be covered. What is the longest the cloud could be?
Idea.
- Positions are prefix sums of the gaps:
3 6 4 2 5→ \(0, 3, 9, 13, 15, 20\). - A cloud of length \(L\) covers people \(i..j\) exactly when \(p_j - p_i < L\) (strictly).
- Covering \(K + 1\) people must be impossible, so for every window of \(K + 1\) consecutive people, \(L \le p_{i+K} - p_i\).
- The answer is the smallest such span, i.e. the smallest sum of \(K\) consecutive gaps: a fixed-length sliding window.
Sample (\(K = 3\)): spans \(13, 12, 11\), answer \(11\).
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// A cloud of length L covers people i..j only when p[j] - p[i] < L, so a window
// of K + 1 people is safe exactly when L <= their span. The cloud must dodge
// every window of K + 1 people at once, so the answer is the smallest such span:
// min over i of p[i + K] - p[i], i.e. the smallest sum of K consecutive gaps.
void solve() {
int n, k;
cin >> n >> k;
vector<ll> d(n - 1);
for (int i = 0; i < n - 1; i++) {
cin >> d[i];
}
ll sum = 0;
for (int i = 0; i < k; i++) {
sum += d[i];
}
ll ans = sum;
for (int i = k; i < n - 1; i++) {
sum += d[i] - d[i - k];
ans = min(ans, sum);
}
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. Janitor¶
Statement. An \(R \times C\) floor has heights (neighbours never equal). Water poured on a tile flows to strictly lower neighbours. Find the fewest tiles to pour on so every tile gets wet, and answer again after each of \(Q\) height changes.
Idea.
- A tile with a higher neighbour gets water from that neighbour. A tile with no higher neighbour (a local maximum) can only be wet by pouring on it.
- Pouring on every local maximum is enough: from any tile, keep stepping to a higher neighbour; heights strictly increase, so you end at a local maximum, whose water flows back down that path.
- So the answer is the number of local maxima.
- Updates: changing one height can only change whether that tile and its 4 neighbours are local maxima. Subtract those 5 before the change, add them back after: \(O(1)\) per update.
Writing the full recount after every update first (\(O(QRC)\)) already earns a subtask; spotting "only 5 cells change" gives full marks. The same incremental update idea appears in Detective.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int r, c;
vector<vector<int>> g;
// A tile with a higher neighbour is reached from that neighbour, so we never
// have to pour on it. A tile with no higher neighbour (a local maximum) can
// only be wet by pouring on it. So the answer is the number of local maxima.
bool peak(int x, int y) {
if (x < 0 || x >= r || y < 0 || y >= c) {
return false;
}
if (x > 0 && g[x - 1][y] > g[x][y]) {
return false;
}
if (x + 1 < r && g[x + 1][y] > g[x][y]) {
return false;
}
if (y > 0 && g[x][y - 1] > g[x][y]) {
return false;
}
if (y + 1 < c && g[x][y + 1] > g[x][y]) {
return false;
}
return true;
}
void solve() {
int q;
cin >> r >> c >> q;
g.assign(r, vector<int>(c, 0));
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cin >> g[i][j];
}
}
int ans = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (peak(i, j)) {
ans++;
}
}
}
cout << ans << "\n";
// One height change can only flip the tile itself and its four neighbours.
vector<int> dx = {0, -1, 1, 0, 0};
vector<int> dy = {0, 0, 0, -1, 1};
for (int t = 0; t < q; t++) {
int x, y, h;
cin >> x >> y >> h;
x--;
y--;
for (int k = 0; k < 5; k++) {
if (peak(x + dx[k], y + dy[k])) {
ans--;
}
}
g[x][y] = h;
for (int k = 0; k < 5; k++) {
if (peak(x + dx[k], y + dy[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;
}
5. Detective¶
Statement. Exactly one of \(N\) children stole the cookies. Each child is honest (always true) or a liar (always false). \(M\) statements: A B 1 "B is honest", A B 2 "B is a liar", A B 3 "B stole the cookies". List every child who could be the thief in increasing order, or MISTAKE if none.
Idea.
- Type 1 and 2 are relations. "A says B is honest": if A is honest, B is honest; if A lies, B lies. Either way A and B are the same kind. Type 2 means different kinds.
- Colour each connected component like a bipartite check (same kind = same colour). A contradiction means
MISTAKE. Inside a component, choosing the kind of one child fixes everyone: two possible states per component. - Fix a thief \(t\). Statement
A B 3is true iff \(B = t\), so A must be honest if \(B = t\) and a liar otherwise. That forces A's component into one state. \(t\) works iff no component is forced both ways. - 60 points: run that check for every \(t\): \(O(N \cdot M)\), fine for \(N, M \le 1000\).
- Full marks: start from the baseline "no accused child is the thief" (every accuser lies). Switching to thief \(t\) only flips the statements that accuse \(t\). Update the per-component counts for those, test, and flip back. Over all \(t\) each statement is flipped once: \(O(N + M)\).
We first wrote this with a DSU with parity, then rewrote it with plain DFS colouring, which is easier to follow. The 60-point version (use this one in class):
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// 60-point version: subtasks 1 + 2 + 3.
// Same idea as the full solution, but instead of updating incrementally we just
// rerun the whole check for every candidate thief. O(N * M), fine for N, M <= 1000.
void solve() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n + 1);
vector<int> sa, sb;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
if (c == 3) {
sa.push_back(a);
sb.push_back(b);
} else {
int w = (c == 1 ? 0 : 1);
g[a].push_back({b, w});
g[b].push_back({a, w});
}
}
// Colour every component: col[v] says whether v matches its root's kind.
vector<int> col(n + 1, 0), cmp(n + 1, -1);
int nc = 0;
for (int s = 1; s <= n; s++) {
if (cmp[s] != -1) {
continue;
}
cmp[s] = nc;
vector<int> st = {s};
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (int i = 0; i < (int) g[u].size(); i++) {
int v = g[u][i].first, w = g[u][i].second;
if (cmp[v] == -1) {
cmp[v] = nc;
col[v] = col[u] ^ w;
st.push_back(v);
} else if (col[v] != (col[u] ^ w)) {
cout << "MISTAKE\n";
return;
}
}
}
nc++;
}
int k = (int) sa.size();
vector<int> ans;
vector<int> st(nc);
for (int t = 1; t <= n; t++) {
// st[c] = -1 means the component is still free to pick either colour.
for (int c = 0; c < nc; c++) {
st[c] = -1;
}
bool ok = true;
for (int i = 0; i < k && ok; i++) {
// Accuser sa[i] is honest exactly when the person it accuses is t.
int h = (sb[i] == t ? 1 : 0);
int want = h ^ col[sa[i]];
int c = cmp[sa[i]];
if (st[c] == -1) {
st[c] = want;
} else if (st[c] != want) {
ok = false;
}
}
if (ok) {
ans.push_back(t);
}
}
if (ans.empty()) {
cout << "MISTAKE\n";
return;
}
for (int v : ans) {
cout << v << "\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;
}
The full solution:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// "A says B is honest" makes A and B the same kind: if A is honest the claim is
// true, if A lies the claim is false and B lies too. "A says B is a liar" makes
// them different kinds. So these statements are just same/different edges, and
// we 2-colour every component like a bipartite check.
//
// "A says B stole it" pins A once we fix the thief t: A is honest if B == t and
// a liar otherwise. Within a component every honesty follows from one colour
// choice, so each accuser demands one of the two choices, and t works iff no
// component gets both demanded.
//
// Baseline: assume nobody accused is the thief, so every accuser is a liar.
// Moving to a real candidate t only flips the accusers who accuse t, and over
// all t that is M flips total, so all candidates cost O(N + M) together.
void solve() {
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n + 1);
vector<int> sa, sb;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
if (c == 3) {
sa.push_back(a);
sb.push_back(b);
} else {
int w = (c == 1 ? 0 : 1);
g[a].push_back({b, w});
g[b].push_back({a, w});
}
}
// col[v] = 0/1 relative to the root of its component, cmp[v] = component id.
vector<int> col(n + 1, 0), cmp(n + 1, -1);
int nc = 0;
for (int s = 1; s <= n; s++) {
if (cmp[s] != -1) {
continue;
}
cmp[s] = nc;
col[s] = 0;
vector<int> st = {s};
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (int i = 0; i < (int) g[u].size(); i++) {
int v = g[u][i].first, w = g[u][i].second;
if (cmp[v] == -1) {
cmp[v] = nc;
col[v] = col[u] ^ w;
st.push_back(v);
} else if (col[v] != (col[u] ^ w)) {
cout << "MISTAKE\n";
return;
}
}
}
nc++;
}
int k = (int) sa.size();
vector<vector<int>> byb(n + 1);
for (int i = 0; i < k; i++) {
byb[sb[i]].push_back(i);
}
// Baseline: every accuser is a liar, so it demands colour col[A].
vector<int> c0(nc, 0), c1(nc, 0);
for (int i = 0; i < k; i++) {
if (col[sa[i]] == 0) {
c0[cmp[sa[i]]]++;
} else {
c1[cmp[sa[i]]]++;
}
}
int bad = 0;
for (int c = 0; c < nc; c++) {
if (c0[c] > 0 && c1[c] > 0) {
bad++;
}
}
vector<int> stamp(nc, 0), touched;
vector<int> ans;
for (int t = 1; t <= n; t++) {
touched.clear();
for (int id : byb[t]) {
int c = cmp[sa[id]];
if (stamp[c] != t) {
stamp[c] = t;
touched.push_back(c);
bad -= (c0[c] > 0 && c1[c] > 0);
}
}
// These accusers now tell the truth, so they demand the other colour.
for (int id : byb[t]) {
int c = cmp[sa[id]];
if (col[sa[id]] == 0) {
c0[c]--;
c1[c]++;
} else {
c1[c]--;
c0[c]++;
}
}
for (int c : touched) {
bad += (c0[c] > 0 && c1[c] > 0);
}
if (bad == 0) {
ans.push_back(t);
}
for (int c : touched) {
bad -= (c0[c] > 0 && c1[c] > 0);
}
for (int id : byb[t]) {
int c = cmp[sa[id]];
if (col[sa[id]] == 0) {
c0[c]++;
c1[c]--;
} else {
c1[c]++;
c0[c]--;
}
}
for (int c : touched) {
bad += (c0[c] > 0 && c1[c] > 0);
}
}
if (ans.empty()) {
cout << "MISTAKE\n";
return;
}
for (int v : ans) {
cout << v << "\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;
}
Both versions were checked against brute force over all \(2^N\) honesty assignments on 3000 random small cases.
Credits & sources
Statements summarised from the official AIO 2018 papers on ORAC (Australian Mathematics Trust); the first four solutions were checked against the full-score references in Australian-Informatics-Problems. Explanations and code are ours.