AIO 2025¶

We met AIO 2025 twice: first Q4–Q6 in depth on 23, 27 and 30 July (including full proofs, below), then the whole paper on 23 August.

#	Problem	Main idea	Difficulty	Related page
1	Soccer Match	simulation	★	—
2	Buried Treasure	intersection of intervals	★	—
3	Off the Track	switch direction at most once	★★	—
4	ORAC	train first; count per difficulty	★★★	Greedy, Binary Search
5	Pairing Cards	greedy from both ends	★★★★	Greedy
6	Robot Writing	prefix maxima, distance + parity	★★★★★	BFS with Parity States

Suggested order

Q1–Q2 are one-pass warm-ups. Q3 asks "what must an optimal plan look like?". Q4 and Q5 are about proving a greedy, which is exactly what our July lessons did. Q6 is for the very top students; read the idea, then the proof notes.

1. Soccer Match¶

ORAC problem 1621

Statement. A match has $N$ goals, each scored by team 1 or team 2, given in order. Was team 1 ever strictly ahead?

Idea. Keep both scores while reading; after each goal, check s1 > s2. For 2 2 1 1 1 2 2: 0:1, 0:2, 1:2, 2:2, 3:2 → YES.

Soccer Match.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

// Replay the goals and check whether team 1 is ever strictly ahead.
void solve() {
    int n;
    cin >> n;

    int s1 = 0, s2 = 0;
    bool ok = false;
    for (int i = 0; i < n; i++) {
        int g;
        cin >> g;
        if (g == 1) {
            s1++;
        } else {
            s2++;
        }
        if (s1 > s2) {
            ok = true;
        }
    }

    if (ok) {
        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;
}

2. Buried Treasure¶

ORAC problem 1617

Statement. Treasure is buried at one of the positions $1 \dots L$. Clue $i$ says it is between $A_i$ and $B_i$ inclusive. How many positions agree with every clue?

Idea. The answer is the intersection of all intervals: lower end $\max A_i$, upper end $\min B_i$, size $\max(0, \text{hi} - \text{lo} + 1)$. For clues $(3,6)$ and $(5,8)$: $[5, 6]$, size $2$.

Buried Treasure.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

// Every clue is an interval; the answer is the size of their intersection.
void solve() {
    int n, l;
    cin >> n >> l;

    int lo = 1, hi = l;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        lo = max(lo, a);
        hi = min(hi, b);
    }

    cout << max(0, hi - lo + 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;
}

3. Off the Track¶

ORAC problem 1619

Statement. $N$ students stand at positions $P_1 < \dots < P_N$ on a track of length $L$. Each second you shout "forwards" or "backwards" and every student still on the track moves one metre that way; reaching $0$ or $L$ means leaving. What is the fewest seconds to clear the track?

Idea.

Shouting one direction the whole time costs $L - P_1$ (everyone off the far end) or $P_N$ (off the near end).
An optimal plan never needs more than one change of direction: a left group leaves through $0$ and a right group through $L$, and going back and forth more often only wastes time.
So try every split between neighbours $i$ and $i + 1$ and both orders. "Backwards first, then forwards": $P_i$ seconds clear the left group, then the student that was at $P_{i+1}$ is at $P_{i+1} - P_i$ and needs $L - (P_{i+1} - P_i)$ more: $2P_i - P_{i+1} + L$. The other order is symmetric.

Sample 3 ($L = 15$, $P = 1\,3\,11\,14$), split between 3 and 11: $2\cdot3 - 11 + 15 = 10$, the answer.

Off the Track.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

// Either yell one direction the whole time, or switch direction exactly once.
// A single switch is decided by which student is the last one pushed off each
// end, so there are only 2*(n-1)+2 candidate plans.
void solve() {
    ll n, l;
    cin >> n >> l;

    vector<ll> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }

    ll ans = min(l - p[0], p[n - 1]);
    for (int i = 0; i + 1 < n; i++) {
        // forwards first, then backwards
        ans = min(ans, p[n - i - 2] - 2 * p[n - i - 1] + 2 * l);
        // backwards first, then forwards
        ans = min(ans, 2 * p[i] - p[i + 1] + l);
    }

    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. ORAC¶

ORAC problem 1618

Statement. $N$ problems have difficulties $D_1 \le \dots \le D_N$. Your skill starts at $0$. Each morning you train ($+1$) or relax ($-1$, may go negative); each afternoon you may solve one problem whose difficulty is at most your skill. Days are unlimited. Minimise the number of training mornings needed to solve everything.

Idea.

Train first. Moving a training morning earlier never lowers any day's skill (Claim 1 below). So the best plans train $x$ days, then relax.
That plan's skill climbs $1, \dots, x$ and falls $x - 1, \dots, 1$. Skill $\ge d$ happens on exactly $2(x - d) + 1$ afternoons.
Let $N_d$ = number of problems with difficulty $\ge d$. They all need such afternoons: $N_d \le 2x - 2d + 1$, i.e. $x \ge \lfloor N_d / 2 \rfloor + d$.
The answer is the largest of these lower bounds over all $d$ (and it is achievable).

Sample 3 ($D = 3\,3\,3\,3\,4\,4\,4\,5\,5\,7$): $d = 3$ gives $5 + 3 = 8$, $d = 4$ gives $3 + 4 = 7$, $d = 7$ gives $0 + 7 = 7$. Answer $8$.

Because $D$ is sorted, $N_d$ is found with a pointer that only moves forward: $O(N + \max D)$.

ORAC.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

// Training days must come first. To clear the cnt problems of difficulty >= i
// we need at least cnt/2 + i training mornings, so the answer is the largest
// such bound over every difficulty level i.
void solve() {
    int n;
    cin >> n;

    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        cin >> d[i];
    }

    int ans = 0, j = 0;
    for (int i = 1; i <= d[n - 1]; i++) {
        // d is sorted, so j walks up to the first problem with d[j] >= i
        while (d[j] < i) {
            j++;
        }
        int cnt = n - j;
        ans = max(ans, cnt / 2 + 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;
}

Proofs from our lesson (23 July)¶

In class we reached the answer by binary search first (Solution 1) and then turned the check into the one-line formula (Solution 2).

Model the skill level as a walk: it starts at $0$, each morning a Train is $+1$ and a Relax is $-1$. Let $L(i)$ be the skill level on day $i$. In the afternoon of day $i$ you may clear one unsolved problem with $D \le L(i)$. We want to minimise the number of Train mornings.

Claim 1¶

Training earlier is better than training later.

Proof of claim 1¶

Assume we train for $x$ days, but these are not the first $x$ days.
Then we can always find some day $d$ where we trained, but we did not train on day $d-1$.
Let $L(i)$ be the skill level on the $i$-th day.
Then we have $$ L(d-1)=L(d-2)-1\ L(d)=L(d-1)+1=\big(L(d-2)-1\big)+1=L(d-2). $$
Now change the schedule so that we train on day $d-1$ instead of day $d$.
Then we have

\[ L'(d-1)=L(d-2)+1\\L'(d)=L'(d-1)-1=\big(L(d-2)+1\big)-1=L(d-2). \]

We find $L'(d)=L(d)$, but $L'(d-1)>L(d-1)$.
Every day up to $d-1$ keeps its skill, and every day from $d$ onward is unchanged too.
Hence the swap never lowers any day's skill and strictly raises one — it is an improvement.
Repeatedly swapping such days pushes all training to the front, giving a schedule that trains the first $x$ days and relaxes afterwards.

Claim 2¶

If we can train $x$ days and solve all the problems, then for all $y\ge x$ we can also solve all the problems by training $y$ days.

Proof¶

Take a schedule that trains $x$ days and solves everything.
Consider its last relaxing morning (if there is none, append one at the end — extra days are free and cost no training).
Turn that relaxing morning into a training morning.
Changing a Relax ($-1$) into a Train ($+1$) never decreases the skill on that day or any later day, and leaves earlier days unchanged.
So every problem that was solvable before is still solvable — feasibility is preserved.
Each change adds one training day, so repeating it reaches any $y\ge x$.

Claim 3¶

Given the number of training days $x$, we can check whether all problems can be solved.

Proof¶

By Claim 1 the trainings come first, so the skill climbs $1,2,\dots,x$; and since relaxing costs no training yet each morning still gives an afternoon, after the peak we relax back down $x-1,x-2,\dots,1$. Call this schedule the mountain.
On the mountain, skill level $x$ is reached on $1$ afternoon, and each level $v<x$ on $2$ afternoons (once going up, once coming down); sorted from the highest, the $k$-th afternoon has skill $x-\lfloor k/2\rfloor$.
No $x$-training schedule can have more afternoons of skill $\ge v$ than the mountain: reaching level $v$ already costs $v$ trainings, and every further day spent at height $\ge v$ needs one of the remaining $x-v$ trainings to climb (each mirrored by one free relax to come back down), so there are at most $2(x-v)+1$ such afternoons — exactly what the mountain attains. The mountain is therefore the most generous $x$-training schedule at every level simultaneously.
Hence $x$ trainings suffice iff the mountain solves everything. Match the hardest remaining problem to the highest free afternoon (a one-line exchange shows sorted-to-sorted matching is optimal): with difficulties sorted descending as $E_1\ge E_2\ge\cdots\ge E_N$, this succeeds iff $E_k\le x-\lfloor k/2\rfloor$ for every $k$.
Rearranged, $x$ training days suffice iff $$ x \ \ge\ \max_{1\le k\le N}\Big(E_k+\big\lfloor k/2\big\rfloor\Big). $$

Solution 1¶

Feasibility is monotone in $x$ (Claim 2), so binary search the smallest feasible $x$, and use the mountain check of Claim 3 for each candidate. This is exactly what we discussed during the class:

The deque lays the sorted difficulties into bitonic order — smallest at both ends, largest in the middle — so they line up against the mountain's skill sequence.
check(x) walks up $1,\dots,x$ then down $x-1,\dots,1$, advancing idx whenever day >= d[idx]. That is precisely the highest-slot / hardest-problem matching of Claim 3.
The search range up to $4\cdot10^5$ is safe, since $$ x^*\le \max D_i+\Big\lfloor \frac{N}{2}\Big\rfloor\le 2\cdot10^5+10^5 $$

Runtime $O(N\log \max D)$.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    deque<int> d;
    for (int i = n - 1; i >= 0; i--) {
        if (i % 2) {
            d.push_back(a[i]);
        } else {
            d.push_front(a[i]);
        }
    }

    /*
     * n = 1
     * a[0] = 3
     */

    auto check = [&](int x) -> bool {
        int idx = 0;
        for (int day = 1; day <= x and idx < n; day++) {
            if (day >= d[idx]) {
                idx++;
            }
        }
        for (int day = x - 1; day > 0 and idx < n; day--) {
            if (day >= d[idx]) {
                idx++;
            }
        }
        return idx == n;
    };

    int l = 1, r = 400000, ans = 400000;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }

    cout << ans;


    return 0;
}

Solution 2¶

Since Claim 3, step 5 is a closed form, we can also drop the binary search entirely and give an one-line version, $O(N)$:

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> D(n);
    for (auto& x : D) cin >> x;  // ascending
    int ans = 0;
    for (int k = 1; k <= n; k++)          // k-th largest is D[n-k]
        ans = max(ans, D[n - k] + k / 2);
    cout << ans;
}

