codeforces-scrape

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

2147C.md (3682B)


      1 Source: https://codeforces.com/problemset/problem/2147/C
      2 
      3 C. Rabbits
      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 have $n$ flower pots arranged in a line numbered from $1$ to $n$ left to right. Some of the pots contain flowers, while others are empty. You are given a binary string $s$ describing which pots contain flowers ($s_i = 1$) and which are empty ($s_i = 0$). You also have some rabbits, and you want to take a nice picture of rabbits and flowers. You want to put rabbits in every empty pot ($s_i = 0$), and for each rabbit, you can put it looking either to the left or to the right. Unfortunately, the rabbits are quite naughty, and they will try to jump, which will ruin the picture.
     22 
     23 Each rabbit will prepare to jump into the next pot in the direction they are looking, but they won't jump if there is a rabbit in that pot already or if there is another rabbit that prepares to jump into the same pot from the opposite side. Rabbits won't jump out of the borders (a rabbit at pot $1$ looking to the left won't jump, same for a rabbit looking to the right at pot $n$).
     24 
     25 Your goal is to choose the directions of the rabbits so that they never jump, allowing you to take your time to take the picture. You need to determine if there is a valid arrangement of rabbits such that no rabbit ever jumps.
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     30 
     31 The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$).
     32 
     33 The second line contains a binary string $s$ of size $n$, denoting the occupied and empty pots.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case, print "YES" if there exists a configuration of rabbits that satisfies the condition, and "NO" otherwise.
     40 
     41 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 12
     49 
     50 4
     51 
     52 0100
     53 
     54 3
     55 
     56 000
     57 
     58 8
     59 
     60 11011011
     61 
     62 5
     63 
     64 00100
     65 
     66 1
     67 
     68 1
     69 
     70 5
     71 
     72 01011
     73 
     74 2
     75 
     76 01
     77 
     78 7
     79 
     80 0101011
     81 
     82 7
     83 
     84 1101010
     85 
     86 5
     87 
     88 11001
     89 
     90 4
     91 
     92 1101
     93 
     94 9
     95 
     96 001101100
     97 ```
     98 
     99 Output
    100 
    101 ```
    102 YES
    103 
    104 YES
    105 
    106 NO
    107 
    108 YES
    109 
    110 YES
    111 
    112 YES
    113 
    114 YES
    115 
    116 YES
    117 
    118 YES
    119 
    120 YES
    121 
    122 NO
    123 
    124 NO
    125 ```
    126 
    127 Note
    128 
    129 [Visualizer link](https://codeforces.com/assets/contests/2147/C_2iM9A1dE03B4IrDfFG54.html)
    130 
    131 In the first test case, one of the valid configurations is to put a rabbit looking to the right at position $1$, a rabbit looking to the left at position $3$, and a rabbit looking to the left at position $4$. No rabbit will move since:
    132 
    133 * The rabbit at pot $1$ won't move to pot $2$ since the rabbit at pot $3$ is looking to the left.
    134 * The rabbit at pot $3$ won't move to pot $2$ since the rabbit at pot $1$ is looking to the right.
    135 * The rabbit at pot $4$ won't move to pot $3$ since there is a rabbit in there.
    136 
    137  ![](https://espresso.codeforces.com/774410cf1eab1d16906b6c1e48e52d02a889b494.png) 
    138 
    139 In the second test case, one of the valid configurations is to put a rabbit looking to the left at position $1$, a rabbit looking to the right at position $2$, and a rabbit looking to the left at position $3$. No rabbit will move since:
    140 
    141 * The rabbit at pot $1$ won't move since it is looking at the left border.
    142 * The rabbit at pot $2$ won't move to pot $3$ since there is a rabbit in there.
    143 * The rabbit at pot $3$ won't move to pot $2$ since there is a rabbit in there.
    144 
    145  ![](https://espresso.codeforces.com/95e25f6cef45ea02d1213238095422d1fbdd6b28.png) 
    146 
    147 It can be proven that there is no valid arrangement of rabbits in the third test case.