Skip to content

AIO 2023

AIO 2023 was a 5 August lesson. Most files below are the versions written in class, so their style is a little freer than our usual template.

# Problem Main idea Difficulty Related page
1 TeleTrip a set of visited positions ★ std::set
2 Distincto's Raffle counting array ★ —
3 Making Bank take the earliest classes; try every number of classes ★★ Greedy
4 Shoptimality split $ H - S $ into left and right; running minimum
5 Wheeling and Dealing fix the winning vote count; two heaps ★★★★ Greedy
6 Yet Another Lights Problem XOR equations for rows and columns ★★★★★ Bit Operations

1. TeleTrip

ORAC problem 1299

Statement. You walk along an infinite street following \(N\) instructions: L one house left, R one house right, T teleport home. How many different houses (including your own) do you visit?

Idea. Keep your position as an integer (home is \(0\)) and insert every position into a set; the answer is its size. RRTRRRR visits \(0, 1, 2, 0, 1, 2, 3, 4\): five different houses.

(The code counts L as \(+1\) and R as \(-1\). The mirror image visits the same number of houses.)

TeleTrip.cpp
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n;
    string s;
    cin >> n >> s;

    int x = 0;
    set<int> st = {x};
    for (auto i: s) {
        if (i == 'L') {
            x++;
        }
        if (i == 'R') {
            x--;
        }
        if (i == 'T') {
            x = 0;
        }
        st.insert(x);
    }

    cout << st.size();


    return 0;
}

2. Distincto's Raffle

ORAC problem 1302

Statement. \(N\) people each submit a number from \(1\) to \(K\). Numbers submitted by two or more people are thrown away. Print the smallest remaining number, or \(-1\).

Idea. Count how often each number appears with cnt[v], then scan \(v = 1, 2, \dots\) for the first cnt[v] == 1. For 9 2 5 2: 2 appears twice, the smallest single one is 5.

Distincto's Raffle.cpp
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> cnt(k + 1);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        cnt[a]++;
    }
    int ans = k + 1;
    for (int i = 1; i <= k; i++) {
        if (cnt[i] == 1) {
            ans = i;
            break;
        }
    }
    if (ans == k + 1) {
        ans = -1;
    }

    cout << ans;
    return 0;
}

3. Making Bank

ORAC problem 1297

Statement. You have \(N\) days and skill \(s = 1\). On a C day you may attend a class (\(s\) increases by 1) or paint (earn \(s\) dollars); on an M day you must paint. Maximise your money.

Idea.

  1. If you attend \(k\) classes, attend them on the first \(k\) C days: moving a class earlier can only raise the skill on later painting days.
  2. Start from "no classes": \(N\) dollars. Now add classes one by one. Turning the \(k\)-th C day (at index \(i\)) into a class loses that day's pay, which was \(k\) (skill before this class), and adds \(1\) dollar on every later day, \(N - i - 1\) of them. So the money changes by \((N - i - 1) - k\).
  3. Try every \(k\) and keep the best.

Sample 1 MCCCC: 5 dollars with no classes; class at \(i=1\): \(+ (3 - 1) = 7\); class at \(i=2\): \(+(2 - 2) = 7\); class at \(i=3\): \(+(1-3) = 5\). Best \(7\).

Making Bank.cpp
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n;
    string s;
    cin >> n >> s;

    ll money = n;

    ll best = n;

    ll k = 0; // the class we took

    for (int i = 0; i < n; i++) {
        if (s[i] == 'C') {
            k++;
            money += (n - i - 1) - k;
            best = max(best, money);
        }
    }

    cout << best;
    return 0;
}

4. Shoptimality

ORAC problem 1301

Statement. Houses at sorted positions \(H_1 < \dots < H_N\) and supermarkets at sorted positions \(S_1 < \dots < S_M\) with price factors \(P_j\). The badness of supermarket \(j\) for house \(i\) is \(P_j + |H_i - S_j|\). For every house print the smallest badness.

Idea.

  1. Remove the absolute value by splitting into two cases.
    • Shop to the left (\(S_j \le H_i\)): badness \(= (P_j - S_j) + H_i\).
    • Shop to the right (\(S_j \ge H_i\)): badness \(= (P_j + S_j) - H_i\).
  2. For the left case, sweep houses from left to right. Every shop that is now to the left of the current house stays to the left of all later houses, so keep a running minimum of \(P_j - S_j\) and advance a pointer over the shops.
  3. Mirror it for the right case, sweeping from the right with \(P_j + S_j\).
  4. Each house's answer is the smaller of its two values. Both sweeps are \(O(N + M)\).

Sample 3: shops \((2, 10)\) and \((9, 1)\). House at \(1\) has only right shops: \(\min(10 + 2, 1 + 9) - 1 = 9\).

