codeforces-scrape

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

1924A.md (2309B)


      1 Source: https://codeforces.com/problemset/problem/1924/A
      2 
      3 A. Did We Get Everything Covered?
      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 You are given two integers $n$ and $k$ along with a string $s$.
     22 
     23 Your task is to check whether all possible strings of length $n$ that can be formed using the first $k$ lowercase English alphabets occur as a subsequence of $s$. If the answer is NO, you also need to print a string of length $n$ that can be formed using the first $k$ lowercase English alphabets which does not occur as a subsequence of $s$.
     24 
     25 If there are multiple answers, you may print any of them.
     26 
     27 Note: A string $a$ is called a subsequence of another string $b$ if $a$ can be obtained by deleting some (possibly zero) characters from $b$ without changing the order of the remaining characters.
     28 
     29 Input
     30 
     31 The first line of input contains a single integer $t \, (1 \le t \le 10^5)$, the number of test cases.
     32 
     33 The first line of each test case contains $3$ integers $n \, (1 \le n \le 26), \: k \, (1 \le k \le 26), \: m \, (1 \le m \le 1000)$, where $n$ and $k$ are the same as described in the input and $m$ is the length of the string $s$.
     34 
     35 The second line of each test case contains a single string $s$ of length $m$, comprising only of the first $k$ lowercase English alphabets.
     36 
     37 It is guaranteed that the sum of $m$ and the sum of $n$ over all test cases does not exceed $10^6$.
     38 
     39 Output
     40 
     41 For each test case, print YES if all possible strings of length $n$ that can be formed using the first $k$ lowercase English alphabets occur as a subsequence of $s$, else print NO.
     42 
     43 If your answer is NO, print a string of length $n$ that can be formed using the first $k$ lowercase English alphabets which does not occur as a subsequence of $s$ in the next line.
     44 
     45 You may print each letter of YES or NO in any case (for example, YES, yES, YeS will all be recognized as a positive answer).
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 3
     53 
     54 2 2 4
     55 
     56 abba
     57 
     58 2 2 3
     59 
     60 abb
     61 
     62 3 3 10
     63 
     64 aabbccabab
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 YES
     71 NO
     72 aa
     73 NO
     74 ccc
     75 ```
     76 
     77 Note
     78 
     79 For the first test case, all possible strings (aa, ab, ba, bb) of length $2$ that can be formed using the first $2$ English alphabets occur as a subsequence of abba.
     80 
     81 For the second test case, the string aa is not a subsequence of abb.