codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.