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.