1845C.md (2717B)
1 Source: https://codeforces.com/problemset/problem/1845/C 2 3 C. Strong Password 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 Monocarp finally got the courage to register on ForceCoders. He came up with a handle but is still thinking about the password. 22 23 He wants his password to be as strong as possible, so he came up with the following criteria: 24 25 * the length of the password should be exactly $m$; 26 * the password should only consist of digits from $0$ to $9$; 27 * the password should not appear in the password database (given as a string $s$) as a subsequence (not necessarily contiguous). 28 29 Monocarp also came up with two strings of length $m$: $l$ and $r$, both consisting only of digits from $0$ to $9$. He wants the $i$-th digit of his password to be between $l_i$ and $r_i$, inclusive. 30 31 Does there exist a password that fits all criteria? 32 33 Input 34 35 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases. 36 37 The first line of each testcase contains a string $s$ ($1 \le |s| \le 3 \cdot 10^5$), consisting only of digits from $0$ to $9$ — the password database. 38 39 The second line contains a single integer $m$ ($1 \le m \le 10$) — the required length of the password. 40 41 The third line contains a string $l$ ($|l| = m$), consisting only of digits from $0$ to $9$ — the lower restriction on each digit. 42 43 The fourth line contains a string $r$ ($|r| = m$), consisting only of digits from $0$ to $9$ — the upper restriction on each digit. $l_i \le r_i$ for all $i$ from $1$ to $m$. 44 45 The sum of lengths of $s$ over all testcases doesn't exceed $3 \cdot 10^5$. 46 47 Output 48 49 For each testcase, print "YES" if there exists a password that fits all criteria. Print "NO" otherwise. 50 51 Example 52 53 Input 54 55 ``` 56 5 57 58 88005553535123456 59 60 2 61 62 50 63 64 56 65 66 123412341234 67 68 3 69 70 111 71 72 444 73 74 1234 75 76 4 77 78 4321 79 80 4321 81 82 459 83 84 2 85 86 49 87 88 59 89 90 00010 91 92 2 93 94 10 95 96 11 97 ``` 98 99 Output 100 101 ``` 102 YES 103 NO 104 YES 105 NO 106 YES 107 ``` 108 109 Note 110 111 In the first testcase, Monocarp can choose password "50". It doesn't appear in $s$ as a subsequence. 112 113 In the second testcase, all combinations of three digits, each of them being from $1$ to $4$, fit the criteria on $l$ and $r$. However, all of them appear in $s$ as subsequences. For example, "314" appears at positions $[3, 5, 12]$ and "222" appears at positions $[2, 6, 10]$. 114 115 In the third testcase, Monocarp can choose password "4321". Actually, that is the only password that fits the criteria on $l$ and $r$. Luckily, it doesn't appear in $s$ as a subsequence. 116 117 In the fourth testcase, only "49" and "59" fit the criteria on $l$ and $r$. Both of them appear in $s$ as subsequences. 118 119 In the fifth testcase, Monocarp can choose password "11".