2158B.md (1943B)
1 Source: https://codeforces.com/problemset/problem/2158/B 2 3 B. Split 4 5 time limit per test 6 7 1 second 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 a sequence $a$ containing $2n$ integers. Let $f(b)$ denote the number of distinct elements with an odd number of occurrences in sequence $b$. You need to split the given array into two disjoint subsequences $p$ and $q$, each of size $n$, such that $f(p) + f(q)$ is maximized. Output the maximum value. 22 23 A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) element from arbitrary positions. 24 25 Input 26 27 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. 28 29 The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$). 30 31 The second line contains $2n$ integers $a_1,a_2,\ldots,a_{2n}$ ($1 \le a_i \le 2n$) — the elements of sequence $a$. 32 33 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 34 35 Output 36 37 For each test case, print one line. 38 39 You have to print the maximum value of $f(p) + f(q)$ that can be achieved. 40 41 Example 42 43 Input 44 45 ``` 46 7 47 48 2 49 50 1 2 3 4 51 52 3 53 54 5 5 5 5 5 5 55 56 4 57 58 3 3 7 6 3 7 8 7 59 60 2 61 62 2 2 2 2 63 64 6 65 66 1 2 3 4 5 4 1 4 1 5 4 6 67 68 4 69 70 1 2 1 2 1 2 1 2 71 72 5 73 74 9 9 9 7 7 7 9 7 7 7 75 ``` 76 77 Output 78 79 ``` 80 4 81 82 2 83 84 4 85 86 0 87 88 8 89 90 4 91 92 2 93 ``` 94 95 Note 96 97 For the first test case: 98 99 * We can divide the array such that $p = [1, 3]$ and $q = [2, 4]$. 100 * This way, $f(p) = 2$ and $f(q) = 2$ since both have two distinct elements with odd frequency. 101 102 For the second test case: 103 104 * We can divide the array such that $p = [5, 5, 5]$ and $q = [5, 5, 5]$. 105 * This way, $f(p) = 1$ and $f(q) = 1$. 106 107 For the fifth test case: 108 109 * We can divide the array such that $p = [1, 2, 3, 4, 5, 6]$ and $q = [4, 1, 4, 1, 5, 4]$. 110 * This way, $f(p) = 6$ and $f(q) = 2$.