5. Pairing Cards¶

ORAC problem 1622

Statement. $N$ cards ($N$ even) show $A_1 \le \dots \le A_N$. Split them into pairs so that every pair has difference $D$ or sum $S$. Is it possible?

Idea: attack from both ends.

The smallest card mn can only pair with mn + D or S - mn (nothing is smaller than it).
Neither exists → NO. Exactly one exists → take it.
Both exist: look at the largest card mx.
- If S - mn == mx, pair mn with mx. This never hurts: if instead mn went with mn + D and mx with mx - D, those two pairs can be regrouped as (mn, mx) and (mn + D, mx - D), whose sum is also $S$.
- Otherwise S - mn < mx, so S - mx < mn: nothing can pair with mx by sum. mx is forced onto mx - D.
Repeat until every card is paired.

Sample 4 ($D = 7$, $S = 8$, cards $1\,3\,5\,8$): 1 can only take 8 (as $1 + 7$); then 3 takes 5 (sum 8). YES.

Counts per value with two pointers for the current min and max give $O(N + \max A)$.

$D = 0$

Then mn + D is mn itself. Remove mn from the counts before checking whether another copy exists.

Pairing Cards.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int MX = 1000000;

// Greedy on the two ends of the deck. The smallest card can only go with
// mn+d or s-mn. If both exist we look at the largest card: if s-mn equals it we
// pair the two ends, otherwise no card matches s-mx so the largest card is
// forced onto mx-d.
void solve() {
    int n, d, s;
    cin >> n >> d >> s;

    vector<int> cnt(MX + 1, 0);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        cnt[a]++;
    }

    int lo = 1, hi = MX, left = n;
    while (left > 0) {
        while (cnt[lo] == 0) {
            lo++;
        }
        int mn = lo;
        cnt[mn]--;
        left--;

        int p = mn + d;
        int q = s - mn;
        bool okp = (p <= MX && cnt[p] > 0);
        bool okq = (q >= 1 && q <= MX && cnt[q] > 0);

        if (!okp && !okq) {
            cout << "NO\n";
            return;
        }

        if (okp && okq) {
            while (cnt[hi] == 0) {
                hi--;
            }
            if (q != hi) {
                // the largest card has no partner summing to s, so force mx-d
                cnt[mn]++;
                left++;
                int mx = hi;
                int r = mx - d;
                cnt[mx]--;
                left--;
                if (r < 1 || cnt[r] == 0) {
                    cout << "NO\n";
                    return;
                }
                cnt[r]--;
                left--;
                continue;
            }
            okp = false;
        }

        int t = (okp ? p : q);
        cnt[t]--;
        left--;
    }

    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;
}

