1882.md (10052B)
1 Source: https://codeforces.com/blog/entry/120792 2 3 [1882A - Increasing Sequence](/contest/1882/problem/A "Codeforces Round 899 (Div. 2)") 4 5 **Tutorial** 6 7 Greedy solution. Continue constructing $b$ as small as possible. 8 9 If $a_{1} = 1$, $b_{1} = 2$. Else, $b_{1} = 1$. 10 11 For $i \ge 2$, if $a_{i} = b_{i-1} + 1$, $b_{i} = b_{i-1} + 2$. Else, $b_{i} = b_{i-1} + 1$. 12 13 $b_{n}$ calculated by this process is the answer. 14 15 Time complexity is $\mathcal{O}(n)$ per test case. 16 17 [1882B - Sets and Union](/contest/1882/problem/B "Codeforces Round 899 (Div. 2)") 18 19 **Something to say** 20 21 Sorry for everyone who got FSTs :( We tried our best to make pretest strong especially for this problem, but it wasn't enough. 22 23 **Hint 1** 24 25 Denote $T = S_{1} \cup S_{2} \cup \cdots \cup S_{n}$, then $S \subset T$. Since $S \neq T$, $i \in T$ and $i \notin S$ for some $i$. 26 27 **Hint 2** 28 29 Given an integer $i$, can you calculate the maximum size of $S$, such that $i \notin S$? 30 31 **Tutorial** 32 33 $i \in T$ and $i \notin S$ for some $i$. Here $1 \le i \le 50$. 34 35 For fixed $i$, select of all the sets among $S_{1}, S_{2}, \cdots, S_{n}$ which don't contain $i$. Size of their union will be the maximum size of $S$ such that $i \notin S$. 36 37 If we do this for all $i$ in $T$, maximum of them is the answer. 38 39 Time complexity is $\mathcal{O} \left( N \cdot \max \left( s_{i, j} \right) ^{2}\right)$. 40 41 [1882C - Card Game](/contest/1882/problem/C "Codeforces Round 899 (Div. 2)") 42 43 **Hint 1** 44 45 Fix the topmost card you'll pick in the initial deck. 46 47 **Tutorial** 48 49 Let's denote $i$-th card in the initial deck as card $i$. 50 51 Let the topmost card you'll pick in the initial deck as card $i$. 52 53 For all cards under card $i$ in initial deck, you can choose all and only cards with the positive value at odd index. 54 55 Proof: Here is the strategy. Before you pick card $i$, if positive card(under card $i$ in initial deck) in odd index exists, choose it. Repeat this until all positive cards(under card $i$ in initial deck) are in even index. Then if you choose card $i$, all index of positive cards(under card $i$ in initial deck) will be decreased by $1$, and will become odd. Now, choose them from the bottom to top, so that the choosing won't change the other positive cards' index. 56 57 Denote $prf_{j}$ as the sum of positive numbers among $a_{j}, a_{j+1}, \cdots, a_{n}$, and $prf_{n+1} = 0$. Since $prf_{j} = prf_{j+1} + \max \left( 0, a_{j}\right)$, $prf$ can be calculated in $\mathcal{O}(n)$. 58 59 You should necessarily pick card $i$ in index of $i$, and can pick all positive cards under card $i$ in initial deck, so your maximum final score will be $(i \% 2 == 1 ? a_{i} : 0) + prf_{i+1}$. 60 61 The answer is $\max \left( (i \% 2 == 1 ? a_{i} : 0) + prf_{i+1} \, | \, 1 \le i \le n \right)$. 62 63 There are lots of other solutions too. 64 65 [1882D - Tree XOR](/contest/1882/problem/D "Codeforces Round 899 (Div. 2)") 66 67 **Hint 1** 68 69 Try to solve the problem for single root. 70 71 **Hint 2** 72 73 For any vertex $v$ which isn't the root, denote $par_{v}$ as the parent of $v$. Then value of $a_{v} \oplus a_{par_{v}}$ only changes if we perform the operation on $v$. 74 75 **Hint 3** 76 77 Since $x_{1} \oplus x_{2} \oplus \cdots \oplus x_{m} \le x_{1} + x_{2} + \cdots + x_{m}$ for any numbers $x_{1}, x_{2}, \cdots, x_{m}$, we can assume that there is at most operation performed in same vertex. 78 79 **Tutorial** 80 81 Let's solve the problem for single root first. 82 83 Denote the operation in the statement as $op(v, c)$, and size of $v$'s subtree as $s_{v}$. 84 85 The goal is to make $a_{v} \oplus a_{par_{v}} = 0$ for every non-root vertex $v$. This value is changed only when we select $v$. To make $a_{v} \oplus a_{par_{v}}$ to $0$, we should perform $op \left( v, a_{v} \oplus a_{par_{v}} \right)$ (Look Hint 3). 86 87 Therefore, the answer sill be $\sum_{i != root} s_{i} \times (a_{i} \oplus a_{par_{i}})$. Now our task is to calculate this for all roots. This can be done by lots of ways, and the following algorithm is one way. 88 89 Calculate the answer for $1$ as root first in $\mathcal{O}(n)$. Now, we will traverse the tree starting at vertex $1$ and keep updating the answer. If root changes from $q$ to $r$ ($q$ and $r$ are adjacent), every vertex except $q$ and $r$ will have same parents and subtree size, so will contribute same to the answer, so we only need to consider $q$ and $r$ to calculate the change. Edge connecting $q$ and $r$ will divide the tree into parts: each of size $X$ and $Y$. If root changes $q$ to $r$, $Y \times (a_{q} \oplus a_{r})$ will be subtracted, and $X \times (a_{q} \oplus a_{r})$ will be added to the answer. $X$ and $Y$ can be pre-calculated in $\mathcal{O}(n)$, so this update costs $\mathcal{O}(1)$. 90 91 Since changing root into the adjacent vertex costs $\mathcal{O}(1)$, answer for all roots can be calculated in $\mathcal{O}(n)$. 92 93 [1882E1 - Two Permutations (Easy Version)](/contest/1882/problem/E1 "Codeforces Round 899 (Div. 2)") 94 95 **Hint 1** 96 97 Let's think two permutations independently. The goal is to make sequence of operations for each permutation which have same parity of number of operations. 98 99 **Hint 2** 100 101 Try to sort single permutation of length $N$, using at most $3N$ operations. It is always possible. 102 103 **Hint 3** 104 105 If the permutation's length is odd, you can perform operation at index $1$ for $N$ times and return to the same permutation. 106 107 **Hint 4** 108 109 If the permutation's length is even, the parity of inversion number changes in each operations. 110 111 **Tutorial** 112 113 Hints above were the summary of the tutorial. Please check them. 114 115 First, let's do Hint 2. There are lots of ways to do this, and I'd like to introduce one which I thought first. It is possible to swap two elements using $3$ operations. Let's denote the two elements as $x$ and $y$, and permutation as $[[ A ] x [ B ] y [ C ]]$ ($[ A ], [ B ], [ C ]$ are subarrays). Then: 116 117 1. Perform the operation at $x$. Permutation becomes $[[ B ] y [ C ] x [ A ]]$. 118 2. Perform the operation at $y$. Permutation becomes $[[ C ] x [ A ] y [ B ]]$. 119 3. Perform the operation at $x$. Permutation becomes $[[ A ] y [ B ] x [ C ]]$. 120 121 Using this, we can sort the single permutation of length $N$ using at most $3N$ operations, since we can sort the permutation by $N$ swaps. 122 123 If this requires same parity of number of operations for $p$ and $q$, the problem is solved. At most $3 \max(m, n)$ operations are used. 124 125 Else, if $n$ or $m$ is odd, we can make the parity equal by method provided in Hint 3. At most $4 \max(m, n)$ operations are used. 126 127 Else, then $n$ and $m$ is both even. In this case, it's impossible because of Hint 4. 128 129 The overall time complexity is $\mathcal{O}(n + m)$ in this solution. 130 131 Lastly, here is the proof of Hint 4. 132 133 Proof: Let's consider the permutation of length $N$($N$ is even). Denote the permutation as $[[ A ] x [ B ]]$, and the length of $[ A ]$ and $[ B ]$ as $n_{A}$ and $n_{B}$. Here $n_{A} + n_{B} = N-1$ so one of $n_{A}$ and $n_{B}$ is even and one of them is odd. Permutation becomes $[[ B ] x [ A ]]$ after the operation. 134 135 First, the parity of inversion number from two elements of $[ A ]$ or two elements of $[ B ]$ doesn't change, because their order inside doesn't change. 136 137 Second, the parity of inversion number from one element of $[ A ]$ and one element of $[ B ]$ doesn't change, because sum of them are $n_{A} \times n_{B}$, which is even. 138 139 Third, the parity of inversion number from $x$ and one element of $[ A ]$ or $[ B ]$ changes, because sum of them are $n_{A} + n_{B}$, which is odd. 140 141 If we add these three, we can lead to the conclusion that the parity of inversion number must change. The text may look a bit complicated, but it will not be that hard if you write them in your own :) 142 143 [1882E2 - Two Permutations (Hard Version)](/contest/1882/problem/E2 "Codeforces Round 899 (Div. 2)") 144 145 Special thanks to [kizen](/profile/kizen "Grandmaster kizen") providing an key idea which motivated me to make this problem! 146 147 **Hint 1** 148 149 The solution is completely different from E1. A brilliant idea is required. Maybe the fact that checker is implemented in linear time might be the hint. 150 151 **Hint 2** 152 153 Find a way changing the operation to 'swap'. 154 155 **Hint 3** 156 157 Add an extra character. 158 159 **Tutorial** 160 161 Add an extra character '$X$' in front of the permutation. Here position of $X$ won't be changed by the operation, and will always locate at left of $p_{1}$. Then in each operation, the permutation will change as: $[X [ A ] c [ B ]] \rightarrow [X [ B ] c [ A ]]$. 162 163 Now, let's consider the array made by $X$ and permutation as **circular**. This is possible because $X$ is always in left of $1$st element, so it marks the start of the permutation. Then $[X [ B ] c [ A ]]$ is equivalent with $[c [ A ] X [ B ]]$. 164 165 Then the operation is: $[X [ A ] c [ B ]] \rightarrow [c [ A ] X [ B ]]$, which is same with swapping $X$ and $c$. 166 167 Now we need to calculate the minimum odd number of swaps and even number of swaps(of $X$ and any element) each, turning $[X\,p_{1}\,p_{2}\,\cdots\,p_{n}]$ to one of $[X\,1\,2\,\cdots\,n]$, $[n\,X\,1\,2\,\cdots\,(n-1)]$, $[(n-1)\,n\,X\,1\,\cdots\,(n-2)]$, $\cdots$, $[1\,2\,\cdots\,n\,X]$. 168 169 To calculate the minimum number of swaps required to turn $[X\,p_{1}\,p_{2}\,\cdots\,p_{n}]$ to the given array, first renumber the initial array to $[X\,1\,2\,\cdots\,n]$, then change the given array in the same correspondence. Do permutation cycle decomposition. Then the answer is (sum of (size + 1) for cycles which have size $\ge$ 2 and don't contain $X$) + ($X$'s cycle size $-$ 1). This can be proven easily by counting the number of elements which go into the proper place in each operations. 170 171 Calculate this for all $[X\,1\,2\,\cdots\,n]$, $[n\,X\,1\,2\,\cdots\,(n-1)]$, $[(n-1)\,n\,X\,1\,\cdots\,(n-2)]$, $\cdots$, $[1\,2\,\cdots\,n\,X]$. Since we can't make the same array using different parity of number of swaps, we can achieve the goal by calculating the minimum odd number and minimum even number each. 172 173 The overall time complexity is $O(n^{2}+m^{2})$. 174 175 **Challenge** 176 177 Try solving E1 in $n,\,m \le 10^{5}$, using at most $1.5 \times 10^{5}$ operations. It is solvable :)