calico 2026

calico 2026 was a team programming contest. i competed with edison yang and daniel li. they took problems 9 to 12, the hardest ones, and i took the other eight. we got a perfect score, 100 out of 100. results aren't out yet.

all eight of my solutions are below. the contest gave a template for each problem that handles the input, so these are the solve functions.

shock

earthquakes hit a grid of blocks one after another. each one reaches every block within its radius, and a block's seismometer ends up showing the most recent earthquake that reached it, at a level of p squared minus the squared distance, plus one.

going forward rewrites the same blocks over and over. going backward, from the last earthquake to the first, a block only ever needs to be set once, because the first earthquake to reach it going backward is the most recent one. to skip blocks that are already set, each row keeps a pointer to its next unset block, with path compression like a union-find, so every row of every earthquake jumps straight past the finished blocks.

vector<vector<int>> solve(int N, int M, int Q, vector<int>& X, vector<int>& Y, vector<int>& P) {
    vector<vector<int>> a(N, vector<int>(M, 0));
    vector<int> nx(N * (M + 1));
    iota(nx.begin(), nx.end(), 0);
    auto find = [&](int x) { while (nx[x] != x) x = nx[x] = nx[nx[x]]; return x; };
    for (int i = Q - 1; i >= 0; i--) {
        int r0 = X[i], c0 = Y[i], p = P[i];
        for (int r = r0 - p; r <= r0 + p; r++) {
            int v = p * p - (r - r0) * (r - r0), w = sqrt(v), b = r * (M + 1);
            for (int c = find(b + c0 - w); c - b <= c0 + w; c = find(c))
                a[r][c - b] = v - (c - b - c0) * (c - b - c0) + 1, nx[c] = c + 1;
        }
    }
    return a;
}

forgor

a two-run problem. in the first run the program sees a tree and has to print n numbers. in the second run it gets those numbers back with one of them replaced by -1, and it has to rebuild the tree. the trick is to root the tree at vertex 1 and write down every other vertex's parent, which takes n - 1 numbers, then put the xor of all of them in the spare slot. the whole list xors to zero, so whichever number goes missing is just the xor of the rest.

vector<int> solve_phase1(int N, vector<pair<int, int>>& E) {
    vector<vector<int>> adj(N + 1);
    for (auto [u, v] : E) adj[u].push_back(v), adj[v].push_back(u);
    vector<int> p(N + 1);
    queue<int> q; q.push(1);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (v != 1 && !p[v]) p[v] = u, q.push(v);
    }
    vector<int> A(N);
    for (int v = 2; v <= N; v++) A[v - 1] = p[v], A[0] ^= p[v];
    return A;
}

vector<pair<int, int>> solve_phase2(int N, vector<int>& A) {
    int x = 0, j = 0;
    for (int i = 0; i < N; i++) if (A[i] == -1) j = i; else x ^= A[i];
    A[j] = x;
    vector<pair<int, int>> E;
    for (int i = 1; i < N; i++) E.push_back({i + 1, A[i]});
    return E;
}

galaxy

a grid of red, blue, and blank tiles. big ben can only step on tiles that match his current color, and blank tiles let him switch. one bfs over (tile, color) states labels every connected piece, so each query is just a lookup.

