codeforces-scrape

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

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.