Overview

For each candidate string, check whether the characters match only at the recovered positions. If all match, output Yes; if even one differs, output No.

Analysis

This matching system follows the rule “only check recovered positions; anything else is acceptable.” Therefore, the condition for each candidate string \(T_j\) to be judged as correct boils down to one thing:

• For all recovery information \((P_i, C_i)\), the \(P_i\)-th character of \(T_j\) must match \(C_i\).

In other words, there is no need to compare the entire string (of length \(N\)) every time. We only need to look at the \(M\) recovered positions.

A naive implementation that “checks all \(N\) characters every time” would have a time complexity of \(O(NQ)\). At maximum \(N=10^5, Q=10^3\), this results in \(10^8\) character checks, which can be heavy depending on the language and constants. By “only checking the \(M\) recovered positions,” we can reduce each query to \(O(M)\).

Concrete example: - \(N=5\) - Recovery: \((2,'a'), (5,'z')\) - Candidate baqqz: the 2nd character is a and the 5th character is z, so Yes - Candidate bbqqz: the 2nd character is b, which doesn’t match, so No (Other positions can be anything)

Algorithm

1. Store the recovery information in an array
   • Convert position \(P_i\) to 0-indexed: pos[i] = P_i - 1
   • Store the expected character as exp[i] = C_i
2. For each candidate string \(T\), do the following:
   • For \(i=1..M\), check whether T[pos[i]] == exp[i]
   • If even one mismatch is found, output No; if all match, output Yes
3. As a special case, when \(M=0\), no positions are checked, so all candidates are always Yes

Complexity

• Time complexity: \(O(MQ)\) (when \(M=0\), it is \(O(Q)\))
• Space complexity: \(O(M)\)

Implementation Notes

• Convert positions to 0-indexed (P_i - 1).

• In Python, for optimization, handling the input string as bytes makes index access faster. In the code, we use sys.stdin.buffer.readline and strip(), comparing t[pos] (an integer) with exp (an ASCII integer).

• When a mismatch is found, break immediately to avoid unnecessary comparisons.

• When \(M=0\), everything is Yes, so we just need to read the candidate strings and output the results.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline

    N, M, Q = map(int, input().split())
    pos = [0] * M
    exp = [0] * M

    for i in range(M):
        p, c = input().split()
        pos[i] = int(p) - 1
        exp[i] = c[0]  # int (ASCII)

    out = []
    if M == 0:
        for _ in range(Q):
            input()
            out.append("Yes")
    else:
        pos_l = pos
        exp_l = exp
        for _ in range(Q):
            t = input().strip()  # bytes
            ok = True
            for i in range(M):
                if t[pos_l[i]] != exp_l[i]:
                    ok = False
                    break
            out.append("Yes" if ok else "No")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.