AIO 2021

AIO 2021 was our 15 August lesson. The set climbs gently: four basics, then "which endpoints are worth trying", then one observation problem.

#	Problem	Main idea	Difficulty	Related page
1	Robot Vacuum	Manhattan distance	★	—
2	Art Class II	bounding box	★	Integer Types
3	Melody	three independent groups, keep the most common note	★★	—
4	Social Distancing	sort + take the leftmost allowed	★★	Greedy
5	Space Mission	suffix minima + binary search	★★★	Binary Search
6	Laser Cutter	walk both paths together, gap ±1	★★★★	—

1. Robot Vacuum

ORAC problem 1098

Statement. A robot starts at the origin and follows N/S/E/W moves. How many more moves does it need, at least, to get back to the origin?

Idea. Horizontal and vertical movement are independent. With \(h\) = east − west and \(v\) = north − south, it needs \(|h| + |v|\) moves. EEWEWEWEEEW has 7 E and 4 W: answer \(3\).

Robot Vacuum.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

// Count net horizontal / vertical displacement; the extra moves needed to
// return home is |h| + |v| (Manhattan distance back to origin).
void solve() {
    int k;
    string s;
    cin >> k >> s;

    int h = 0, v = 0;
    for (char c: s) {
        if (c == 'E') {
            h++;
        } else if (c == 'W') {
            h--;
        } else if (c == 'N') {
            v++;
        } else {
            v--; // 'S'
        }
    }

    cout << abs(h) + abs(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;
}

2. Art Class II

ORAC problem 1099

Statement. Given \(N\) points, find the smallest area of an axis-aligned rectangle containing all of them.

Idea. The rectangle must stretch from the smallest to the largest \(x\) and from the smallest to the largest \(y\); any margin only adds area. Track four extremes in one pass; area \((\max x - \min x)(\max y - \min y)\), which needs long long.

Art Class II.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

// The smallest axis-aligned rectangle covering all points is the bounding box:
// area = (maxX - minX) * (maxY - minY).
void solve() {
    int n;
    cin >> n;

    ll minx = LLONG_MAX, maxx = LLONG_MIN;
    ll miny = LLONG_MAX, maxy = LLONG_MIN;
    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        minx = min(minx, x);
        maxx = max(maxx, x);
        miny = min(miny, y);
        maxy = max(maxy, y);
    }

    cout << (maxx - minx) * (maxy - miny) << "\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. Melody

ORAC problem 1097

Statement. A tune has \(N\) notes with pitches \(1 \dots K\). A melody repeats every 3 notes (positions \(0, 3, 6, \dots\) equal; \(1, 4, 7, \dots\) equal; \(2, 5, 8, \dots\) equal). Change as few notes as possible to make it a melody.

Idea. Split positions by i % 3 into three independent groups. In each group keep the most common note and change the rest: cost = group size − highest count. The three groups may even choose the same note.

Melody.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

// A melody repeats every 3 notes, so positions i%3 == 0/1/2 form three
// independent groups. Each group must become one single note; keep the most
// common note in each group and change the rest. The three notes are chosen
// independently and do NOT have to be distinct.
void solve() {
    int n, k;
    cin >> n >> k;

    vector<vector<int>> cnt(3, vector<int>(k + 1, 0));
    vector<int> sz(3, 0);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[i % 3][x]++;
        sz[i % 3]++;
    }

    int ans = 0;
    for (int g = 0; g < 3; g++) {
        int best = 0;
        for (int v = 1; v <= k; v++) {
            best = max(best, cnt[g][v]);   // mode of this group
        }
        ans += sz[g] - best;               // change everything except the mode
    }

    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. Social Distancing

ORAC problem 1102

Statement. Meals are at positions on a line. Choose as many as possible so that any two chosen ones are at least \(K\) apart.

Idea. Sort. Take the leftmost meal, then repeatedly the next meal at least \(K\) after the last one taken. Taking the leftmost possible meal leaves the most room for the rest (stays ahead), and after that choice the rest is the same problem on a shorter line.

Social Distancing.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

// Sort the positions, then greedily take a meal whenever it is at least K away
// from the last one taken. Taking the earliest valid meal each time is optimal
// (it leaves the most room for the rest).
void solve() {
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    sort(p.begin(), p.end());

    int ans = 1;
    ll last = p[0];
    for (int i = 1; i < n; i++) {
        if (p[i] - last >= k) {
            ans++;
            last = p[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. Space Mission

ORAC problem 1101

Statement. Day \(i\) has fuel cost \(C_i\). Pick a launch day \(i\) and a return day \(j > i\) with \(C_i + C_j \le F\) to maximise the length \(j - i + 1\), or print \(-1\).

Idea, following the subtasks:

1. Brute force over all pairs: \(O(N^2)\).
2. A good launch day is far left and cheap; a good return day is far right and cheap.
3. Key fact: for any budget \(t\), the largest index \(j\) with \(C_j \le t\) is a suffix minimum (smaller than everything to its right), because everything to its right is more than \(t \ge C_j\).
4. So collect the suffix minima; both their indices and their values increase. For each launch day \(i\), binary search the last suffix minimum with value \(\le F - C_i\), and use it if its index is after \(i\).

\(O(N \log N)\). For 3 1 4 1 5 with \(F = 5\) the suffix minima are index 3 (value 1) and index 4 (value 5); launching at index 0 (\(C = 3\)) can return at index 3: length \(4\).

Space Mission.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

// Find i < j with c[i] + c[j] <= f maximizing the span j - i + 1 (print -1 if
// none). The largest index j whose value <= t is always a "suffix minimum", so
// we collect suffix minima (index & value both ascending) and, for each i,
// binary search the farthest such j with value <= f - c[i].
void solve() {
    int n;
    ll f;
    cin >> n >> f;
    vector<ll> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }

    // suffix minima: an index smaller than everything to its right
    vector<int> ridx;
    vector<ll> rval;
    ll cur = LLONG_MAX;
    for (int j = n - 1; j >= 0; j--) {
        if (c[j] < cur) {
            cur = c[j];
            ridx.push_back(j);
            rval.push_back(c[j]);
        }
    }
    reverse(ridx.begin(), ridx.end());   // index ascending, value ascending
    reverse(rval.begin(), rval.end());

    int ans = -1;
    for (int i = 0; i < n; i++) {
        ll t = f - c[i];
        if (t < 0) {
            continue;
        }
        // farthest suffix-minimum index whose value is <= t
        int pos = (int) (upper_bound(rval.begin(), rval.end(), t) - rval.begin()) - 1;
        if (pos >= 0 && ridx[pos] > i) {
            ans = max(ans, ridx[pos] - 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;
}

6. Laser Cutter

ORAC problem 1100

Statement. A shape is enclosed by an upper and a lower path, each \(2N\) steps of D (down) and R (right) from \((0, 0)\) to \((N, N)\). Find the side of the largest square that fits inside.

Idea.

1. The official observation: an optimal square has its top-right corner on the upper path and its bottom-left corner on the lower path, and these corners are the \(i\)-th points of the two paths for the same \(i\).
2. So walk both paths in step and track the gap between their \(i\)-th points:
   • upper goes D while lower goes R: gap \(+1\);
   • upper goes R while lower goes D: gap \(-1\);
   • otherwise the gap is unchanged.
3. The answer is the largest gap reached.

Draw a \(3 \times 3\) example and move both paths one step at a time to see the gap grow and shrink.

Laser Cutter.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

// Walk the upper path a and lower path b in lockstep. The vertical gap between
// them changes by +1 when the upper goes Down while the lower goes Right, and
// by -1 in the opposite case. The largest square that fits is the largest gap
// ever reached.
void solve() {
    int n;
    string a, b; // upper walk and lower walk, each of length 2*n
    cin >> n >> a >> b;

    int side = 0, ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (a[i] == 'D' && b[i] == 'R') {
            side++;
        } else if (a[i] == 'R' && b[i] == 'D') {
            side--;
        }
        ans = max(ans, side);
    }

    cout << ans << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

---

Credits & sources

Statements summarised from the official AIO 2021 papers on ORAC (Australian Mathematics Trust); approaches follow the ORAC editorials, with input details cross-checked against the full-score reference solutions in Australian-Informatics-Problems. Explanations and code are ours.