6. Robot Writing¶

ORAC problem 1620

Statement. $N$ tiles in a row show $T_1, \dots, T_N$. A robot starts on any tile and makes $M$ steps; in each step it writes down the number under it, moves one tile left or right, and if the new tile's number is smaller than the old tile's, the two tiles swap numbers. Can the written sequence be exactly $S_1, \dots, S_M$?

Idea.

The swaps are a disguise. The robot always carries the largest value seen so far (Claims 1–5 below), so what it writes is the running maximum of the original numbers along its walk.
So $S$ must be non-decreasing and every value of $S$ must appear on some tile.
Group $S$ into runs of equal values $v_1 < v_2 < \dots$ with lengths $c_1, c_2, \dots$. Run $j$ must start on a tile showing $v_j$, and the robot must stay inside the stretch of tiles with values $\le v_j$ around it.
Moving from a tile $u$ with value $v_{j-1}$ to a tile $i$ with value $v_j$ during run $j - 1$ is possible exactly when the distance fits ($|i - u| \le c_{j-1}$), the parity matches ($|i - u| \equiv c_{j-1} \pmod 2$, spare steps are burned by stepping back and forth), and no bigger value lies strictly between them.
Mark reachable tiles value by value. For speed: keep the previous layer's reachable tiles in two sorted lists by index parity (only the nearest one on each side matters) and answer "largest value between" with a sparse table. $O(N \log N)$.

