codeforces-scrape

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

1766B.md (1727B)


      1 Source: https://codeforces.com/problemset/problem/1766/B
      2 
      3 B. Notepad#
      4 
      5 time limit per test
      6 
      7 3 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 want to type the string $s$, consisting of $n$ lowercase Latin letters, using your favorite text editor Notepad#.
     22 
     23 Notepad# supports two kinds of operations:
     24 
     25 * append any letter to the end of the string;
     26 * copy a continuous substring of an already typed string and paste this substring to the end of the string.
     27 
     28 Can you type string $s$ in strictly less than $n$ operations?
     29 
     30 Input
     31 
     32 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.
     33 
     34 The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.
     35 
     36 The second line contains a string $s$, consisting of $n$ lowercase Latin letters.
     37 
     38 The sum of $n$ doesn't exceed $2 \cdot 10^5$ over all testcases.
     39 
     40 Output
     41 
     42 For each testcase, print "YES" if you can type string $s$ in strictly less than $n$ operations. Otherwise, print "NO".
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 6
     50 
     51 10
     52 
     53 codeforces
     54 
     55 8
     56 
     57 labacaba
     58 
     59 5
     60 
     61 uohhh
     62 
     63 16
     64 
     65 isthissuffixtree
     66 
     67 1
     68 
     69 x
     70 
     71 4
     72 
     73 momo
     74 ```
     75 
     76 Output
     77 
     78 ```
     79 NO
     80 YES
     81 NO
     82 YES
     83 NO
     84 YES
     85 ```
     86 
     87 Note
     88 
     89 In the first testcase, you can start with typing "codef" ($5$ operations), then copy "o" ($1$ operation) from an already typed part, then finish with typing "rces" ($4$ operations). That will be $10$ operations, which is not strictly less than $n$. There exist other ways to type "codeforces". However, no matter what you do, you can't do less than $n$ operations.
     90 
     91 In the second testcase, you can type "labac" ($5$ operations), then copy "aba" ($1$ operation), finishing the string in $6$ operations.