codeforces-scrape

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

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".