Overview

We freely choose how to fill in the password \(S\) and the order of sending to agents, maximizing the number of successful authentications.
Although \(L\) is large, \(N,K \leq 8\) is small, so we enumerate all sending orders while only considering “the \(S\) required for success at each point” as candidates.

Analysis

The key observation is that once a sending order is fixed, the transformation rule \(C\) at each point does not depend on the password \(S\).

This is because the update after sending is always performed as

\[ C' = A_i \circ C \]

regardless of whether authentication succeeds or fails.

Therefore, once the sending order is determined, the \(C\) immediately before sending to each agent is uniquely determined.

---

Suppose at some point the transformation rule is \(C\) and the recipient is agent \(i\).

The condition for successful authentication is that for all positions \(j\):

\[ C_{S_j} = T_{i,j} \]

Since \(C\) is a permutation, the inverse map \(C^{-1}\) exists. Therefore, the password required to make agent \(i\) succeed at this point is uniquely determined:

\[ S_j = C^{-1}(T_{i,j}) \]

For example, if the current transformation is

\[ 1 \mapsto 2,\quad 2 \mapsto 3,\quad 3 \mapsto 1 \]

and the authentication code is \((3,1,1)\), then the required password is \((2,3,3)\).

However, if this candidate contradicts the fixed positions in memo \(B\), then it is impossible to make that agent succeed at that point.

---

In other words, once a sending order is fixed, each sending point corresponds to either:

• A candidate \(S\) such that “this password leads to success”
• Or “success is impossible for any valid \(S\)”

Therefore, for a fixed sending order, by counting how many times the same candidate password appears, we can determine the number of successes when choosing that password.

For example, if the candidates for a certain sending order appear as

\[ X, Y, X, Z, X \]

then by choosing password \(X\), we can achieve \(3\) successful authentications.

---

Naively trying all passwords, when there are many undetermined positions, gives up to

\[ K^L \]

possibilities, which is completely infeasible for \(K=8, L=200\).

On the other hand, the number of sending orders is at most

\[ 8! = 40320 \]

so it suffices to enumerate all sending orders and only examine the candidate passwords that appear.

If the optimal number of successes is at least \(1\), then at least one sending point has a success, so that password will necessarily appear as a candidate through this method.

If the maximum number of successes is \(0\), then no password can achieve success, so we output the lexicographically smallest one satisfying memo \(B\), i.e., the one with all undetermined positions set to \(1\).

Algorithm

We enumerate all sending orders using DFS.

The DFS state consists of:

• The set of agents already sent to: mask
• The current depth: depth
• The current transformation rule \(C\)
• The candidate password IDs at each sending point so far

At each state, we choose the next agent \(i\) that hasn’t been sent to yet.

1. Compute the candidate password

From the current \(C\), we construct the inverse map \(C^{-1}\).

The password \(U\) required to make agent \(i\) succeed at this point is

\[ U_j = C^{-1}(T_{i,j}) \]

We check whether this \(U\) contradicts the fixed positions in memo \(B\).

• If there is a contradiction: there is no valid password that can succeed at this point, so set the ID to -1
• If there is no contradiction: register \(U\) as a candidate password and obtain its ID

Identical passwords are grouped under the same ID using an unordered_map.

2. Update the transformation rule

The transformation rule after sending to agent \(i\) is

\[ C'_x = A_{i,C_x} \]

In code, this is computed as

nextC[x] = Aperm[i][C[x]];

3. Update when all agents have been sent to

When the depth reaches \(N\), one complete sending order has been formed.

The candidate password IDs at each point in this sending order have been recorded.

We count how many times the same ID appears and update bestCnt[id] with that maximum value.

That is, bestCnt[id] represents:

When choosing password ID id, the maximum number of people that can succeed under some sending order.

4. Choose the answer

After the full enumeration, we examine bestCnt for all candidate passwords.

• Choose the one with the maximum bestCnt
• If multiple have the same number of successes, choose the lexicographically smallest password

If the maximum number of successes is \(0\), we don’t use any candidate password and instead output the one with all undetermined positions in memo \(B\) set to \(1\).

Complexity

Let the number of edges in the DFS tree of sending orders be

\[ E = \sum_{r=1}^{N} {}_NP_r \]

Since \(N \leq 8\), this is sufficiently small at maximum.

Since we construct a candidate password of length \(L\) at each edge, the complexity is approximately:

• Time complexity: \(O(E(L+K) + N! \cdot N^2)\)
• Space complexity: \(O(E \cdot L)\)

Here, \(O(E \cdot L)\) is the space for storing candidate passwords as strings.

Under the constraints, even \(N=8, L=200\) is well within limits.

Implementation Notes

• Input values are converted to \(0\)-indexed for easier handling.

• Undetermined positions where \(B_j=0\) are managed as -1 in the code.

• By storing only the fixed positions in fixedPos, we can efficiently check whether a candidate password contradicts \(B\).

• Candidate passwords are converted to string and assigned IDs using an unordered_map.

  • Since each element is a small value from \(1\) to \(K\), storing them as characters allows lexicographic comparison to work directly.

• When ans == 0, any password achieves a maximum success count of \(0\), so we set all undetermined positions to \(1\) to be lexicographically smallest.

  Source Code

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

int N, K, L;
vector<int> Bv, fixedPos;
vector<vector<int>> T;
vector<array<int, 8>> Aperm;

unordered_map<string, int> idMap;
vector<int> bestCnt;
array<int, 8> pathIds;

int getId(const array<int, 8>& invC, int agent) {
    const auto& Ti = T[agent];

    for (int pos : fixedPos) {
        if (invC[Ti[pos]] != Bv[pos]) return -1;
    }

    string s;
    s.resize(L);
    for (int j = 0; j < L; ++j) {
        s[j] = char(invC[Ti[j]] + 1);
    }

    auto it = idMap.find(s);
    if (it != idMap.end()) return it->second;

    int id = (int)bestCnt.size();
    bestCnt.push_back(0);
    idMap.emplace(std::move(s), id);
    return id;
}

void updateLeaf() {
    for (int a = 0; a < N; ++a) {
        int id = pathIds[a];
        if (id < 0) continue;

        bool seen = false;
        for (int b = 0; b < a; ++b) {
            if (pathIds[b] == id) {
                seen = true;
                break;
            }
        }
        if (seen) continue;

        int cnt = 0;
        for (int b = a; b < N; ++b) {
            if (pathIds[b] == id) ++cnt;
        }
        bestCnt[id] = max(bestCnt[id], cnt);
    }
}

void dfs(int depth, int mask, const array<int, 8>& C) {
    if (depth == N) {
        updateLeaf();
        return;
    }

    array<int, 8> invC{};
    for (int x = 0; x < K; ++x) {
        invC[C[x]] = x;
    }

    for (int i = 0; i < N; ++i) {
        if (mask & (1 << i)) continue;

        int id = getId(invC, i);
        pathIds[depth] = id;

        array<int, 8> nextC{};
        for (int x = 0; x < K; ++x) {
            nextC[x] = Aperm[i][C[x]];
        }

        dfs(depth + 1, mask | (1 << i), nextC);
    }
}

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

    cin >> N >> K >> L;

    Bv.resize(L);
    for (int j = 0; j < L; ++j) {
        int x;
        cin >> x;
        if (x == 0) {
            Bv[j] = -1;
        } else {
            Bv[j] = x - 1;
            fixedPos.push_back(j);
        }
    }

    T.assign(N, vector<int>(L));
    Aperm.resize(N);

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < L; ++j) {
            cin >> T[i][j];
            --T[i][j];
        }
        for (int k = 0; k < K; ++k) {
            cin >> Aperm[i][k];
            --Aperm[i][k];
        }
    }

    long long edges = 0, p = 1;
    for (int r = 1; r <= N; ++r) {
        p *= (N - r + 1);
        edges += p;
    }

    idMap.max_load_factor(0.7);
    idMap.reserve((size_t)edges);

    array<int, 8> initC{};
    for (int x = 0; x < K; ++x) initC[x] = x;

    dfs(0, 0, initC);

    int ans = 0;
    string bestS;
    bool found = false;

    for (const auto& kv : idMap) {
        int cnt = bestCnt[kv.second];
        if (cnt > ans || (cnt == ans && cnt > 0 && (!found || kv.first < bestS))) {
            ans = cnt;
            bestS = kv.first;
            found = true;
        }
    }

    if (ans == 0) {
        bestS.resize(L);
        for (int j = 0; j < L; ++j) {
            bestS[j] = char((Bv[j] == -1 ? 0 : Bv[j]) + 1);
        }
    }

    cout << ans << '\n';
    for (int j = 0; j < L; ++j) {
        if (j) cout << ' ';
        cout << (int)(unsigned char)bestS[j];
    }
    cout << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.