1851C.md (3055B)
1 Source: https://codeforces.com/problemset/problem/1851/C 2 3 C. Tiles Comeback 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 Vlad remembered that he had a series of $n$ tiles and a number $k$. The tiles were numbered from left to right, and the $i$-th tile had colour $c_i$. 22 23 If you stand on the first tile and start jumping any number of tiles right, you can get a path of length $p$. The length of the path is the number of tiles you stood on. 24 25 Vlad wants to see if it is possible to get a path of length $p$ such that: 26 27 * it ends at tile with index $n$; 28 * $p$ is divisible by $k$ 29 * the path is divided into blocks of length exactly $k$ each; 30 * tiles in each block have the same colour, the colors in adjacent blocks are not necessarily different. 31 32 For example, let $n = 14$, $k = 3$. 33 34 The colours of the tiles are contained in the array $c$ = [$\color{red}{1}, \color{violet}{2}, \color{red}{1}, \color{red}{1}, \color{gray}{7}, \color{orange}{5}, \color{green}{3}, \color{green}{3}, \color{red}{1}, \color{green}{3}, \color{blue}{4}, \color{blue}{4}, \color{violet}{2}, \color{blue}{4}$]. Then we can construct a path of length $6$ consisting of $2$ blocks: 35 36 $\color{red}{c_1} \rightarrow \color{red}{c_3} \rightarrow \color{red}{c_4} \rightarrow \color{blue}{c_{11}} \rightarrow \color{blue}{c_{12}} \rightarrow \color{blue}{c_{14}}$ 37 38 All tiles from the $1$-st block will have colour $\color{red}{\textbf{1}}$, from the $2$-nd block will have colour $\color{blue}{\textbf{4}}$. 39 40 It is also possible to construct a path of length $9$ in this example, in which all tiles from the $1$-st block will have colour $\color{red}{\textbf{1}}$, from the $2$-nd block will have colour $\color{green}{\textbf{3}}$, and from the $3$-rd block will have colour $\color{blue}{\textbf{4}}$. 41 42 Input 43 44 The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 45 46 The description of the test cases follows. 47 48 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$)—the number of tiles in the series and the length of the block. 49 50 The second line of each test case contains $n$ integers $c_1, c_2, c_3, \dots, c_n$ ($1 \le c_i \le n$) — the colours of the tiles. 51 52 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 53 54 Output 55 56 For each test case, output on a separate line: 57 58 * YES if you can get a path that satisfies these conditions; 59 * NO otherwise. 60 61 You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive response). 62 63 Example 64 65 Input 66 67 ``` 68 10 69 70 4 2 71 72 1 1 1 1 73 74 14 3 75 76 1 2 1 1 7 5 3 3 1 3 4 4 2 4 77 78 3 3 79 80 3 1 3 81 82 10 4 83 84 1 2 1 2 1 2 1 2 1 2 85 86 6 2 87 88 1 3 4 1 6 6 89 90 2 2 91 92 1 1 93 94 4 2 95 96 2 1 1 1 97 98 2 1 99 100 1 2 101 102 3 2 103 104 2 2 2 105 106 4 1 107 108 1 1 2 2 109 ``` 110 111 Output 112 113 ``` 114 YES 115 YES 116 NO 117 NO 118 YES 119 YES 120 NO 121 YES 122 YES 123 YES 124 ``` 125 126 Note 127 128 In the first test case, you can jump from the first tile to the last tile; 129 130 The second test case is explained in the problem statement.