Overview

Under the permutation \(C\) that changes depending on the sending order, the password \(S\) required for each agent to succeed is uniquely determined.
Therefore, we enumerate all sending orders via DFS and count the maximum number of times a “success candidate requiring the same \(S\)” appears.

Analysis

Suppose the device’s transformation rule at a certain point is the permutation \(C\).

Since agent \(i\)’s authentication code is \(T_i\), the condition for successful authentication is

\[ (C_{S_1}, C_{S_2}, \dots, C_{S_L}) = T_i \]

This means for each position \(j\):

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

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

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

In other words, once the current \(C\) and agent \(i\) are determined, “the \(S\) needed to make this agent succeed” is also uniquely determined.

For example, if \(K=3\) and

\[ C = (2,3,1) \]

that is, \(1 \mapsto 2, 2 \mapsto 3, 3 \mapsto 1\),
then \(C^{-1}\) is

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

If \(T_i = (2,1,3)\), the \(S\) required for success is

\[ (C^{-1}(2), C^{-1}(1), C^{-1}(3)) = (1,3,2) \]

---

The key point here is that the password \(S\) is decided only once at the beginning and cannot be changed afterward.

Therefore, to make multiple agents succeed in a given sending order, the password required at each respective point must all be the same.

In other words, for a given sending order, we need to check:

• The candidate \(S\) required for agent \(i\) to succeed at that point
• Whether it is consistent with the memo \(B\)

and count how many times the same candidate \(S\) appears.

---

If we naively enumerate all possible passwords \(S\), there could be up to

\[ K^L \]

possibilities for undetermined positions, and since \(K \leq 8, L \leq 200\), this is infeasible.

On the other hand, since the number of agents is

\[ N \leq 8 \]

the number of sending orders is at most

\[ 8! = 40320 \]

So instead of enumerating all passwords, we enumerate all sending orders and compute the “password required for success” by working backwards.

Algorithm

We enumerate all sending orders via DFS.

The state consists of:

• The set of agents already sent, mask
• The current permutation \(C\)

In the initial state:

\[ C_x = x \]

At each DFS state, we choose the next unsent agent \(i\).

1. Check if agent \(i\) can succeed

When the current permutation is \(C\), the password candidate required for success is

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

However, this \(S\) must be consistent with the memo \(B\).

At positions where \(B_j \neq 0\), we need \(S_j = B_j\).
This is equivalent to

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

Therefore, for fixed positions, we can check for contradictions before constructing the entire candidate sequence.

If the same value \(x\) appears at multiple fixed positions in \(B\), then \(T_{i,j}\) must be the same value for all of them.
Otherwise, success is impossible regardless of \(C\).

In the code, for each agent, we precompute:

constraints[i]

which summarizes the conditions that

\[ C_x = v \]

should hold.

If the current \(C\) satisfies these conditions, we actually construct

\[ S = C^{-1}(T_i) \]

2. Count occurrences of the same candidate \(S\)

The current DFS path represents a partial sending order up to some point.

We use a dictionary counts to manage:

counts[S] = number of times candidate S has appeared in the sending orders so far

If agent \(i\) yields candidate \(S\) this time:

counts[S] += 1

This value represents the number of agents that succeed when password \(S\) is chosen in the current sending order.

Therefore, if counts[S] exceeds the current maximum, we update the answer.
If it ties the maximum, we adopt the lexicographically smaller \(S\).

3. Update the permutation and recurse

After sending to agent \(i\), regardless of success or failure, the permutation is updated.

The new permutation is

