codeforces-scrape

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

2259D.md (2815B)


      1 Source: https://codeforces.com/problemset/problem/2259/D
      2 
      3 D. MEX Multiset
      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 are given an array $a_1, a_2, \ldots, a_n$. There exist $3$ initially empty multisets $A, B, C$, and for each index $i$ ($1 \leq i \leq n$), you may put $a_i$ into exactly one of $A$, $B$, or $C$.
     22 
     23 Determine whether it is possible to put the elements into the multisets such that $\operatorname{MEX}(A) + \operatorname{MEX}(B) + \operatorname{MEX}(C) \geq 2 \cdot \max(\operatorname{MEX}(A), \operatorname{MEX}(B), \operatorname{MEX}(C))$$^{\text{∗}}$. If so, output a construction that achieves this.
     24 
     25 $^{\text{∗}}$$\operatorname{MEX}(D)$ is defined as the smallest non-negative integer that is not present in the set $D$. For example, $\operatorname{MEX}([1, 2, 0, 5]) = 3$, and $\operatorname{MEX}([1, 2, 4, 9]) = 0$. The $\operatorname{MEX}$ of an empty set is $0$.
     26 
     27 Input
     28 
     29 The first line of each input contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     30 
     31 The first line of each test case contains $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of $a$.
     32 
     33 The second line of each test case contains $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) — the array $a$.
     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 If a valid distribution of elements into the multisets exists, output $\texttt{YES}$. Otherwise, output $\texttt{NO}$.
     40 
     41 If the answer is $\texttt{YES}$, output a string $s$ of length $n$ on a new line, such that $s_i = \texttt{A}$ if the $i$-th element was put into the multiset $A$, $s_i = \texttt{B}$ if the $i$-th element was put into the multiset $B$, and $s_i = \texttt{C}$ if the $i$-th element was put into the multiset $C$.
     42 
     43 You can output the answer in any case (upper or lower). For example, the strings $\texttt{YES}$, $\texttt{yes}$, $\texttt{yEs}$, and $\texttt{Yes}$ will be recognized as positive responses, and the strings $\texttt{NO}$, $\texttt{no}$, $\texttt{No}$ will be recognized as negative responses. Additionally, the strings $\texttt{AABCAAA}$, $\texttt{aabcaaa}$, and $\texttt{aaBcaaa}$ will be recognized as the same answer.
     44 
     45 If there are multiple possible outputs, output any.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 5
     53 
     54 6
     55 
     56 1 0 0 1 2 1
     57 
     58 4
     59 
     60 0 0 0 0
     61 
     62 3
     63 
     64 0 2 2
     65 
     66 4
     67 
     68 6 7 6 7
     69 
     70 5
     71 
     72 0 0 0 1 2
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 YES
     79 ABABCA
     80 YES
     81 ABAC
     82 NO
     83 YES
     84 AAAB
     85 YES
     86 ABCAB
     87 ```
     88 
     89 Note
     90 
     91 In the first test case, we can have $A = \{0, 1, 1\}$, $B = \{0, 1\}$, $C = \{2\}$, meaning $\operatorname{MEX}(A) + \operatorname{MEX}(B) + \operatorname{MEX}(C) = 4$, and $2 \cdot \max(\operatorname{MEX}(A), \operatorname{MEX}(B), \operatorname{MEX}(C)) = 2 \cdot \max(2, 2, 0) = 4$.
     92 
     93 In the third test case, it can be shown that there are no valid distributions.