codeforces-scrape

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

1669D.md (3542B)


      1 Source: https://codeforces.com/problemset/problem/1669/D
      2 
      3 D. Colorful Stamp
      4 
      5 time limit per test
      6 
      7 1 second
      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 A row of $n$ cells is given, all initially white. Using a stamp, you can stamp any two neighboring cells such that one becomes red and the other becomes blue. A stamp can be rotated, i.e. it can be used in both ways: as $\color{blue}{\texttt{B}}\color{red}{\texttt{R}}$ and as $\color{red}{\texttt{R}}\color{blue}{\texttt{B}}$.
     22 
     23 During use, the stamp must completely fit on the given $n$ cells (it cannot be partially outside the cells). The stamp can be applied multiple times to the same cell. Each usage of the stamp recolors both cells that are under the stamp.
     24 
     25 For example, one possible sequence of stamps to make the picture $\color{blue}{\texttt{B}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\color{blue}{\texttt{B}}\texttt{W}$ could be $\texttt{WWWWW} \to \texttt{WW}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\texttt{W} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{red}{\texttt{R}}\color{blue}{\texttt{B}}\texttt{W} \to \color{blue}{\texttt{B}}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}\texttt{W}$. Here $\texttt{W}$, $\color{red}{\texttt{R}}$, and $\color{blue}{\texttt{B}}$ represent a white, red, or blue cell, respectively, and the cells that the stamp is used on are marked with an underline.
     26 
     27 Given a final picture, is it possible to make it using the stamp zero or more times?
     28 
     29 Input
     30 
     31 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     32 
     33 The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^5$) — the length of the picture.
     34 
     35 The second line of each test case contains a string $s$ — the picture you need to make. It is guaranteed that the length of $s$ is $n$ and that $s$ only consists of the characters $\texttt{W}$, $\texttt{R}$, and $\texttt{B}$, representing a white, red, or blue cell, respectively.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     38 
     39 Output
     40 
     41 Output $t$ lines, each of which contains the answer to the corresponding test case. As an answer, output "YES" if it possible to make the picture using the stamp zero or more times, and "NO" otherwise.
     42 
     43 You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 12
     51 
     52 5
     53 
     54 BRBBW
     55 
     56 1
     57 
     58 B
     59 
     60 2
     61 
     62 WB
     63 
     64 2
     65 
     66 RW
     67 
     68 3
     69 
     70 BRB
     71 
     72 3
     73 
     74 RBB
     75 
     76 7
     77 
     78 WWWWWWW
     79 
     80 9
     81 
     82 RBWBWRRBW
     83 
     84 10
     85 
     86 BRBRBRBRRB
     87 
     88 12
     89 
     90 BBBRWWRRRWBR
     91 
     92 10
     93 
     94 BRBRBRBRBW
     95 
     96 5
     97 
     98 RBWBW
     99 ```
    100 
    101 Output
    102 
    103 ```
    104 YES
    105 NO
    106 NO
    107 NO
    108 YES
    109 YES
    110 YES
    111 NO
    112 YES
    113 NO
    114 YES
    115 NO
    116 ```
    117 
    118 Note
    119 
    120 The first test case is explained in the statement.
    121 
    122 For the second, third, and fourth test cases, it is not possible to stamp a single cell, so the answer is "NO".
    123 
    124 For the fifth test case, you can use the stamp as follows: $\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{blue}{\texttt{B}}\color{red}{\texttt{R}}}}\color{blue}{\texttt{B}}$.
    125 
    126 For the sixth test case, you can use the stamp as follows: $\texttt{WWW} \to \texttt{W}\color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}} \to \color{brown}{\underline{\color{red}{\texttt{R}}\color{blue}{\texttt{B}}}}\color{blue}{\texttt{B}}$.
    127 
    128 For the seventh test case, you don't need to use the stamp at all.