2242B.md (3032B)
1 Source: https://codeforces.com/problemset/problem/2242/B 2 3 B. Predominant Frequency Division 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array $a$ consisting of the numbers $1$, $2$, and $3$. Check whether it is possible to split it into three contiguous non-empty parts such that, for each part $i$ from $1$ to $3$, the following condition holds: 22 23 * the number of elements greater than $i$ is at most half of the part. 24 25 In other words, you need to divide the array $a$ into three pairwise disjoint contiguous non-empty parts so that in the left part the number of ones is at least the total number of twos and threes, in the middle part the total number of ones and twos is at least the number of threes, and the right part can be anything, but it must be non-empty. 26 27 For example, the array $[2, 1, 1, 3, 3, 1, 2, 3]$ can be split into three parts: $[2, 1, 1, 3]$, $[3, 1, 2]$, and $[3]$. And the array $[2, 1, 3, 3, 3, 2, 3]$ cannot be split in such a way. 28 29 Input 30 31 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. 32 33 The first line of each test case contains an integer $n$ ($3 \le n \le 2 \cdot 10^{5}$) — the length of the array. 34 35 The second line of each test case contains $n$ integers $a_{i}$ ($1 \le a_{i} \le 3$). 36 37 Additional constraints on the input data: 38 39 * the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$. 40 41 Output 42 43 For each test case, print YES if there exists a way to split the array as required, and NO otherwise. 44 45 You may print the answer in any case. For example, YeS, YES, NO, nO will also be accepted. 46 47 Example 48 49 Input 50 51 ``` 52 10 53 54 8 55 56 2 1 1 3 3 1 2 3 57 58 7 59 60 2 1 3 3 3 2 3 61 62 4 63 64 1 3 3 2 65 66 6 67 68 2 2 2 1 1 1 69 70 8 71 72 3 2 1 2 1 1 2 3 73 74 3 75 76 2 1 2 77 78 3 79 80 1 2 3 81 82 5 83 84 1 3 3 1 1 85 86 5 87 88 1 1 3 3 1 89 90 3 91 92 1 3 1 93 ``` 94 95 Output 96 97 ``` 98 YES 99 100 NO 101 102 NO 103 104 NO 105 106 YES 107 108 NO 109 110 YES 111 112 YES 113 114 YES 115 116 NO 117 ``` 118 119 Note 120 121 The first two test cases are explained in the statement. 122 123 In the third test case, the left part may be $[1]$, but then any choice of the middle part ($[3]$, $[3, 3]$, $[3, 3, 2]$) does not work. The left part may also be $[1, 3]$; then the middle part must be $[3, 2]$, and in this case the right part is empty. Therefore, the answer for the third example is NO. 124 125 In the fourth test case, the only valid left part is the entire array, because on any non-empty shorter prefix the number of ones is less than the number of twos, so the middle and right parts cannot both be non-empty. 126 127 In the fifth test case, the split $[3, 2, 1, 2, 1, 1], [2], [3]$ works. 128 129 In the sixth test case, the only possible split is $[2], [1], [2]$, but the left part does not work. 130 131 In the seventh test case, the split $[1], [2], [3]$ works. 132 133 In the eighth test case, the split $[1, 3], [3, 1], [1]$ works. 134 135 In the ninth test case, the split $[1], [1], [3, 3, 1]$ works. 136 137 In the tenth test case, the only possible split is $[1], [3], [1]$, but the middle part does not work.