2000C.md (2673B)
1 Source: https://codeforces.com/problemset/problem/2000/C 2 3 C. Numeric String Template 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Kristina has an array $a$, called a template, consisting of $n$ integers. She also has $m$ strings, each consisting only of lowercase Latin letters. The strings are numbered from $1$ to $m$. She wants to check which strings match the template. 22 23 A string $s$ is considered to match the template if all of the following conditions are simultaneously satisfied: 24 25 * The length of the string $s$ is equal to the number of elements in the array $a$. 26 * The same numbers from $a$ correspond to the same symbols from $s$. So, if $a_i = a_j$, then $s_i = s_j$ for ($1 \le i, j \le n$). 27 * The same symbols from $s$ correspond to the same numbers from $a$. So, if $s_i = s_j$, then $a_i = a_j$ for ($1 \le i, j \le n$). 28 29 In other words, there must be a one-to-one correspondence between the characters of the string and the elements of the array. 30 31 For example, if $a$ = [$3, 5, 2, 1, 3$], then the string "abfda" matches the template, while the string "afbfa" does not, since the character "f" corresponds to both numbers $1$ and $5$. 32 33 Input 34 35 The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 36 37 The following descriptions are for the test cases. 38 39 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in the array $a$. 40 41 The second line of each test case contains exactly $n$ integers $a_i$ ($-10^9 \le a_i \le 10^9$) — the elements of the array $a$. 42 43 The third line of each test case contains a single integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of strings to check for template matching. 44 45 Following are $m$ strings, each containing a non-empty string $s_j$ ($1 \le |s_j| \le 2 \cdot 10^5$), consisting of lowercase Latin letters. 46 47 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$, and that the sum of the lengths of all strings does not exceed $2 \cdot 10^5$. 48 49 Output 50 51 For each test case, output $m$ lines. On the $i$-th line ($1 \le i \le m$) output: 52 53 * "YES", if the string with index $i$ matches the template; 54 * "NO" otherwise. 55 56 You may output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer). 57 58 Example 59 60 Input 61 62 ``` 63 3 64 65 5 66 67 3 5 2 1 3 68 69 2 70 71 abfda 72 73 afbfa 74 75 2 76 77 1 2 78 79 3 80 81 ab 82 83 abc 84 85 aa 86 87 4 88 89 5 -3 5 -3 90 91 4 92 93 aaaa 94 95 bcbc 96 97 aba 98 99 cbcb 100 ``` 101 102 Output 103 104 ``` 105 YES 106 NO 107 YES 108 NO 109 NO 110 NO 111 YES 112 NO 113 YES 114 ``` 115 116 Note 117 118 The first test case is explained in the problem statement.