Overview

This is a problem where, based on partially recovered information about a password, you need to determine whether each candidate string is the correct password.

Analysis

In this problem, the positions and characters of some parts of the password are known, and we need to verify whether the characters at those positions match the candidate string.

As a straightforward approach, instead of checking every position of the candidate string each time, we note that we only need to check the recovered positions. If we checked every character each time, unnecessary computations would increase, which becomes wasteful especially when \(N\) is large.

Furthermore, to efficiently manage the recovery data \((P_i, C_i)\), we can use a dictionary (associative array) with positions as keys and characters as values, allowing fast lookup of the correct character at each position.

In this way, by extracting only the necessary information and managing it with an efficient data structure, we can perform the determination quickly.

Algorithm

1. Read the recovery data \((P_i, C_i)\) and store it in a dictionary restore with positions as keys and characters as values.
2. For each candidate string \(T_j\), compare the characters at the positions registered in restore with the characters at the corresponding positions in \(T_j\).
3. If there is even one mismatch, output No; if all match, output Yes.

For example, suppose we have the following input:

N=5, M=2
P=[2, 5], C=['a', 'b']
=> restore = {2: 'a', 5: 'b'}

The candidate string "xaxxb" has 'a' at position 2 and 'b' at position 5, so it satisfies the conditions and the answer is Yes.

Complexity

• Time complexity: \(O(M + Q \cdot M)\)
  (\(O(M)\) for reading the recovery data, and comparing up to \(M\) characters per query)
• Space complexity: \(O(M + N \cdot Q)\)
  (\(O(M)\) for storing the recovery data, \(O(N \cdot Q)\) for holding all input strings)

Implementation Notes

• By managing the recovery data with a dictionary instead of a list, we can quickly retrieve the character from a given position.

• The index of each query string is 0-based, but the positions specified in the problem are 1-based, so be careful to use pos - 1 when accessing characters.

• To speed up input, it is recommended to use sys.stdin.read to read everything at once.

  Source Code

# 入力の読み込み
import sys
input = sys.stdin.read

data = input().split()
idx = 0

N = int(data[idx])
idx += 1
M = int(data[idx])
idx += 1
Q = int(data[idx])
idx += 1

# 復旧データを辞書で保持
restore = {}
for _ in range(M):
    p = int(data[idx])
    idx += 1
    c = data[idx]
    idx += 1
    restore[p] = c

# 各候補文字列に対して判定
results = []
for _ in range(Q):
    T = data[idx]
    idx += 1
    valid = True
    for pos, char in restore.items():
        if T[pos - 1] != char:
            valid = False
            break
    results.append("Yes" if valid else "No")

# 結果の出力
print("\n".join(results))

This editorial was generated by qwen3-coder-480b.