codeforces-scrape

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

1766C.md (3045B)


      1 Source: https://codeforces.com/problemset/problem/1766/C
      2 
      3 C. Hamiltonian Wall
      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 Sir Monocarp Hamilton is planning to paint his wall. The wall can be represented as a grid, consisting of $2$ rows and $m$ columns. Initially, the wall is completely white.
     22 
     23 Monocarp wants to paint a black picture on the wall. In particular, he wants cell $(i, j)$ (the $j$-th cell in the $i$-th row) to be colored black, if $c_{i, j} =$ 'B', and to be left white, if $c_{i, j} =$ 'W'. Additionally, he wants each column to have at least one black cell, so, for each $j$, the following constraint is satisfied: $c_{1, j}$, $c_{2, j}$ or both of them will be equal to 'B'.
     24 
     25 In order for the picture to turn out smooth, Monocarp wants to place down a paint brush in some cell $(x_1, y_1)$ and move it along the path $(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$ so that:
     26 
     27 * for each $i$, $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ share a common side;
     28 * all black cells appear in the path exactly once;
     29 * white cells don't appear in the path.
     30 
     31 Determine if Monocarp can paint the wall.
     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 single integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of columns in the wall.
     38 
     39 The $i$-th of the next two lines contains a string $c_i$, consisting of $m$ characters, where each character is either 'B' or 'W'. $c_{i, j}$ is 'B', if the cell $(i, j)$ should be colored black, and 'W', if the cell $(i, j)$ should be left white.
     40 
     41 Additionally, for each $j$, the following constraint is satisfied: $c_{1, j}$, $c_{2, j}$ or both of them are equal to 'B'.
     42 
     43 The sum of $m$ over all testcases doesn't exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each testcase, print "YES" if Monocarp can paint a wall. Otherwise, print "NO".
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 6
     55 
     56 3
     57 
     58 WBB
     59 
     60 BBW
     61 
     62 1
     63 
     64 B
     65 
     66 B
     67 
     68 5
     69 
     70 BWBWB
     71 
     72 BBBBB
     73 
     74 2
     75 
     76 BW
     77 
     78 WB
     79 
     80 5
     81 
     82 BBBBW
     83 
     84 BWBBB
     85 
     86 6
     87 
     88 BWBBWB
     89 
     90 BBBBBB
     91 ```
     92 
     93 Output
     94 
     95 ```
     96 YES
     97 YES
     98 NO
     99 NO
    100 NO
    101 YES
    102 ```
    103 
    104 Note
    105 
    106 In the first testcase, Monocarp can follow a path $(2, 1)$, $(2, 2)$, $(1, 2)$, $(1, 3)$ with his brush. All black cells appear in the path exactly once, no white cells appear in the path.
    107 
    108 In the second testcase, Monocarp can follow a path $(1, 1)$, $(2, 1)$.
    109 
    110 In the third testcase:
    111 
    112 * the path $(1, 1)$, $(2, 1)$, $(2, 2)$, $(2, 3)$, $(1, 3)$, $(2, 4)$, $(2, 5)$, $(1, 5)$ doesn't suffice because a pair of cells $(1, 3)$ and $(2, 4)$ doesn't share a common side;
    113 * the path $(1, 1)$, $(2, 1)$, $(2, 2)$, $(2, 3)$, $(1, 3)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(1, 5)$ doesn't suffice because cell $(2, 3)$ is visited twice;
    114 * the path $(1, 1)$, $(2, 1)$, $(2, 2)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(1, 5)$ doesn't suffice because a black cell $(1, 3)$ doesn't appear in the path;
    115 * the path $(1, 1)$, $(2, 1)$, $(2, 2)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(1, 5)$, $(1, 4)$, $(1, 3)$ doesn't suffice because a white cell $(1, 4)$ appears in the path.