The distance-and-parity test is the same one as in Evading Capture.

Robot Writing.cpp

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

// Tile i is "possible" if the robot can arrive at i for the first time having
// printed exactly a prefix of s, with t[i] printed for the first time there.
// Walking from a tile holding the previous target value p to a tile holding the
// next value v needs: distance <= cnt[p], distance and cnt[p] of equal parity,
// and nothing bigger than p strictly in between.
void solve() {
    int n;
    cin >> n;

    vector<int> t(n);
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }
    int m;
    cin >> m;
    vector<int> s(m);
    for (int i = 0; i < m; i++) {
        cin >> s[i];
    }

    for (int i = 0; i + 1 < m; i++) {
        if (s[i] > s[i + 1]) {
            cout << "NO\n";
            return;
        }
    }

    // distinct target values (already sorted) and how often each is printed
    vector<int> v, cnt;
    for (int i = 0; i < m; i++) {
        if (i == 0 || s[i] != s[i - 1]) {
            v.push_back(s[i]);
            cnt.push_back(1);
        } else {
            cnt.back()++;
        }
    }
    int k = (int) v.size();

    // tiles holding each target value
    vector<vector<int>> at(k);
    map<int, int> id;
    for (int j = 0; j < k; j++) {
        id[v[j]] = j;
    }
    for (int i = 0; i < n; i++) {
        auto it = id.find(t[i]);
        if (it != id.end()) {
            at[it->second].push_back(i);
        }
    }
    for (int j = 0; j < k; j++) {
        if (at[j].empty()) {
            cout << "NO\n";
            return;
        }
    }

    // sparse table over t for range maximum
    int lg = 1;
    while ((1 << lg) <= n) {
        lg++;
    }
    vector<vector<int>> sp(lg, vector<int>(n));
    sp[0] = t;
    for (int j = 1; j < lg; j++) {
        for (int i = 0; i + (1 << j) <= n; i++) {
            sp[j][i] = max(sp[j - 1][i], sp[j - 1][i + (1 << (j - 1))]);
        }
    }
    auto rmax = [&](int l, int r) {
        // max of t[l..r], or 0 if the range is empty
        if (l > r) {
            return 0;
        }
        int j = 31 - __builtin_clz(r - l + 1);
        return max(sp[j][l], sp[j][r - (1 << j) + 1]);
    };

    vector<char> ok(n, 0);
    for (int i : at[0]) {
        bool bigl = (i == 0 || t[i - 1] > t[i]);
        bool bigr = (i == n - 1 || t[i + 1] > t[i]);
        // a tile hemmed in by bigger tiles can only be printed once
        if (cnt[0] >= 2 && bigl && bigr) {
            continue;
        }
        ok[i] = 1;
    }

    for (int j = 1; j < k; j++) {
        int p = v[j - 1], x = cnt[j - 1];
        // possible tiles holding p, split by index parity
        vector<vector<int>> src(2);
        for (int i : at[j - 1]) {
            if (ok[i]) {
                src[i & 1].push_back(i);
            }
        }

        bool any = false;
        for (int i : at[j]) {
            vector<int> &c = src[(i + x) & 1];
            auto it = lower_bound(c.begin(), c.end(), i);
            if (it != c.begin()) {
                int u = *prev(it);
                if (i - u <= x && rmax(u + 1, i - 1) <= p) {
                    ok[i] = 1;
                }
            }
            if (it != c.end()) {
                int u = *it;
                if (u - i <= x && rmax(i + 1, u - 1) <= p) {
                    ok[i] = 1;
                }
            }
            if (ok[i]) {
                any = true;
            }
        }
        if (!any) {
            cout << "NO\n";
            return;
        }
    }

    for (int i : at[k - 1]) {
        if (ok[i]) {
            cout << "YES\n";
            return;
        }
    }
    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;
}