Shoptimality.cpp
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

constexpr ll inf = 4e18;

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

    int n = 0, m = 0;
    cin >> n >> m;

    vector<ll> h(n), s(m), p(m), ans(n);

    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    for (int j = 0; j < m; j++) {
        cin >> s[j];
    }
    for (int j = 0; j < m; j++) {
        cin >> p[j];
    }

    // shops to the left: minimize p[j] - s[j], then add h[i]
    ll best = inf;
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j < m && s[j] <= h[i]) {
            best = min(best, p[j] - s[j]);
            j++;
        }
        ans[i] = (best == inf) ? inf : best + h[i];
    }

    // shops to the right: minimize p[j] + s[j], then subtract h[i]
    best = inf;
    j = m - 1;
    for (int i = n - 1; i >= 0; i--) {
        while (j >= 0 && s[j] >= h[i]) {
            best = min(best, p[j] + s[j]);
            j--;
        }
        if (best != inf) {
            ans[i] = min(ans[i], best - h[i]);
        }
    }

    for (int i = 0; i < n; i++) {
        cout << ans[i] << (i + 1 < n ? ' ' : '\n');
    }

    return 0;
}

5. Wheeling and Dealing

ORAC problem 1298

Statement. \(N\) candidates, \(M\) voters; voter \(i\) plans to vote for \(V_i\) and can be paid \(P_i\) to vote for anyone. Candidate 1 must get strictly more votes than every other candidate. Minimise the total payment.

Idea. Fix \(T\) = the number of votes candidate 1 will end with, and try every \(T\).

  1. Every other candidate \(j\) must end with at most \(T - 1\) votes. If \(j\) has \(\text{cnt}_j \ge T\) voters, we must buy \(\text{cnt}_j - T + 1\) of them, obviously the cheapest ones. Bought voters vote for candidate 1.
  2. After that, candidate 1 has its own voters plus the forced ones. If that is still fewer than \(T\), buy the cheapest remaining voters from anyone else (the "pool") until it reaches \(T\).
  3. Cost for this \(T\) = forced cost + cost of the cheapest extra voters. Answer = minimum over all \(T\).

Making it fast. As \(T\) grows by one, each candidate needs one fewer forced purchase, so exactly the voters whose "release level" is \(T\) move from forced into the pool. The number of extra voters needed only grows. Two heaps keep the cheapest \(K\) pool voters and their sum: a max-heap sel for the chosen ones and a min-heap rest for the others; a new pool voter cheaper than the most expensive chosen one is swapped in. Every voter moves between heaps \(O(1)\) times: \(O(M \log M)\).

Sample 1: pay \(1\) to move the fourth voter (to candidate 2) and \(4\) to move the fifth voter to candidate 1: total \(5\).

Wheeling and Dealing.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

priority_queue<int> sel; // the K cheapest (max-heap)
priority_queue<int, vector<int>, greater<int> > rest; // everyone else (min-heap)
ll selSum = 0;

void addPool(int x) {
    rest.push(x);
    if (!sel.empty() && rest.top() < sel.top()) {
        // the newcomer is cheaper, swap it in
        int a = rest.top();
        rest.pop();
        int b = sel.top();
        sel.pop();
        selSum += a - b;
        sel.push(a);
        rest.push(b);
    }
}

