AIO 2026¶
The Australian Informatics Olympiad 2026 was held on 27 August 2026. We went through the whole paper on 12 September, right after it was released on ORAC.
| # | Problem | Main idea | Difficulty | Related page |
|---|---|---|---|---|
| 1 | Jump on Platforms | largest gap between neighbours | ★ | — |
| 2 | IGM | a rotated sorted circle has exactly one drop | ★★ | — |
| 3 | Discount Destinations | fixed-length sliding window | ★★ | Two Pointers |
| 4 | Sunday Drive II | two sweeps, take the smaller bound | ★★★ | — |
| 5 | Prime Minister | binary search on the median | ★★★ | Binary Search |
| 6 | Mundane Square | greedy construction, feed the hungriest column | ★★★★★ | Greedy |
Suggested order
Q1 as a warm-up. Q2 trains turning a wordy condition into one property. Q3 is the sliding-window main course: write the \(O(NK)\) version first, then remove the repeated work. Q4 is the one most worth time: the "two sweeps" trick comes back again and again. Q5 drills the binary search template. Q6: understand the story in §6 first, code last.
All code below compiles, passes every official sample, and was timed on maximum-size inputs.
1. Jump on Platforms¶
Statement. \(N\) platforms stand at strictly increasing positions \(P_1 < \dots < P_N\). You must jump \(1 \to 2 \to \dots \to N\) without skipping any. What is the length of the longest jump you make?
Idea. There is no choice at all: jump \(i\) is \(P_{i+1} - P_i\). Take the maximum of the \(N - 1\) differences.
For 5 6 7 11 14 the jumps are \(1, 1, 4, 3\), so the answer is \(4\).
When there is nothing to choose
If the order of moves is forced, the problem is just "compute and take the max". Reading that out of the statement quickly is a skill too.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Jumps are only between neighbouring platforms, so the answer is the largest
// gap between two consecutive positions.
void solve() {
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
}
int ans = 0;
for (int i = 1; i < n; i++) {
ans = max(ans, p[i] - p[i - 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;
}
2. IGM¶
Statement. \(N\) delegates sit clockwise around a table; delegate \(i\) has importance \(A_i\) (all different). Pick someone to speak first; after that speakers go clockwise until everyone has spoken, and every speaker except the first must be strictly more important than the previous one. Is there a valid first speaker?
Idea.
- Starting somewhere and always going up means: cutting the circle at the start gives an increasing list.
- Walk once around an increasing list that was "bent into a circle": values go up everywhere except at one place, where the largest value is followed by the smallest.
- So count the positions \(i\) with \(A_i > A_{(i+1) \bmod N}\). Exactly one →
YES, otherwiseNO. (Since all values differ there is always at least one drop.)
Sample 1 8 16 1 2 4: \(8 \to 16\) up, \(16 \to 1\) down, \(1 \to 2 \to 4 \to 8\) up. One drop: YES (start at the 1). Sample 2 10 30 20: \(30 \to 20\) and \(20 \to 10\) are both drops: NO.
The pair that wraps around
Compare the last delegate with the first one: (i + 1) % n. Forgetting it breaks sample 2.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Walking clockwise from the start we must always go up, so the circle has to be
// a sorted list that was rotated. A rotated sorted circle has exactly one place
// where the next value is smaller (the wrap point), so just count the drops.
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int cnt = 0;
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
if (a[i] > a[j]) {
cnt++;
}
}
if (cnt == 1) {
cout << "YES\n";
} else {
cout << "NO\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. Discount Destinations¶
Statement. A trip lasts \(N\) days; day \(i\) normally costs \(A_i\). A new rule says that over any \(K\) consecutive days you pay at most \(D\) in total. Days are charged in order: on day \(i\) you pay the largest amount \(\le A_i\) that keeps the last \(K\) days (including today) within \(D\). How much do you pay in total?
Idea.
- The charging order is fixed, so this is a simulation, not an optimisation.
- Today's charge only depends on
win= the total charged on the previous \(K - 1\) days: charge \(\min(A_i, D - \texttt{win})\). - Recomputing
winby looping back costs \(O(K)\) per day, \(O(NK)\) in total, which matches the small subtask. - Keep
winas a sliding window: after charging day \(i\) add it, and remove the day that leaves the window. \(O(1)\) per day.
Sample 2 (\(K = 3\), \(D = 3\), \(A = 1\,2\,3\,2\,1\)):
| day | previous two days | cap \(D - \texttt{win}\) | \(A_i\) | paid |
|---|---|---|---|---|
| 1 | 0 | 3 | 1 | 1 |
| 2 | 1 | 2 | 2 | 2 |
| 3 | 1 + 2 = 3 | 0 | 3 | 0 |
| 4 | 2 + 0 = 2 | 1 | 2 | 1 |
| 5 | 0 + 1 = 1 | 2 | 1 | 1 |
Total \(5\).
long long for the total
Up to \(2\cdot10^5\) days of up to \(10^4\) each is \(2\cdot10^9\), past the int limit.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Simulate day by day. Keep win = what was charged on the previous K-1 days, so
// today's cap is D - win. A sliding window keeps that sum in O(1) per day.
void solve() {
int n, k, d;
cin >> n >> k >> d;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> c(n, 0);
int win = 0;
ll ans = 0;
for (int i = 0; i < n; i++) {
c[i] = min(a[i], d - win);
ans += c[i];
win += c[i];
if (i - k + 1 >= 0) {
win -= c[i - k + 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;
}
4. Sunday Drive II¶
Statement. A street is \(N\) km long and km \(i\) has a volume limit \(V_i\). The radio starts at volume \(0\). At the start of each kilometre you may change the volume by \(+1\), \(-1\) or \(0\); it must stay between \(0\) and the current limit. Your enjoyment is the sum of the volumes over all kilometres. Maximise it.
Idea.
- Think about each kilometre's highest possible volume \(u_i\) on its own. Two things hold it down.
- From the left: you start at \(0\) and rise by at most \(1\) per km, so \(u_i \le u_{i-1} + 1\). Sweep left to right:
u[i] = min(V[i], u[i-1] + 1). - From the right: a strict limit ahead forces you to turn down early, so \(u_i \le u_{i+1} + 1\). Sweep right to left:
u[i] = min(u[i], u[i+1] + 1). - The key point: after both sweeps, the list \(u\) is itself a legal drive (neighbours differ by at most \(1\), every limit respected). Every kilometre is at its own ceiling at the same time, so the sum of \(u\) is the maximum.
Sample 2 (\(V = 3\,3\,3\,3\,0\)): left sweep \(1, 2, 3, 3, 0\); right sweep fixes km 4 to \(\le 1\) and km 3 to \(\le 2\): \(1, 2, 2, 1, 0\), total \(6\).
Remember this shape
"Neighbours may differ by at most 1, each position has a cap" → one sweep from each side, take the minimum. It is the same pattern as "distance to the nearest 0".
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// The volume can change by at most 1 per kilometre and starts at 0, so the best
// level at km i is min over j of (v[j] + |i - j|), plus the start cap i itself.
// A left sweep handles coming up from 0, a right sweep handles coming down in
// time for a low limit ahead. Both bounds can be met at once, so just sum them.
void solve() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
vector<int> u(n);
int pre = 0;
for (int i = 0; i < n; i++) {
u[i] = min(v[i], pre + 1);
pre = u[i];
}
for (int i = n - 2; i >= 0; i--) {
u[i] = min(u[i], u[i + 1] + 1);
}
ll ans = 0;
for (int i = 0; i < n; i++) {
ans += u[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. Prime Minister¶
Statement. \(N\) citizens (\(N\) odd) have \(A_1 \le \dots \le A_N\) dollars. The Prime Minister hands out \(K\) dollars in total (non-negative whole amounts per person). Make the median as large as possible.
Idea.
- With 0-based index \(m = N / 2\), the median is
a[m]of the sorted list. - Money given to people before \(m\) is wasted: it cannot raise the middle value.
- For the median to be at least \(x\), everyone from \(m\) to the end must have at least \(x\). The cost is \(\sum_{i \ge m} \max(0, x - A_i)\).
- That cost grows with \(x\), so binary search the largest affordable \(x\) between \(A_m\) and \(A_m + K\).
Sample 1 (\(K = 4\), \(A = 1\,2\,5\,6\,9\), \(m = 2\)): \(x = 7\) costs \(2 + 1 + 0 = 3 \le 4\); \(x = 8\) costs \(3 + 2 + 0 = 5 > 4\). Answer \(7\).
Two traps
- This code uses the
while (lo < hi)form with an upper middlelo + (hi - lo + 1) / 2; with the lower middle,lo = midloops forever. Our usuall <= rtemplate withansavoids the question entirely. - Costs reach \(2\cdot10^5 \cdot 2\cdot10^9\): use
long long, and stop summing once the cost passes \(K\).
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// The median is the element at index m = n / 2 of the sorted list. To reach a
// median of x we must lift every citizen from m to the end up to x, and that
// cost only grows with x, so binary search the largest affordable x.
void solve() {
int n;
ll k;
cin >> n >> k;
vector<ll> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int m = n / 2;
ll lo = a[m], hi = a[m] + k;
while (lo < hi) {
ll mid = lo + (hi - lo + 1) / 2;
ll cost = 0;
for (int i = m; i < n && cost <= k; i++) {
if (a[i] < mid) {
cost += mid - a[i];
}
}
if (cost <= k) {
lo = mid;
} else {
hi = mid - 1;
}
}
cout << lo << "\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. Mundane Square¶
Statement. Build an \(N \times N\) grid of whole numbers between \(0\) and \(K\) whose row \(i\) sums to \(R_i\) and column \(j\) sums to \(C_j\), or say it is impossible. \(N \le 1000\).
6.1 Think of it as handing out money¶
Row \(i\) holds \(R_i\) dollars and must spend all of it; column \(j\) must receive exactly \(C_j\); the cell \((i, j)\) is how much row \(i\) gives column \(j\). The single difficulty: one row may give one column at most \(K\) dollars.
First check: counting all cells by rows gives \(\sum R\), by columns \(\sum C\). If they differ, NO (sample 3: \(7+0+3 = 10 \ne 11\)).
6.2 The easy version: \(K\) huge (30 points)¶
If the cap never matters, walk from the top-left cell: put \(\min(\text{row still has}, \text{column still needs})\), then step right if the column is satisfied or down if the row is spent. This northwest corner rule always finishes when the totals match. For \(R = (3, 2)\), \(C = (1, 4)\) it gives \(\begin{smallmatrix}1 & 2\\ 0 & 2\end{smallmatrix}\).
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Subtasks 1 and 2 (30 points): k is 1e9 while every r[i] and c[j] is at most
// 100, so the per-cell cap can never bite. Then the only thing that matters is
// sum(r) == sum(c), and the northwest corner rule builds a square: walk the
// grid top-left to bottom-right, always pour as much as the current row and
// column still want, then step off whichever of the two is now satisfied.
void solve() {
int n;
ll k;
cin >> n >> k;
vector<ll> r(n), c(n);
ll sr = 0, sc = 0;
for (int i = 0; i < n; i++) {
cin >> r[i];
sr += r[i];
}
for (int j = 0; j < n; j++) {
cin >> c[j];
sc += c[j];
}
if (sr != sc) {
cout << "NO\n";
return;
}
vector<vector<ll>> g(n, vector<ll>(n, 0));
int i = 0, j = 0;
while (i < n && j < n) {
ll put = min(r[i], c[j]);
g[i][j] = put;
r[i] -= put;
c[j] -= put;
if (r[i] == 0) {
i++;
}
if (c[j] == 0) {
j++;
}
}
cout << "YES\n";
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
if (y > 0) {
cout << ' ';
}
cout << g[x][y];
}
cout << "\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.3 Where a small \(K\) breaks things¶
\(N = 3\), \(K = 2\), \(R = (5, 3, 3)\), \(C = (2, 4, 5)\). Totals match. Fill each row left to right:
- Row 1 (5): column 1 gets 2, column 2 gets 2, column 3 gets 1. Needs left \((0, 2, 4)\).
- Row 2 (3): column 2 gets 2, column 3 gets 1. Needs \((0, 0, 3)\).
- Row 3 (3): column 3 can take only \(2\). One dollar is left with nowhere to go. Stuck.
Why? Column 3 needs \(5\), but each row gives it at most \(2\), so all three rows had to give it money, and rows 1 and 2 spent their money elsewhere first. The hungriest column was served last.
6.4 The rule: feed the hungriest column first¶
Each row, pour into the columns that still need the most, \(\min(K, \text{need}, \text{money left})\) per cell. Same data:
- Row 1 (5): needs \((2,4,5)\) → column 3 gets 2, column 2 gets 2, column 1 gets 1. Needs \((1, 2, 3)\).
- Row 2 (3): column 3 gets 2, column 2 gets 1. Needs \((1, 1, 1)\).
- Row 3 (3): one each. Done.
6.5 Rows matter too: richest row first¶
\(K = 3\), \(R = (3, 2, 6)\), \(C = (4, 1, 6)\). Rows in the order \(2, 3, 6\) dollars get stuck: the 6-dollar row needs two columns that can each still take 3, and the smaller rows have already used them up. Rows in the order \(6, 3, 2\) work. A row with lots of money is the hardest to place, so place it while there is the most room.
6.6 The full algorithm and why a failure means NO¶
- If \(\sum R \ne \sum C\):
NO. - Process rows from the largest \(R_i\) down.
- In each row, sort columns by remaining need (largest first) and pour \(\min(K, \text{need}, \text{left})\).
- If a row still has money after visiting every column:
NO. Otherwise print the grid.
Why a failure is final: each row–column pair can move at most \(K\), and pouring into the hungriest columns keeps the remaining needs as even as possible. Any other filling leaves needs that are at least as uneven, so if the greedy gets stuck, everything does. (A careful proof uses an exchange argument; we also checked the greedy against an exact max-flow criterion on 4000 random small cases.)
\(N\) sorts of \(N\) columns: \(O(N^2 \log N)\), about \(0.12\) s for \(N = 1000\).
Two easy bugs
- Sort the row indices (
ord), not the values: the output must be in the original row order. - Re-sort the columns for every row, because the needs change after each row.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// Greedy, the Gale-Ryser idea with a cap of k per cell. Handle the rows from the
// biggest target down; inside a row, pour as much as possible into the columns
// that still need the most. That keeps the leftover column needs as flat as
// possible, which is exactly what leaves the rest of the grid solvable. If the
// greedy cannot finish, no square exists.
void solve() {
int n;
ll k;
cin >> n >> k;
vector<ll> r(n), c(n);
ll sr = 0, sc = 0;
for (int i = 0; i < n; i++) {
cin >> r[i];
sr += r[i];
}
for (int j = 0; j < n; j++) {
cin >> c[j];
sc += c[j];
}
if (sr != sc) {
cout << "NO\n";
return;
}
vector<int> ord(n);
for (int i = 0; i < n; i++) {
ord[i] = i;
}
sort(ord.begin(), ord.end(), [&](int x, int y) {
return r[x] > r[y];
});
vector<int> col(n);
for (int j = 0; j < n; j++) {
col[j] = j;
}
vector<vector<ll>> g(n, vector<ll>(n, 0));
for (int t = 0; t < n; t++) {
int i = ord[t];
sort(col.begin(), col.end(), [&](int x, int y) {
return c[x] > c[y];
});
ll left = r[i];
for (int p = 0; p < n && left > 0; p++) {
int j = col[p];
ll put = min(left, min(k, c[j]));
g[i][j] = put;
c[j] -= put;
left -= put;
}
if (left > 0) {
cout << "NO\n";
return;
}
}
cout << "YES\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (j > 0) {
cout << ' ';
}
cout << g[i][j];
}
cout << "\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 2026 papers on ORAC (Australian Mathematics Trust). Explanations and code are ours, prepared for and used in the 12 September lesson.