Overview

For each ciphertext and each plaintext, we precompute and update the number of mismatches for all shift amounts, and after each query, we exhaustively search for the minimum cost under “fixed shift + one-to-one correspondence (permutation)” to find the answer.

Analysis

The optimization target of this problem has two stages:

1. Determine the common shift amount \(r\)
2. Determine the correspondence (one-to-one) between ciphertext \(i\) and plaintext \(j\)

Here, if we define \(D[i][j][r]\) as the number of mismatches when comparing ciphertext \(i\) and plaintext \(j\) with shift \(r\), the desired value is:

[ \min{0 \le r < M} \ \min{\text{permutation } \pi} \sum_{i=0}^{N-1} D[i][\pi(i)][r] ]

---

If we naively compute everything from scratch each time: - Building each \(D[i][j][r]\) takes \(O(M)\) - There are \(N^2M\) combinations

This is too heavy, and doing it for every query won’t fit in time.

However, looking at the constraints: - \(N \le 5\) (very small) - \(M,Q \le 500\), and \(MQ \le 5\times 10^4\)

So the following approach is effective:

• Since \(N\) is small, enumerating all correspondences (\(N!\)) is feasible
• Since each change affects only one character, we only need to recompute the affected rows/columns of \(D\)

The key insight is “exhaustively search the small \(N\), incrementally recompute the larger \(M\)”.

Algorithm

1. Managing the Mismatch Table

We maintain a 3D array D[i][j][r].

• Meaning: the number of mismatches when comparing ciphertext i and plaintext j with shift r
• Comparison is only done at positions p where C[i][p]=='0'

recompute_pair(i,j) recomputes this single pair in \(O(M^2)\).
(Iterate over positions p, and for each shift r, compare with T[j][(p+r)%M])

2. Query Updates

• 1 i p x (S update): recompute all j related to ciphertext i
• 2 i p b (C update): same as above
• 3 j p x (T update): recompute all i related to plaintext j

In other words, at most \(N\) pairs are recomputed each time.

3. Computing the Answer

After each query, compute the following:

• For each shift r:
  • For each permutation pm (\(N!\) of them): [ \sum_i D[i][pm[i]][r] ]
  • Let best(r) be the minimum of these
• Output the minimum over all r

Permutations are pre-enumerated using next_permutation and stored in advance.

Complexity

• Time complexity:
  • Initial construction: \(O(N^2M^2)\)
  • Update per query: at most \(N\) pairs recomputed, so \(O(NM^2)\)
  • Answer computation per query: \(O(M \cdot N! \cdot N)\)
  • Therefore, per query: [ O(NM^2 + M\cdot N!\cdot N) ] This is sufficiently fast under the constraints (\(N\le5\)).
• Space complexity: [ O(N^2M) ] (mainly for D)

Implementation Notes

• Input is 1-indexed, but the implementation converts to 0-indexed (--a, --p).

• If the value is the same before and after the update, skip recomputation to avoid unnecessary work.

• Note that for type=3, a refers to “plaintext index j”.

• Positions where C[i][p]=='1' (unreadable positions) are not included in the mismatch check. This is a typical point that causes WA.

  Source Code

#include <bits/stdc++.h>
using namespace std;

static const int INF = 1e9;

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

    int N, M, Q;
    cin >> N >> M >> Q;

    vector<string> S(N), C(N), T(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i] >> C[i];
    }
    for (int j = 0; j < N; j++) cin >> T[j];

    // D[i][j][r]: mismatches between cipher i and plain j with shift r
    vector<vector<vector<int>>> D(N, vector<vector<int>>(N, vector<int>(M, 0)));

    auto recompute_pair = [&](int i, int j) {
        vector<int> &arr = D[i][j];
        fill(arr.begin(), arr.end(), 0);
        for (int p = 0; p < M; p++) {
            if (C[i][p] == '1') continue;
            char sc = S[i][p];
            for (int r = 0; r < M; r++) {
                int tp = p + r;
                if (tp >= M) tp -= M;
                if (sc != T[j][tp]) arr[r]++;
            }
        }
    };

    auto recompute_i_allj = [&](int i) {
        for (int j = 0; j < N; j++) recompute_pair(i, j);
    };
    auto recompute_j_alli = [&](int j) {
        for (int i = 0; i < N; i++) recompute_pair(i, j);
    };

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) recompute_pair(i, j);
    }

    vector<int> perm(N);
    iota(perm.begin(), perm.end(), 0);
    vector<vector<int>> perms;
    do perms.push_back(perm); while (next_permutation(perm.begin(), perm.end()));

    for (int qi = 0; qi < Q; qi++) {
        int type, a, p;
        char x;
        cin >> type >> a >> p >> x;
        --a; --p;

        if (type == 1) {
            if (S[a][p] != x) {
                S[a][p] = x;
                recompute_i_allj(a);
            }
        } else if (type == 2) {
            if (C[a][p] != x) {
                C[a][p] = x;
                recompute_i_allj(a);
            }
        } else { // type == 3
            int j = a;
            if (T[j][p] != x) {
                T[j][p] = x;
                recompute_j_alli(j);
            }
        }

        int ans = INF;
        for (int r = 0; r < M; r++) {
            int best = INF;
            for (const auto &pm : perms) {
                int sum = 0;
                for (int i = 0; i < N; i++) sum += D[i][pm[i]][r];
                if (sum < best) best = sum;
            }
            if (best < ans) ans = best;
        }
        cout << ans << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.3-codex.