AIO 2022¶
AIO 2022 was our 10 August lesson, together with the DP Quick Start written for Q5. None of the six needs graphs or heavy data structures: counting, scanning, greedy and one clever DP are enough.
| # | Problem | Main idea | Difficulty | Related page |
|---|---|---|---|---|
| 1 | Election II | counting | ★ | — |
| 2 | Level Ground | maximal equal blocks | ★ | Two Pointers |
| 3 | TSP | sell as little as allowed | ★★ | Greedy |
| 4 | Beautiful Buildings | only 1–2 terms change; triangle inequality | ★★★ | — |
| 5 | Composing Pyramids | DP indexed by value | ★★★★ | DP Quick Start |
| 6 | Spaceship Shuffle | prefix sums + median | ★★★★ | Prefix Sum |
Suggested order
Q1–Q3 as warm-ups (focus on why the TSP greedy is right). Q4: "a change only affects its neighbours". Q5: "delete fewest = keep most" and DP by value. Q6: work out 3 bays on paper first, then the median.
1. Election II¶
Statement. \(N\) votes, each for A, B or C. Print the winner, or T if the highest count is shared.
Idea. Count three numbers, find the maximum, count how many candidates reach it: two or more means a tie.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
string s;
cin >> n >> s;
vector<int> cnt(3);
for (char c: s) {
cnt[c - 'A']++;
}
int mx = max({cnt[0], cnt[1], cnt[2]});
int tie = (cnt[0] == mx) + (cnt[1] == mx) + (cnt[2] == mx);
if (tie > 1) {
cout << "T\n";
} else if (cnt[0] == mx) {
cout << "A\n";
} else if (cnt[1] == mx) {
cout << "B\n";
} else {
cout << "C\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. Level Ground¶
Statement. A mountain range has \(N\) sections with heights \(A_i\). A race needs a contiguous stretch of equal height; its strength is length × height. Maximise the strength.
Idea. A valid stretch lies inside a maximal block of equal heights, and inside a block longer is always better. So cut the array into maximal blocks (i at the block start, j runs until the height changes) and take the best (j - i) * a[i].
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
ll ans = 0;
int i = 0;
while (i < n) {
int j = i;
while (j < n && a[j] == a[i]) {
j++;
}
// [i, j) is a maximal block of equal heights
ans = max(ans, (ll) (j - i) * a[i]);
i = j;
}
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. TSP¶
Statement. On day \(i\) the Tomato Salesperson must sell between \(L_i\) and \(R_i\) tomatoes, and never fewer than the day before. Is it possible?
Idea. On day \(i\) you must sell at least \(\max(\text{yesterday}, L_i)\). Selling exactly that minimum is never worse: a smaller number today only relaxes tomorrow's lower bound. If that minimum exceeds \(R_i\), answer NO.
This "choosing the smallest keeps the most options open" argument is the stays ahead proof from the Greedy page.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<ll> l(n), r(n);
for (int i = 0; i < n; i++) {
cin >> l[i];
}
for (int i = 0; i < n; i++) {
cin >> r[i];
}
ll cur = 0;
for (int i = 0; i < n; i++) {
cur = max(cur, l[i]); // minimum we must sell today
if (cur > r[i]) {
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;
}
4. Beautiful Buildings¶
Statement. Building heights \(H_1, \dots, H_N\); ugliness is \(\sum |H_i - H_{i+1}|\). You may change at most one height to anything. Minimise the ugliness.
Idea.
- Changing \(H_i\) only affects the terms containing \(H_i\): one term at an end, two in the middle. Answer = total − best saving.
- End building: set it equal to its neighbour, saving that whole term.
- Middle building: by the triangle inequality \(|H_{i-1} - x| + |x - H_{i+1}| \ge |H_{i-1} - H_{i+1}|\), with equality for any \(x\) between them. The saving is the old two terms minus \(|H_{i-1} - H_{i+1}|\).
- Take the largest saving (at least \(0\)).
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<ll> h(n);
for (int i = 0; i < n; i++) {
cin >> h[i];
}
ll sum = 0;
for (int i = 0; i + 1 < n; i++) {
sum += abs(h[i] - h[i + 1]);
}
// changing one building affects only its 1~2 adjacent terms; answer = sum - max saving
ll save = 0;
save = max(save, abs(h[0] - h[1]));
save = max(save, abs(h[n - 1] - h[n - 2]));
for (int i = 1; i + 1 < n; i++) {
ll old = abs(h[i - 1] - h[i]) + abs(h[i] - h[i + 1]);
ll cur = abs(h[i - 1] - h[i + 1]);
save = max(save, old - cur);
}
cout << sum - save << "\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. Composing Pyramids¶
Statement. Delete as few notes as possible so the remaining notes form a pyramid \(x, x+1, \dots, x+k, \dots, x+1, x\).
Idea. This problem has its own page: DP Quick Start builds the DP step by step (Fibonacci → stairs → LIS → this) and traces the sample. In short: up[i] = longest \(+1\) chain ending at \(i\), dn[i] = longest \(-1\) chain starting at \(i\), both found with a table indexed by value; the answer is \(N - \max_i (2\min(\texttt{up}[i], \texttt{dn}[i]) - 1)\).
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXV = 100001;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// up[i]: longest chain of consecutive increasing values ending at i
// dn[i]: longest chain of consecutive decreasing values starting at i
vector<int> up(n), dn(n);
// f[v]: longest chain of consecutive increasing values ending with value v
vector<int> f(MAXV + 2, 0), g(MAXV + 2, 0);
for (int i = 0; i < n; i++) {
up[i] = f[a[i] - 1] + 1;
f[a[i]] = max(f[a[i]], up[i]);
}
for (int i = n - 1; i >= 0; i--) {
dn[i] = g[a[i] - 1] + 1;
g[a[i]] = max(g[a[i]], dn[i]);
}
int best = 1;
for (int i = 0; i < n; i++) {
best = max(best, 2 * min(up[i], dn[i]) - 1);
}
cout << n - best << "\n";
}
// LIS
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. Spaceship Shuffle¶
Statement. \(N\) bays form a ring. Bay \(i\) has \(A_i\) people and needs \(B_i\) (totals are equal). Moving one person to a neighbouring bay costs \(1\). Minimise the cost.
Idea.
- Let \(D_i = A_i - B_i\). Instead of tracking people, track the net flow \(f_i\) over each edge \(i \to i+1\); the cost is \(\sum |f_i|\).
- On a line the flows are forced: everything extra in bays \(1..i\) must cross edge \(i\), so \(f_i = S_i = D_1 + \dots + D_i\) (a prefix sum).
- On a ring there is one free choice: the flow \(x\) over the edge between bay \(N\) and bay \(1\). Then \(f_i = x + S_i\), and we minimise \(\sum_i |x + S_i|\).
- \(\sum |x - t_i|\) is smallest when \(x\) is a median of the \(t_i\) (moving away from it adds more distance on one side than it saves on the other). So take \(m\) = median of \(S\) and the answer is \(\sum |S_i - m|\).
Sample 2: \(A = 5\,0\,0\,0\,0\), \(B = 1\,1\,1\,1\,1\) → \(D = 4, -1, -1, -1, -1\) → \(S = 4, 3, 2, 1, 0\), median \(2\), cost \(2 + 1 + 0 + 1 + 2 = 6\).
Subtask strategy
Subtask 2 promises an optimal solution that never uses the edge between bays \(N\) and \(1\). That is exactly \(x = 0\): print \(\sum |S_i|\) for 55 points, then add the median.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n;
cin >> n;
vector<ll> a(n), b(n), s(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
// s[i]: prefix sum of net people over first i bays, i.e. base flow on edge i
ll pre = 0;
for (int i = 0; i < n; i++) {
pre += a[i] - b[i];
s[i] = pre;
}
// the ring adds one free variable x; cost = sum|x + s[i]|, minimized at the median
vector<ll> t = s;
sort(t.begin(), t.end());
ll mid = t[n / 2];
ll ans = 0;
for (int i = 0; i < n; i++) {
ans += abs(s[i] - mid);
}
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 2022 papers on ORAC (Australian Mathematics Trust). Explanations and code are ours; all files pass the official samples.