void growTo(ll K) {
    while ((ll) sel.size() < K) {
        int a = rest.top();
        rest.pop();
        sel.push(a);
        selSum += a;
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> v(m), p(m), cnt(n + 1, 0);
    for (auto &x: v) scanf("%d", &x);
    for (auto &x: p) scanf("%d", &x);
    for (int i = 0; i < m; i++) cnt[v[i]]++;

    vector<vector<int> > lst(n + 1);
    for (int i = 0; i < m; i++) if (v[i] != 1) lst[v[i]].push_back(p[i]);
    for (int j = 2; j <= n; j++) sort(lst[j].begin(), lst[j].end());

    // T=1: every voter not for candidate 1 must be bought
    ll c1 = cnt[1], forcedSum = 0, forcedCnt = 0;
    vector<vector<int> > rel(m + 2); // rel[T] = voters released at level T
    for (int j = 2; j <= n; j++)
        for (int idx = 0; idx < (int) lst[j].size(); idx++) {
            forcedSum += lst[j][idx];
            forcedCnt++;
            int T = cnt[j] - idx + 1;
            if (T <= m) rel[T].push_back(lst[j][idx]);
        }

    ll ans = LLONG_MAX;
    for (int T = 1; T <= m; T++) {
        for (int c: rel[T]) {
            forcedSum -= c;
            forcedCnt--;
            addPool(c);
        }
        ll K = max(0LL, (ll) T - c1 - forcedCnt);
        growTo(K);
        ans = min(ans, forcedSum + selSum);
    }
    printf("%lld\n", ans == LLONG_MAX ? 0 : ans);
}

Code comments translated from Chinese; the code itself is unchanged.

Checked against brute force (every voter kept or bought for every candidate) on 300 random small cases.

6. Yet Another Lights Problem

ORAC problem 1300

Statement. An \(R \times C\) grid of lights, each on (*) or off (.). A cross-flip at \((a, b)\) toggles every light in row \(a\) and every light in column \(b\) (the light \((a, b)\) itself once). Print at most \(40\,000\) cross-flips that turn all lights on, or \(-1\).

Idea.

  1. Order does not matter and flipping the same cell twice cancels out, so a solution is just a 0/1 value \(x_{r,c}\) ("flip this cell or not").
  2. Let \(\text{row}_r\) be the parity of flips in row \(r\) and \(\text{col}_c\) the parity in column \(c\). Light \((r, c)\) is toggled by the flips in its row, plus those in its column except itself, so its toggle parity is \(\text{row}_r \oplus \text{col}_c \oplus x_{r,c}\). It must equal \(d_{r,c}\) = 1 if the light starts off. Hence $$ x_{r,c} = d_{r,c} \oplus \text{row}_r \oplus \text{col}_c . $$
  3. So a solution is determined by choosing one bit \(u_r\) per row and \(v_c\) per column, then flipping every cell with \(d_{r,c} \oplus u_r \oplus v_c = 1\), as long as the choice is consistent: the row parities of the resulting \(x\) must really be \(u\) (up to flipping all of \(u\) and \(v\) together, which gives the same \(x\)).
  4. Writing that consistency out with XOR sums \(D_r\) (row sums of \(d\)), \(E_c\) (column sums) and \(T\) (total) splits into cases by the parity of \(R\) and \(C\):
    • both even: always solvable, take \(u_r = T \oplus D_r\), \(v_c = T \oplus E_c\);
    • \(C\) even, \(R\) odd: solvable only if all \(E_c\) are equal; \(R\) even, \(C\) odd: only if all \(D_r\) are equal;
    • both odd: all \(D_r\) equal and all \(E_c\) equal.
  5. Print the cells with \(d \oplus u \oplus v = 1\): at most \(R \cdot C = 40\,000\) flips.

Sample 3 (*.., .*., ...) has odd \(R\) and \(C\) with unequal row sums, so the answer is \(-1\).

Yet Another Lights Problem.cpp
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int R, C;
    cin >> R >> C;

    vector<string> s(R);
    for (auto &x: s) {
        cin >> x;
    }

    vector<vector<int> > d(R, vector<int>(C));
    vector<int> D(R), E(C);


    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            d[r][c] = (s[r][c] == '.');
            D[r] ^= d[r][c];
            E[c] ^= d[r][c];
        }
    }

    int T = 0;
    for (int r = 0; r < R; r++) {
        T ^= D[r];
    }

    bool okD = true, okE = true;
    for (int r = 0; r < R; r++) {
        if (D[r] != D[0]) {
            okD = false;
        }
    }
    for (int c = 0; c < C; c++) {
        if (E[c] != E[0]) {
            okE = false;
        }
    }

    if ((C % 2 && !okD) || (R % 2 && !okE)) {
        cout << "-1\n";
        return 0;
    }

    vector<int> u(R), v(C);

    if (C % 2 == 0 and R % 2 == 0) {
        for (int r = 0; r < R; r++) {
            u[r] = T ^ D[r];
        }
        for (int c = 0; c < C; c++) {
            v[c] = T ^ E[c];
        }
    } else if (C % 2 == 0) {
        for (int r = 0; r < R; r++) {
            u[r] = T ^ D[r];
        }
        v[0] = E[0] ^ T;
    } else if (R % 2 == 0) {;
        u[0] = D[0] ^ T;
        for (int c = 0; c < C; c++) {
            v[c] = T ^ E[c];
        }
    } else {
        u[0] = E[0];
        v[0] = D[0];
    }

    vector<pair<int, int> > ans;
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            if (u[r] ^ v[c] ^ d[r][c]) {
                ans.push_back({r, c});
            }
        }
    }

    cout << ans.size() << "\n";
    for (auto [r,c]: ans) {
        cout << r << " " << c << "\n";
    }

    return 0;
}

This output is not unique. We checked the program with a validity checker against brute force over all flip subsets on 400 random grids up to \(4 \times 4\).

Credits & sources

Statements summarised from the official AIO 2023 papers on ORAC (Australian Mathematics Trust). Explanations are ours; the code is from the 5 August lesson.