The complete proof (30 July lesson note)¶

Notation¶

Tiles are numbered $1..N$. The initial values are $T_1,\dots,T_N$. An unsuperscripted $T_i$ always means the initial value.
$T^{(k)}$ is the array after step $k$, so $T^{(0)}=T$.
Positions: $p_0,\dots,p_M$, with $|p_k-p_{k-1}|=1$ and $1\le p_k\le N$.
Step $k$: record $O_k$, then move to $p_k$, then swap. Here $O_k=T^{(k-1)}[p_{k-1}]$.
$V_k={p_0,\dots,p_k}$ is the set of visited positions.
Target sequence: $S_1,\dots,S_M$.

Claim 1 (What the swap rule really does)¶

Write $v$ for the value on the tile being left and $u$ for the value on the tile being entered. After the move and swap of step $k$:

the robot's new tile holds $\max(u,v)$, i.e. $T^{(k)}[p_k]=\max(u,v)$;

the tile just left holds $\min(u,v)$, i.e. $T^{(k)}[p_{k-1}]=\min(u,v)$;

no other tile changes.

In words: the robot carries away the larger value and leaves the smaller one behind.

Proof¶

By definition $v=T^{(k-1)}[p_{k-1}]$ and $u=T^{(k-1)}[p_k]$.
Case $u<v$: the rule swaps. The new tile gets $v$, which is $\max(u,v)$; the old tile gets $u$, which is $\min(u,v)$. ✔
Case $u\ge v$: no swap. The new tile keeps $u=\max(u,v)$; the old tile keeps $v=\min(u,v)$. ✔
The rule touches only these two tiles. $\square$

Claim 2 (The visited set is an interval)¶

For every $k$, the set $V_k$ is a contiguous interval $[L_k,R_k]$. Also $p_k\in V_k$ and $V_{k-1}\subseteq V_k$.

Proof¶

Base: $V_0={p_0}$, an interval.
Assume $V_{k-1}=[L,R]$ with $p_{k-1}\in[L,R]$.
Since $p_k=p_{k-1}\pm1$, we get $p_k\in[L-1,R+1]$.
So $V_k=[L,R]\cup{p_k}$ is still an interval: $p_k$ is either inside, or immediately outside one end. $\square$

Claim 3 (Values are only shuffled inside the visited interval)¶

For every $k$:

(a) tiles outside are untouched: $T^{(k)}[i]=T_i$ for $i\notin V_k$;

(b) tiles inside are a permutation of the originals: as multisets, ${T^{(k)}[i]}*{i\in V_k}={T_i}*{i\in V_k}$.

Proof¶

Base $k=0$: immediate.
Step $k$ swaps only $p_{k-1}$ and $p_k$, and both lie in $V_k$. So nothing outside $V_k$ is ever touched, giving (a).
For (b), case $p_k\in V_{k-1}$: then $V_k=V_{k-1}$, and the swap just exchanges two values already inside. Apply the induction hypothesis.
Case $p_k\notin V_{k-1}$: then $V_k=V_{k-1}\cup{p_k}$, and by (a) at step $k-1$ we know $T^{(k-1)}[p_k]=T_{p_k}$. So the multiset over $V_k$ is the old one plus $T_{p_k}$, which is exactly ${T_i}_{i\in V_k}$; one more exchange preserves it. $\square$

Claim 4 (The robot always stands on the maximum of the visited region)¶

