Overview

This problem asks us to determine whether each of \(Q\) candidate strings satisfies the condition that, for a password of length \(N\) where \(M\) characters at specific positions are known, the characters at those known positions match.

Analysis

The following two points are important for password verification:

1. Positions that need checking: We only need to check whether the character at position \(P_i\) in candidate string \(T_j\) matches \(C_i\) for the \(M\) recovered positions. For positions that have not been recovered, any character is acceptable and does not affect the result.
2. Complexity estimation:
   • The string length \(N\) is at most \(10^5\), and the number of candidates \(Q\) is \(10^3\).
   • Since we check at most \(M\) positions for each candidate string, the overall complexity is \(O(Q \times M)\) in the worst case.
   • Since \(M \leq N\), up to \(10^3 \times 10^5 = 10^8\) comparisons may occur. In the case of Python, this complexity is somewhat tight for the time limit, so an efficient implementation (fast I/O and elimination of unnecessary operations) is required.

Algorithm

The determination is performed using the following steps:

1. Store recovery data: Store the \(M\) recovery data entries \((P_i, C_i)\) in a list. At this point, it is convenient to subtract \(1\) from \(P_i\) to make it “0-indexed” to match the array indexing of the programming language.
2. Process queries: For each candidate string \(T_j\), repeat the following:
   • Initialize a match flag (is_match) to True.
   • Iterate through the \(M\) stored recovery data entries, and if the \(P_i\)-th character of \(T_j\) differs from \(C_i\), set the flag to False and break out of the loop (early termination).
   • If the flag remains True, output Yes; otherwise, output No.

Complexity

• Time complexity: \(O(QN)\)
  • For each query, at most \(M\) comparisons are performed. Since \(M \leq N\), the overall complexity is \(O(QM)\), or \(O(QN)\) when including string reading.
  • Under the given constraints (\(QN \approx 10^8\)), early termination (break) and fast I/O contribute significantly to the execution time.
• Space complexity: \(O(N + M)\)
  • \(O(M)\) memory is used for storing the recovery data, and \(O(N)\) for holding the input strings.

Implementation Notes

• Fast I/O: By using sys.stdin.readline() instead of input(), the time spent on reading a large amount of string input is reduced.

• Avoiding unnecessary string operations: Methods like t.strip() generate a new string of length \(N\) each time they are called, so using them inside a loop results in a heavy \(O(QN)\) operation. Since accessing by index \(P_i\) (where \(P_i < N\)) is unaffected even if a newline character is included, comparisons are performed directly without stripping.

• Early termination: Since even a single mismatching character is enough to determine No, we use break to skip the remaining checks.

  Source Code

import sys

def solve():
    # Use sys.stdin.readline for fast input reading
    input_readline = sys.stdin.readline
    
    # Read the first line containing N (length), M (known characters), and Q (queries)
    line1 = input_readline().split()
    if not line1:
        return
    n, m, q = map(int, line1)
    
    # Store the known characters as a list of tuples (0-indexed position, character)
    # Using a list of tuples is efficient for iteration in the main loop
    known = []
    for _ in range(m):
        line = input_readline().split()
        if not line:
            break
        # The position P_i is 1-indexed, so we subtract 1 to make it 0-indexed
        p = int(line[0]) - 1
        c = line[1]
        known.append((p, c))
        
    # Prepare a list to collect results for each query
    output = []
    # Pre-binding the append method of the list can provide a slight speed boost
    out_append = output.append
    
    # Process each candidate string T_j
    for _ in range(q):
        # Read the next candidate string
        t = input_readline()
        if not t:
            break
        
        # We perform the matching check for each known position.
        # Note: We do not call t.strip() here because it would create a new string 
        # of length N in every iteration, which is O(N). Since we only care 
        # about the characters at specific indices p < N, and sys.stdin.readline() 
        # includes the newline character at index N or later, t[p] is safe.
        is_match = True
        for p, c in known:
            if t[p] != c:
                is_match = False
                break
        
        # Append "Yes" if all restored positions matched, otherwise "No"
        if is_match:
            out_append("Yes")
        else:
            out_append("No")
    
    # Print all accumulated results at once, separated by newlines
    if output:
        sys.stdout.write('\n'.join(output) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.