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  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  146 147 It can be proven that there is no valid arrangement of rabbits in the third test case.