\[ C' = A_i \circ C \]

That is, for each \(x\):

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

We continue the DFS with this new \(C'\).

After returning from recursion, we undo the changes to counts.

---

The DFS flow in pseudocode is as follows:

dfs(mask, C):
    if all agents have been sent:
        return

    for i in unsent agents:
        if current C satisfies the fixed conditions for agent i:
            S = C^{-1}(T_i)
            counts[S] += 1
            update answer

        dfs(mask with i added, A_i ∘ C)

        restore counts[S]

---

Finally, if no success candidate ever appeared, the maximum number of successes is \(0\).

In this case, any password achieves the maximum of \(0\).
Therefore, we output the lexicographically smallest password that follows memo \(B\), which is the one with all undetermined positions set to \(1\).

Complexity

The number of partial states in the sending order is

\[ \sum_{r=0}^{N} {}_NP_r \]

This can be considered \(O(N!)\).

At each transition:

• Checking fixed conditions takes \(O(K)\)
• Generating the candidate password takes \(O(L)\)

Therefore:

• Time complexity: \(O(NL + N!(K+L))\)
• Space complexity: \(O(N(L+K) + DK)\)

Here, \(D\) is the number of distinct permutations that appear during DFS, which is at most

\[ D \leq \min(K!, \sum_{r=0}^{N} {}_NP_r) \]

Given the constraints \(N,K \leq 8\), \(L \leq 200\), this is sufficiently fast.

Implementation Notes

• The input is 1-indexed, but in the implementation we convert to 0-indexed for convenience.

• The permutation \(C\) is stored as an array where C[x] = C_x.

• The composition \(A_i \circ C\) is computed as A_i[C[x]] for each \(x\).

• The inverse permutation \(C^{-1}\) for the current \(C\) is cached since it is used frequently.

• In Python, using bytes and translate allows fast transformation of entire sequences.

• Lexicographic comparison of bytes coincides with lexicographic comparison of integer sequences, so it can be used directly for updating the lexicographically smallest answer.

• In DFS, after updating counts, it must be restored when returning from recursion. This is a fundamental aspect of backtracking.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    p = 0
    N, K, L = data[p], data[p + 1], data[p + 2]
    p += 3

    B_raw = data[p:p + L]
    p += L
    B = [x - 1 if x != 0 else -1 for x in B_raw]

    base_table = bytes(range(256))

    T = []
    Atrans = []

    for _ in range(N):
        T.append(bytes([x - 1 for x in data[p:p + L]]))
        p += L

        a = [x - 1 for x in data[p:p + K]]
        p += K

        arr = bytearray(base_table)
        for i, v in enumerate(a):
            arr[i] = v
        Atrans.append(bytes(arr))

    fixed = [(idx, b) for idx, b in enumerate(B) if b >= 0]

    constraints = []
    for i in range(N):
        req = [-1] * K
        ok = True
        ti = T[i]
        for idx, b in fixed:
            v = ti[idx]
            if req[b] == -1:
                req[b] = v
            elif req[b] != v:
                ok = False
                break

        if not ok:
            constraints.append(None)
        else:
            constraints.append(tuple((s, req[s]) for s in range(K) if req[s] != -1))

    identity = bytes(range(K))
    inv_cache = {identity: base_table}

    def get_inv_table(C):
        tab = inv_cache.get(C)
        if tab is not None:
            return tab

        inv = [0] * K
        for i, v in enumerate(C):
            inv[v] = i

        arr = bytearray(base_table)
        for i in range(K):
            arr[i] = inv[i]

        tab = bytes(arr)
        inv_cache[C] = tab
        return tab

    sys.setrecursionlimit(1000000)

    full_mask = (1 << N) - 1
    counts = {}

    best = 0
    best_s = None

    def dfs(mask, C):
        nonlocal best, best_s

        if mask == full_mask:
            return

        for i in range(N):
            bit = 1 << i
            if mask & bit:
                continue

            added = False
            cand = None
            prev = 0

            cons = constraints[i]
            if cons is not None:
                ok = True
                for s, v in cons:
                    if C[s] != v:
                        ok = False
                        break

                if ok:
                    cand = T[i].translate(get_inv_table(C))
                    prev = counts.get(cand, 0)
                    now = prev + 1
                    counts[cand] = now

                    if now > best:
                        best = now
                        best_s = cand
                    elif now == best and (best_s is None or cand < best_s):
                        best_s = cand

                    added = True

            dfs(mask | bit, C.translate(Atrans[i]))

            if added:
                if prev:
                    counts[cand] = prev
                else:
                    del counts[cand]

    dfs(0, identity)

    if best_s is None:
        ans = [b + 1 if b >= 0 else 1 for b in B]
    else:
        ans = [x + 1 for x in best_s]

    print(best)
    print(*ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.