For every $k$, the value under the robot is the maximum of the original values over everything visited so far: $T^{(k)}[p_k]=\max_{i\in V_k}T_i$.

Proof¶

Base: $T^{(0)}[p_0]=T_{p_0}$, and $V_0={p_0}$.
By Claim 1, $T^{(k)}[p_k]=\max\big(T^{(k-1)}[p_{k-1}],,T^{(k-1)}[p_k]\big)$.
By the induction hypothesis the first argument is $\max_{i\in V_{k-1}}T_i$.
Case $p_k\notin V_{k-1}$: by Claim 3(a) the second argument is $T_{p_k}$. The max of the two is $\max_{i\in V_k}T_i$. ✔
Case $p_k\in V_{k-1}$: by Claim 3(b) the second argument is one of the values ${T_i}*{i\in V*{k-1}}$, hence at most $\max_{i\in V_{k-1}}T_i$. So the max of the two is $\max_{i\in V_{k-1}}T_i$, and here $V_k=V_{k-1}$. ✔ $\square$

Claim 5 (Restatement: only prefix maxima matter)¶

The instance is solvable iff there is a walk $p_0,\dots,p_{M-1}$ (steps of $\pm1$, staying in $[1,N]$) whose prefix maxima match $S$, i.e. $\max(T_{p_0},\dots,T_{p_{k-1}})=S_k$ for every $k\in[1,M]$.

The swapping can be discarded entirely.

Proof¶

By definition $O_k=T^{(k-1)}[p_{k-1}]$.
Claim 4 applied at time $k-1$ turns this into $O_k=\max_{i\in V_{k-1}}T_i$, which is the prefix maximum $\max(T_{p_0},\dots,T_{p_{k-1}})$. So the output of any legal run is the prefix-maximum sequence — necessity.
Conversely, such a walk uses only $M-1$ moves. Since $N\ge2$, an $M$-th move to some $p_M$ always exists (at an endpoint, move inward).
Running the robot along that walk therefore outputs $O_k=S_k$. $\square$

Claim 6 (First necessary condition)¶

If solvable, $S$ is non-decreasing.

Proof¶

$V_{k-1}\subseteq V_k$ by Claim 2.
A maximum over a larger set can only grow, so $S_k\le S_{k+1}$. $\square$

Compression. Split $S$ into maximal runs of equal values. Let the distinct values in order be $v_1<v_2<\cdots<v_t$, and let $c_j$ be the length of the $j$-th run, so $c_1+\cdots+c_t=M$. Write $K_j=c_1+\cdots+c_j$ and $K_0=0$.

Block $j$ means the outputs with indices $k\in[K_{j-1}+1,,K_j]$. Its positions are $p_{K_{j-1}},\dots,p_{K_j-1}$: that is $c_j$ positions and $c_j-1$ moves. Its entry position is $x_j:=p_{K_{j-1}}$, and note $x_1=p_0$.