vector<string> solve(int N, int M, int Q, vector<string>& G, vector<pair<int, int>>& start, vector<pair<int, int>>& end) {
    auto ok = [&](int r, int c, int m) {
        return r >= 0 && r < N && c >= 0 && c < M && (G[r][c] == '.' || G[r][c] == (m ? 'R' : 'B'));
    };
    vector<vector<int>> comp(2, vector<int>(N * M, -1));
    int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1}, k = 0;
    auto bfs = [&](int sr, int sc, int sm) {
        queue<array<int, 3>> q;
        comp[sm][sr * M + sc] = k, q.push({sr, sc, sm});
        while (!q.empty()) {
            auto [r, c, m] = q.front(); q.pop();
            if (G[r][c] == '.' && comp[!m][r * M + c] == -1) comp[!m][r * M + c] = k, q.push({r, c, !m});
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (ok(nr, nc, m) && comp[m][nr * M + nc] == -1) comp[m][nr * M + nc] = k, q.push({nr, nc, m});
            }
        }
        k++;
    };
    for (int r = 0; r < N; r++) for (int c = 0; c < M; c++) for (int m = 0; m < 2; m++)
        if (comp[m][r * M + c] == -1 && ok(r, c, m)) bfs(r, c, m);
    vector<string> ans;
    for (int i = 0; i < Q; i++) {
        int s = start[i].first * M + start[i].second, e = end[i].first * M + end[i].second;
        ans.push_back(comp[0][s] == comp[0][e] || comp[0][s] == comp[1][e] ? "YES" : "NO");
    }
    return ans;
}

schedule

classes with one prerequisite each form a tree. each semester it takes up to k of the classes that are available, picking the ones with the longest chain of classes still behind them.

int solve(int N, int M, int K, vector<int> &P){
    vector<vector<int>> ch(N + 1);
    for (int i = 1; i <= N; i++) ch[P[i - 1]].push_back(i);
    vector<int> h(N + 1);
    function<int(int)> dfs = [&](int u) {
        for (int v : ch[u]) h[u] = max(h[u], dfs(v));
        return ++h[u];
    };
    dfs(0);
    priority_queue<pair<int, int>> pq;
    for (int v : ch[0]) pq.push({h[v], v});
    int ans = 0;
    for (int s = 0; s < M && !pq.empty(); s++) {
        vector<int> took;
        while (!pq.empty() && (int)took.size() < K) took.push_back(pq.top().second), pq.pop();
        ans += took.size();
        for (int u : took) for (int v : ch[u]) pq.push({h[v], v});
    }
    return ans;
}

rain

drones fly east or north, and an east drone and a north drone on the same diagonal can run into each other. it groups drones by x + y, sorts the north ones, and binary searches how many each east drone meets.

long long solve(int N, int K, vector<tuple<int, int, int, char>> L){
    long long answer =0;
    vector<pair<int, int>> e, n;
    for (auto [x, y, z, d] : L) if (d == 'E') e.push_back({x + y, x}); else n.push_back({x + y, x});
    sort(n.begin(), n.end());
    answer = (long long)N * K;
    for (auto [s, x] : e) answer -= upper_bound(n.begin(), n.end(), make_pair(s, x + K - 1)) - lower_bound(n.begin(), n.end(), make_pair(s, x));
    return answer;
}

smoke

two smoke charges that recharge one at a time. it walks through the requests in order, refilling charges as time passes, and fails as soon as a request comes in with nothing left.

string solve(int N, int R, vector<int> A) {
    int c = 2, nxt = 0;
    for (int t : A) {
        while (c < 2 && nxt <= t) c++, nxt += R;
        if (!c) return "NO";
        if (c == 2) nxt = t + R;
        c--;
    }
    return "YES";
}

verity

an interactive one. you guess a string and get told which spots are right. every round it fills the unknown spots with the next candidate letter and keeps whatever comes back correct.

void solve(int N, int K, vector<char>& A) {
    string g(N, '?');
    for (char x : A) {
        for (char &c : g) if (c == '?') c = x;
        cout << g << endl;
        string r; cin >> r;
        if (r == "CORRECT") return;
        for (int i = 0; i < N; i++) if (r[i] == '_') g[i] = '?';
    }
}

prompt

the answer was appending the right phrase to an ai prompt, like "make_it_sound_human" when it asks you to write something.

string solve(string S) {
    if (S.find("write_me") != string::npos) return S + "make_it_sound_human";
    if (S.find("what_is") != string::npos) return S + "do_not_hallucinate";
    if (S.find("solve") != string::npos) return S + "make_no_mistakes";
    return S + "thank_you";
}

download the solutions (6 kb zip)