USACO 2026 Third Contest Bronze Division - Swap to Win#

Problem link: here

Problem Solution#

We must turn \(s_1\) into \(t\) using at most \(2M\) operations: a swap of two characters inside one string, or a swap of the \(k\)-th characters of two strings. The plan is to fix the columns of \(s_1\) from left to right, paying at most two operations per column.

Both operations preserve the multiset of all \(NM\) characters, so the solvability guarantee implies that this multiset contains, for every letter, at least as many copies as \(t\) requires. The strings \(s_2,\dots,s_N\) thus form a freely rearrangeable pool: a type-1 swap can move any of their characters to any column of its row, and a type-2 swap can then lift it into \(s_1\). Every letter we need is therefore reachable --- either inside \(s_1\) to the right of the current column, or in some other string.

Therefore, we scan \(i=1,\dots,M\); once column \(i\) of \(s_1\) matches \(t[i]\), never touch it again. If \(s_1[i]\neq t[i]\), first search \(s_1[i+1..M]\) for the letter \(t[i]\): a copy found at position \(j\) costs only one type-1 swap of \(i\) and \(j\), the cheapest option.

Otherwise the letter must come from another row. Keep, for each of the 26 letters, a list of positions in rows \(2..N\) where it may occur. Entries go stale as characters move, so discard the top entry while the character stored there no longer matches the letter. Once a genuine position \((r,c)\) with \(s_r[c]=t[i]\) is found, swap columns \(c\) and \(i\) inside row \(r\) (type 1) to bring the letter to column \(i\), then swap the \(i\)-th characters of rows \(1\) and \(r\) (type 2). Neither operation touches columns \(\lt i\) of \(s_1\), so previously fixed columns stay correct. Each column costs at most two operations, giving at most \(2M\) in total.

Why It Never Gets Stuck#

\(\textit{Invariant:}\) before fixing column \(i\), the characters of rows \(2..N\) together with the suffix \(s_1[i..M]\) contain, for each letter, at least as many copies as \(t[i..M]\) requires. This holds initially by the counting observation above. Fixing column \(i\) locks exactly one copy of \(t[i]\) into \(s_1[i]\), while the displaced character either stays inside the suffix of \(s_1\) (first case) or lands in row \(r\ge 2\) (second case) --- so it remains in the pool. The invariant is preserved, and the letter \(t[i]\) is always found; when \(N=1\), the first case always applies.

Each operation appends \(O(1)\) entries to the position lists, and every discarded stale entry is paid for by the operation that created it (an \(\textit{amortized}\) argument: each entry is created once and destroyed at most once). One test therefore runs in \(O(NM)\) time and memory --- easily fast enough for \(N,M\le 1000\) and \(T\le 10\).

Source code#

The source code for the solution in C++ can be seen below.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MAX_N = 1000;
const int MAX_M = 1000;

struct Operation {
    int type;
    int a;
    int b;
    int c;
};

string s[MAX_N + 1];
vector<pair<int, int>> positions[26];
vector<Operation> operations;

void add_position(int row, int column) {
    int letter = s[row][column] - 'a';
    positions[letter].push_back({row, column});
}

void solve() {
    int n, m;
    cin >> n >> m;

    string t;
    cin >> t;

    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }

    for (int c = 0; c < 26; c++) {
        positions[c].clear();
    }

    operations.clear();

    for (int row = 2; row <= n; row++) {
        for (int column = 0; column < m; column++) {
            add_position(row, column);
        }
    }

    for (int i = 0; i < m; i++) {
        if (s[1][i] == t[i]) {
            continue;
        }

        int found = -1;

        for (int j = i + 1; j < m; j++) {
            if (s[1][j] == t[i]) {
                found = j;
                break;
            }
        }

        if (found != -1) {
            operations.push_back({1, 1, i + 1, found + 1});

            swap(s[1][i], s[1][found]);

            continue;
        }

        int letter = t[i] - 'a';

        while (true) {
            int row = positions[letter].back().first;
            int column = positions[letter].back().second;

            if (s[row][column] == t[i]) {
                break;
            }

            positions[letter].pop_back();
        }

        int row = positions[letter].back().first;
        int column = positions[letter].back().second;

        if (column != i) {
            operations.push_back({1, row, column + 1, i + 1});

            swap(s[row][column], s[row][i]);

            add_position(row, column);
            add_position(row, i);
        }

        operations.push_back({2, 1, row, i + 1});

        swap(s[1][i], s[row][i]);

        add_position(row, i);
    }

    cout << operations.size() << "\n";

    for (Operation op : operations) {
        cout << op.type << " "
             << op.a << " "
             << op.b << " "
             << op.c << "\n";
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}