Claim 7 (The entry tile carries exactly that block's value)¶

If solvable then $T_{x_j}=v_j$ for every $j$. Moreover for $j\ge2$ the entry tile is freshly stepped on: $x_j\notin V_{K_{j-1}-1}$.

Proof¶

For $j=1$: $S_1=\max{T_{p_0}}=T_{p_0}$, so $T_{x_1}=v_1$.
For $j\ge2$, by Claim 5 the maximum just before entering is $\max_{i\in V_{K_{j-1}-1}}T_i=S_{K_{j-1}}$, which equals $v_{j-1}$.
Right after entering it is $\max_{i\in V_{K_{j-1}}}T_i=S_{K_{j-1}+1}$, which equals $v_j$.
The two sets differ by at most one element, since $V_{K_{j-1}}=V_{K_{j-1}-1}\cup{x_j}$.
The maximum strictly increased, so the newly added element must be responsible: $x_j$ is new and $T_{x_j}=v_j$. $\square$

Claim 8 (A block is confined to one maximal run)¶

Let $R_j:=[A_j,B_j]$ be the maximal contiguous interval containing $x_j$ whose values are all $\le v_j$. Concretely, $A_j-1$ is the nearest position left of $x_j$ with $T>v_j$ (or $A_j=1$ if none), and $B_j+1$ is the nearest position right of $x_j$ with $T>v_j$ (or $B_j=N$ if none).

Then every position of block $j$ lies in $R_j$: $p_k\in R_j$ for all $k\in[K_{j-1},,K_j-1]$.

Moreover the runs are nested: $R_1\subsetneq R_2\subsetneq\cdots\subsetneq R_t$.

Proof¶

For such a $k$, Claim 5 gives $\max_{i\in V_k}T_i=S_{k+1}=v_j$. So every tile in $V_k$ has value $\le v_j$.
By Claim 2, $V_k$ is an interval, and it contains $x_j$ because $k\ge K_{j-1}$.
So $V_k$ is an interval containing $x_j$ with all values $\le v_j$. Such intervals are closed under union, so there is a unique maximal one, namely $R_j$, and $V_k\subseteq R_j$. In particular $p_k\in R_j$.
Nesting: by Claim 9, $x_{j+1}$ sits immediately outside an endpoint of $R_j$, so $R_j\cup{x_{j+1}}$ is an interval. All its values are $\le v_{j+1}$ and it contains $x_{j+1}$, so it is contained in the maximal such interval $R_{j+1}$. $\square$

Note. Claim 7 gives $T_{x_j}=v_j$, so the conditions "values $\le v_j$" and "values $\le T_{x_j}$" coincide. Hence $R_j$ is just the stretch between the nearest strictly greater element on each side of $x_j$ — computable for every position in $O(N)$ with a monotonic stack, independently of $j$.

Claim 9 (You can only leave a block through an endpoint)¶

Suppose the instance is solvable and $j<t$. Then at the last moment of block $j$ the robot sits on an endpoint: $p_{K_j-1}\in{A_j,B_j}$.

Correspondingly the next entry is the tile just outside, $x_{j+1}=A_j-1$ or $x_{j+1}=B_j+1$, and its value must be exactly the next block's value: $T_{x_{j+1}}=v_{j+1}$.

Proof¶

Claim 7 gives $T_{x_{j+1}}=v_{j+1}$, and $v_{j+1}>v_j$.
All values inside $R_j$ are $\le v_j$, so $x_{j+1}\notin R_j$.
By Claim 8, $p_{K_j-1}\in R_j$, and $x_{j+1}$ is adjacent to it.
A position adjacent to a point of $[A_j,B_j]$ but outside it can only be $A_j-1$ or $B_j+1$; that forces the previous position to be $A_j$ or $B_j$ respectively.
The exit value cannot exceed $v_{j+1}$ (the prefix maximum would skip over $v_{j+1}$) and cannot be below it (being outside $R_j$ forces a value $>v_j$). So it equals $v_{j+1}$. $\square$

Claim 10 (Timing lemma for movement inside a block)¶

Fix an interval $[A,B]$, two of its points $e$ and $y$, a distance $d=|e-y|$, and a step count $s\ge0$. A walk of exactly $s$ steps from $e$ to $y$ that never leaves $[A,B]$ exists iff all three hold:

it is long enough: $d\le s$;

the parities match: $d\equiv s\pmod 2$;

there is room to idle: $d=s$, or else $B>A$.

Proof¶

Necessity of the first two: each step changes the position by $\pm1$, so after $s$ steps the displacement is at most $s$ and has the same parity as $s$.
Necessity of the third: if $d<s$ and $A=B$, the interval is a single tile so the robot cannot move, yet $s>0$ forces a move — contradiction.
Sufficiency: walk straight from $e$ to $y$ in $d$ steps. The leftover $s-d$ is a non-negative even number.
If the leftover is positive then $B>A$, so $y$ has a neighbour $z$ inside $[A,B]$; oscillate $y\to z\to y$ exactly $(s-d)/2$ times. $\square$

Corollary (survival lemma). A walk of exactly $s$ steps from $e\in[A,B]$ that never leaves $[A,B]$ exists iff $s=0$ or $B>A$. (Take $y=e$ or $y$ a neighbour of $e$, covering both parities.)

Claim 11 (Sufficiency: gluing the conditions back into a full walk)¶

Suppose positions $x_1,\dots,x_t$ exist with:

the right values: $T_{x_j}=v_j$ for every $j$;

for each $j<t$, an endpoint $y_j\in{A_j,B_j}$ that is reachable from $x_j$ under Claim 10 inside $R_j$ with $s=c_j-1$, such that the tile immediately outside is the next entry: $x_{j+1}=y_j\mp1$ with $T_{x_{j+1}}=v_{j+1}$;

for $j=t$, the survival condition: $c_t=1$ or $|R_t|\ge2$.

Then the instance is solvable.

Proof¶

Concatenate: block $j$ starts at $x_j$, spends $c_j-1$ steps inside $R_j$ reaching $y_j$, then one move crosses out to $x_{j+1}$. The last block just survives $c_t-1$ steps inside $R_t$.
Move count: $\sum_j(c_j-1)$ inside blocks plus $t-1$ crossings equals $M-1$, giving exactly $M$ positions $p_0,\dots,p_{M-1}$ as required by Claim 5.
Legality: every $R_j\subseteq[1,N]$ and every $x_{j+1}$ is a real tile, so the walk stays in bounds.
Prefix maxima: by the nesting in Claim 8, all positions of blocks $1..j$ lie in $R_j$, so their values are $\le v_j$; and $x_j$ is visited with $T_{x_j}=v_j$. Hence at every time $k$ inside block $j$ we get $\max_{i\in V_k}T_i=v_j=S_{k+1}$.
Claim 5 converts this walk into a solution of the original problem. $\square$

Claims 7–10 (necessity) plus Claim 11 (sufficiency) give an exact characterisation: solvable iff such a sequence $x_1,\dots,x_t$ exists.

Claim 12 (It becomes a forward recurrence whose state is a single position)¶

Let $E_j$ be the set of positions that can serve as the entry $x_j$ of block $j$, i.e. those $x$ with $T_x=v_j$ for which some legal $x_1,\dots,x_{j-1}$ completes the first $j-1$ blocks. Then:

the base is everything with the first value: $E_1={x: T_x=v_1}$;

the step, for each $x\in E_j$, adds up to two positions to $E_{j+1}$: it adds $A_x-1$ if the left endpoint is reachable and $T_{A_x-1}=v_{j+1}$, and it adds $B_x+1$ if the right endpoint is reachable and $T_{B_x+1}=v_{j+1}$;

the answer is YES iff some $x\in E_t$ satisfies the survival condition.

Here $[A_x,B_x]$ depends on $x$ only, and "reachable" depends only on $x$, $[A_x,B_x]$ and $s=c_j-1$.

Proof¶

Claim 9 says $x_{j+1}$ can only be $A_j-1$ or $B_j+1$, and $R_j$ is fully determined by $x_j$ (Note after Claim 8).
Claim 10 says whether block $j$ can reach a given endpoint is determined by $x_j$ and the fixed budget $c_j-1$.
So the only thing "blocks $1..j$ are feasible" contributes to the future is the single position $x_{j+1}$: no other information about $x_1,\dots,x_j$ is needed. That is exactly the recurrence above.
The stopping test is condition 3 of Claim 11. $\square$

Claim 13 (One sweep in increasing order of value suffices)¶

The sets $E_j$ are pairwise disjoint, and $j$ is recoverable from the value alone. Processing all positions in increasing order of $T_x$ therefore guarantees that when $x$ is processed, every transition that could put it into some $E_j$ has already happened. One boolean array entry[] suffices.

Proof¶

Membership $x\in E_j$ forces $T_x=v_j$, and the $v_j$ are distinct. So the $E_j$ are disjoint, and $j$ is determined by $T_x$ via a lookup table idx[value].
A transition from $E_j$ marks only positions of value $v_{j+1}$, and $v_{j+1}>v_j$. So it always writes to a strictly larger value, i.e. to a position not yet processed.
There are no transitions within one value, so the order inside a layer is arbitrary. $\square$

Final flowchart¶

read T, S
├─ S not non-decreasing ─────────────► NO
├─ compress S into (v[1..t], c[1..t]); idx[v[j]] = j
├─ monotonic stack: for each position x compute its run [A[x], B[x]]
│     (the stretch between the nearest strictly greater elements on each side)
└─ sweep positions x in increasing order of T[x]:
      j := idx[T[x]];  if j == 0, skip (this value never occurs in S)
      if j >= 2 and entry[x] == false, skip
      a, b := A[x], B[x];  avail := c[j] - 1;  sz := b - a + 1
      ├─ j == t :  avail == 0 or sz >= 2  ──────────────► YES
      └─ j <  t :
            a reachable  (|x-a| <= avail, same parity,
                          and |x-a| == avail or sz >= 2)
                  and a > 1 and T[a-1] == v[j+1]   ──►  entry[a-1] = true
            b reachable  (symmetric)
                  and b < N and T[b+1] == v[j+1]   ──►  entry[b+1] = true
   sweep finished without success ────► NO

Complexity: $O(N)$ for the monotonic stack, $O(N\log N)$ to sort by value (counting sort gives $O(N+V)$), $O(N)$ for the sweep, $O(N+M)$ for input.

Credits & sources

Statements summarised from the official AIO 2025 papers on ORAC (Australian Mathematics Trust); approaches cross-checked with the ORAC editorials. The two proof notes are our lesson notes of 23 and 30 July, unchanged apart from heading levels. The other explanations and code are ours; Pairing Cards and Robot Writing were checked against brute force on thousands of random cases.