1896.md (36509B)
1 Source: https://codeforces.com/blog/entry/122172 2 3 ## [1896A - Пиковые обмены](/contest/1896/problem/A) 4 5 Writer: [maomao90](/profile/maomao90 "Гроссмейстер maomao90") 6 7 **Hint 1** 8 9 Look at the samples. 10 11 **Solution** 12 13 Observe that since we are only allowed to choose $i \ge 2$ to swap $a_i$ and $a_{i+1}$, it means that $a_1$ cannot be modified by the operation. Hence, $a_1 = 1$ must hold. We can prove that as long as $a_1 = 1$, we will be able to sort the array. 14 15 Consider the largest element of the array. Let its index be $i$. Our objective is to move $a_i$ to the end of the array. If $i = n$, it means that the largest element is already at the end. Otherwise, since $a_i$ is the largest element, this means that $a_{i-1} \lt a_i$ and $a_i \gt a_{i+1}$. Hence, we can do an operation on index $i$ and move the largest element one step closer to the end. We repeatedly do the operation until we finally move the largest element to the end of the array. Then, we can pretend that the largest element does not exist and do the same algorithm for the prefix of size $n - 1$. Hence, we will able to sort the array by doing this repeatedly. 16 17 **Implementation** 18 19 ``` 20 #include <bits/stdc++.h> 21 using namespace std; 22 typedef long long ll; 23 typedef vector <ll> vi; 24 int main() { 25 int t; 26 cin >> t; 27 while (t --> 0) { 28 int n; 29 cin >> n; 30 vi arr(n); 31 for (int i = 0; i < n; i++) { 32 cin >> arr[i]; 33 } 34 if (arr[0] == 1) { 35 cout << "YES"; 36 } else { 37 cout << "NO"; 38 } 39 cout << '\n'; 40 } 41 } 42 ``` 43 44 ## [1896B - AB-обмен](/contest/1896/problem/B) 45 46 Writer: [maomao90](/profile/maomao90 "Гроссмейстер maomao90") 47 48 **Hint 1** 49 50 What happens when $s$ starts with some $\texttt{B}$ and ends with some $\texttt{A}$? 51 52 **Solution** 53 54 If the string consists of only $\texttt{A}$ or only $\texttt{B}$, no operations can be done and hence the answer is $0$. Otherwise, let $x$ be the smallest index where $s_x = \texttt{A}$ and $y$ be the largest index where $x_y = \texttt{B}$. If $x \gt y$, this means that the string is of the form $s=\texttt{B}\ldots\texttt{BA}\ldots\texttt{A}$. Since all the $\texttt{B}$ are before the $\texttt{A}$, no operation can be done and hence the answer is also $0$. 55 56 Now, we are left with the case where $x \lt y$. Note that $s[1,x-1] = \texttt{B}\ldots\texttt{B}$ and $s[y+1,n] = \texttt{A}\ldots\texttt{A}$ by definition. Since the operation moves $\texttt{A}$ to the right and $\texttt{B}$ to the left, this means that $s[1,x - 1]$ will always consist of all $\texttt{B}$ and $s[y + 1, n]$ will always consist of all $\texttt{A}$. Hence, no operation can be done from index $1$ to $x - 1$ as well as from index $y$ to $n - 1$. 57 58 The remaining indices where an operation could be done are from $x$ to $y - 1$. It can be proven that all $y - x$ operations can be done if their order is chosen optimally. Let array $b$ store the indices of $s$ between $x$ and $y$ that contain $\texttt{B}$ in increasing order. In other words, $x \lt b_1 \lt b_2 \lt \ldots \lt b_k = y$ and $b_i = \texttt{B}$, where $k$ is the number of occurences of $\texttt{B}$ between $x$ and $y$. For convenience, we let $b_0 = x$. Then, we do the operations in the following order: 59 60 $b_1 - 1, b_1 - 2, \ldots, b_0 + 1, b_0,$ 61 62 $b_2 - 1, b_2 - 2, \ldots, b_1 + 1, b_1,$ 63 64 $b_3 - 1, b_3 - 2, \ldots, b_2 + 1, b_2,$ 65 66 $\vdots$ 67 68 $b_k - 1, b_k - 2, \ldots, b_{k - 1} + 1, b_k$ 69 70 It can be seen that the above ordering does operation on all indices between $x$ and $y - 1$. To see why all of the operations are valid, we look at each row separately. Each row starts with $b_i - 1$, which is valid as $s_{b_i} = \texttt{B}$ and $s_{b_i - 1} = \texttt{A}$ (assuming that it is not the last operation of the row). Then, the following operations in the same row move $\texttt{B}$ to the left until position $b_{i - 1}$. To see why the last operation of the row is valid as well, even though $s_{b_{i - 1}}$ might be equal to $\texttt{B}$ initially by definition, either $i = 1$ which means that $s_{b_0} = s_x = \texttt{A}$, or an operation was done on index $b_{i - 1} - 1$ in the previous row which moved $\texttt{A}$ to index $b_{i - 1}$. Hence, all operations are valid. 71 72 **Implementation** 73 74 ``` 75 #include <bits/stdc++.h> 76 using namespace std; 77 78 char s[200005]; 79 80 signed main() { 81 ios_base::sync_with_stdio(0); 82 cin.tie(0); cout.tie(0); 83 int tc, n; cin >> tc; 84 while (tc--) { 85 cin >> n; s[n + 1] = 'C'; 86 for (int i = 1; i <= n; ++i) cin >> s[i]; 87 int pt1 = 1, pt2 = 1, ans = 0; 88 while (s[pt1] == 'B') ++pt1, ++pt2; 89 while (pt1 <= n) { 90 int cntA = 0, cntB = 0; 91 while (s[pt2] == 'A') ++pt2, ++cntA; 92 while (s[pt2] == 'B') ++pt2, ++cntB; 93 if (s[pt2 - 1] == 'B') ans += pt2 - pt1 - 1; 94 if (cntB) pt1 = pt2 - 1; 95 else break; 96 } 97 cout << ans << '\n'; 98 } 99 } 100 ``` 101 102 ## [1896C - Сопоставление массивов](/contest/1896/problem/C) 103 104 Writer: [maomao90](/profile/maomao90 "Гроссмейстер maomao90") 105 106 **Hint 1** 107 108 Consider a greedy algorithm. 109 110 **Solution** 111 112 For simplicity, assume that both arrays $a$ and $b$ are sorted in increasing order. The final answer can be obtained by permuting the answer array using the same permutation to permute sorted array $a$ to the original array $a$. 113 114 **Claim**: If the rearrangement $b_{x + 1}, b_{x + 2}, \ldots, b_n, b_1, b_2, \ldots, b_x$ does not have beauty $x$, it is not possible to rearrange $b$ to make the beauty equals to $x$. 115 116 *Proof*: Suppose there exists an alternative rearrangement different from above represented by permutation $p$ where $b_{p_1}, b_{p_2}, \ldots, b_{p_n}$ results in a beauty of $x$. Let array $q$ represent the $x$ indices where $a_i \gt b_{p_i}$ in increasing order. In other words, $1 \le q_1 \lt q_2 \lt \ldots \lt q_x \le n$ and $a_{q_i} \gt b_{p_{q_i}}$. Let $i$ be the largest index where $q_i \neq n - i + 1$ ($q_i \lt n - i + 1$ also holds due to strict inequality above). We know that $a_{q_i} \gt b_{p_{q_i}}$ and $a_{n - i + 1} \le b_{p_{n - i + 1}}$. Since $a$ is sorted and $q_i \lt n - i + 1$, we have $a_{q_i} \le a_{n - i + 1}$, and hence, $a_{n - i + 1} \gt b_{p_{q_i}}$ and $a_{q_i} \le b_{p_{n - i + 1}}$. This means that we can swap $p_{q_i}$ with $p_{n - i + 1}$ without changing the beauty of the array, while allowing $q_i = n - i + 1$. Hence, by doing the swapping repeatedly, we will get $q_i = n - i + 1$ for all $i$ between 1 and $x$. 117 118 An alternative interpretation to the result above is that we managed to obtain a solution where for all $i$ between $1$ and $n - x$, we have $a_i \le b_{p_i}$. On the other hand, for all $i$ between $n - x + 1$ and $n$, we have $a_i \gt b_{p_i}$. Let $i$ be the largest index between $1$ and $n - x$ where $p_i \neq i + x$ ($p_i \lt i + x$ due to maximality). Then, let $j$ be the index where $p_j = i + x$. Consider two cases: 119 120 * $j \le n - x$. Since $i$ is the largest index where $p_i \neq i + x$, this means that $j \lt i$ and hence $a_j \le a_i$. We have $a_i \le b_{p_i} \le b_{i + x} = b_{p_j}$ and $a_j \le a_i \le b_{p_i}$. Hence, we can swap $p_i$ and $p_j$ without changing the beauty of the array, while allowing $p_i = i + x$. 121 * $j \gt n - x$. We have $a_i \le b_{p_i} \le b_{i + x} = b_{p_j}$ and $a_j \gt b_{p_j} = b_{i + x} \gt b_{p_i}$. Hence, we can swap $p_i$ and $p_j$ without changing the beauty of the array, while allowing $p_i = i + x$. 122 123 By repeating the above repeatedly, we can obtain a solution where $p_i = i + x$ for all $i$ between $1$ and $n - x$. Let $i$ be the smallest index between $n - x + 1$ and $n$ where $p_i \neq i - n + x$ ($p_i \gt i - n + x$ by minimality). Then, let $j$ be the index where $p_j = i - n + x$. Note that $j \gt n - x$ as well since $p_i = i + x$ for all $i$ between $1$ and $n - x$. Since $i$ is the smallest index where $p_i \neq i - n + x$, this means that $i \lt j$ and hence $a_i \le a_j$. We have $a_i \gt b_{p_i} \ge b_{i - n + x} = b_{p_j}$ and $a_j \ge a_i \gt b_{p_i}$. Hence, we can swap $p_i$ and $p_j$ without changing the beauty of the array, while allowing $p_i = i - n + x$. By doing this repeatedly, we can obtain a solution where $p_i = i - n + x$ for all $i$ between $n - x + 1$ and $n$. Now, $p = [x + 1, x + 1, \ldots, n, 1, 2, \ldots, x]$, which matches the rearrangement in our claim. 124 125 **Implementation** 126 127 ``` 128 #include <bits/stdc++.h> 129 using namespace std; 130 131 #define REP(i, s, e) for (int i = (s); i < (e); i++) 132 #define RREP(i, s, e) for (int i = (s); i >= (e); i--) 133 134 const int INF = 1000000005; 135 const int MAXN = 200005; 136 137 int t; 138 int n, x; 139 int a[MAXN], b[MAXN], aid[MAXN]; 140 int ans[MAXN]; 141 142 int main() { 143 ios::sync_with_stdio(0), cin.tie(0); 144 cin >> t; 145 while (t--) { 146 cin >> n >> x; 147 REP (i, 0, n) { 148 cin >> a[i]; 149 } 150 REP (i, 0, n) { 151 cin >> b[i]; 152 } 153 iota(aid, aid + n, 0); 154 sort(aid, aid + n, [&] (int l, int r) { 155 return a[l] < a[r]; 156 }); 157 sort(b, b + n); 158 REP (i, 0, x) { 159 ans[aid[n - x + i]] = b[i]; 160 } 161 REP (i, x, n) { 162 ans[aid[i - x]] = b[i]; 163 } 164 REP (i, 0, n) { 165 x -= a[i] > ans[i]; 166 } 167 if (x == 0) { 168 cout << "YES\n"; 169 REP (i, 0, n) { 170 cout << ans[i] << ' '; 171 } 172 cout << '\n'; 173 } else { 174 cout << "NO\n"; 175 } 176 } 177 return 0; 178 } 179 ``` 180 181 ## [1896D - Единицы и двойки](/contest/1896/problem/D) 182 183 Writer: [lanhf](/profile/lanhf "Мастер lanhf") 184 185 **Hint 1** 186 187 Consider some small examples and write down every possible value of subarray sums. Can you see some patterns? 188 189 **Solution** 190 191 Denote $s[l,r]$ as the sum of subarray from $l$ to $r$. 192 193 **Claim**: If there is any subarray with sum $v\ge 2$, we can find a subarray with sum $v-2$. 194 195 *Proof*: Suppose $s[l,r]=v$, consider 3 cases: 196 197 * $a[l]=2$, we have $s[l+1,r]=v-2$. 198 * $a[r]=2$, we have $s[l,r-1]=v-2$. 199 * $a[l]=a[r]=1$, we have $s[l+1,r-1]=v-2$. 200 201 So to check if there exists a subarray whose sum equals $v$, we can find the maximum subarray sum having the same parity with $v$ and compare it with $v$. 202 203 The case where $(s[1,n]-v)\%2=0$ is obvious, suppose the opposite happens. If array $a$ is full of $2$-s, the answer is $\texttt{NO}$. Otherwise, let $x$ and $y$ be the positions of the first $1$ and last $1$ in $a$. Any subarray with $l\le x\le y\le r$ will have a different parity with $v$. So we will compare $\max(s[x+1, n],s[1,y-1])$ with $v$ to get the answer. 204 205 **Implementation** 206 207 ``` 208 #include <bits/stdc++.h> 209 210 using namespace std; 211 212 int main() { 213 cin.tie(0)->sync_with_stdio(0); 214 int t; cin >> t; 215 while (t--) { 216 int n, q; cin >> n >> q; 217 vector<int> a(n); 218 set<int> pos; 219 for (int i = 0; i < n; i++) { 220 cin >> a[i]; 221 if (a[i] == 1) pos.insert(i); 222 } 223 while (q--) { 224 int cmd; cin >> cmd; 225 if (cmd == 1) { 226 int v; cin >> v; 227 int num = pos.size(); 228 if ((v - num) & 1) { 229 if (num == 0) cout << "NO"; 230 else { 231 int s1 = 2 * *pos.rbegin() - (num - 1); 232 int s2 = 2 * (n - *pos.begin() - 1) - (num - 1); 233 if (v <= max(s1, s2)) cout << "YES"; 234 else cout << "NO"; 235 } 236 } else { 237 if (v <= 2 * n - num) cout << "YES"; 238 else cout << "NO"; 239 } 240 cout << '\n'; 241 } else { 242 int i; cin >> i; i--; 243 pos.erase(i); 244 cin >> a[i]; 245 if (a[i] == 1) pos.insert(i); 246 } 247 } 248 } 249 } 250 ``` 251 252 ## [1896E - Сортировка перестановки](/contest/1896/problem/E) 253 254 Writer: [maomao90](/profile/maomao90 "Гроссмейстер maomao90") 255 256 **Hint 1** 257 258 For each index $i$ from $1$ to $n$, let $h_i$ denote the number of cyclic shifts needed to move $a_i$ to its correct spot. In other words, $h_i$ is the minimum value such that $(i + h_i - 1)\ \%\ n + 1 = a_i$. How can we get the answer from $h_i$? 259 260 **Solution** 261 262 For convenience, we will assume that the array is cyclic, so $a_j = a_{(j - 1)\ \%\ n + 1}$. The answer for each index $i$ from $1$ to $n$ is $h_i$ (defined in hint 1) minus the number of indices $j$ where $i \lt j \lt i + h_i$ and $i \lt a_j \lt i + h_i$ (or $i \lt a_j + n \lt i + h_i$ to handle cyclic case when $i + h_i \gt n$). This is because the value that we are calculating is equal to the number of positions that $a_i$ will skip during the rotation as the index is already good. 263 264 To calculate the above value, it is convenient to define an array $b$ of size $2n$ where $b_i = a_i$ for all $i$ between $1$ to $n$, and $b_i = a_{i - n} + n$ for all $i$ between $n + 1$ to $2n$ to handle cyclicity. We will loop from $i = 2n$ to $i = 1$, and do a point increment to position $a_i$ if $a_i \ge i$, otherwise, do a point increment to position $a_i + n$. Then, to get the answer for index $i$, we do a range sum query from $i + 1$ to $i + h_i - 1$. Point increment and range sum query can be done using a binary indexed tree in $O(\log n)$ time per query/update. Hence, the problem can be solved in $O(n\log n)$ time. 265 266 **Implementation** 267 268 ``` 269 #include <bits/stdc++.h> 270 using namespace std; 271 272 #define REP(i, s, e) for (int i = (s); i < (e); i++) 273 #define RREP(i, s, e) for (int i = (s); i >= (e); i--) 274 #define ALL(_a) _a.begin(), _a.end() 275 #define SZ(_a) (int) _a.size() 276 277 const int INF = 1000000005; 278 const int MAXN = 1000005; 279 280 int t; 281 int n; 282 int p[MAXN]; 283 int ans[MAXN]; 284 285 int fw[MAXN * 2]; 286 void incre(int i, int x) { 287 for (; i <= 2 * n; i += i & -i) { 288 fw[i] += x; 289 } 290 } 291 int qsm(int i) { 292 int res = 0; 293 for (; i > 0; i -= i & -i) { 294 res += fw[i]; 295 } 296 return res; 297 } 298 inline int qsm(int s, int e) { 299 return qsm(e) - qsm(s - 1); 300 } 301 302 int main() { 303 #ifndef DEBUG 304 ios::sync_with_stdio(0), cin.tie(0); 305 #endif 306 cin >> t; 307 while (t--) { 308 cin >> n; 309 REP (i, 1, n + 1) { 310 cin >> p[i]; 311 } 312 REP (i, 0, 2 * n + 5) { 313 fw[i] = 0; 314 } 315 vector<pair<int, int>> rgs; 316 REP (i, 1, n + 1) { 317 if (i <= p[i]) { 318 rgs.push_back({i, p[i]}); 319 rgs.push_back({i + n, p[i] + n}); 320 } else { 321 rgs.push_back({i, p[i] + n}); 322 } 323 } 324 sort(ALL(rgs), greater<pair<int, int>>()); 325 for (auto [l, r] : rgs) { 326 if (l <= n) { 327 ans[p[l]] = r - l - qsm(l, r); 328 } 329 incre(r, 1); 330 } 331 REP (i, 1, n + 1) { 332 cout << ans[i] << ' '; 333 } 334 cout << '\n'; 335 } 336 return 0; 337 } 338 ``` 339 340 ## [1896F - Инвертирование скобок](/contest/1896/problem/F) 341 342 Writer: [maomao90](/profile/maomao90 "Гроссмейстер maomao90") 343 344 **Hint 1** 345 346 The operation is equivalent to toggling $s$ at every odd $i$ where $b_i$ is an open bracket and every even $i$ where $b_i$ is a closed bracket. 347 348 **Proof** 349 350 Suppose there are $x$ open brackets and $y$ close brackets between positions $1$ and $i$. Note that $x \ge y$ by definition of balanced bracket sequences. - Case 1: $b_i$ is an open bracket. Position $i$ will be toggled exactly $x - y$ times as $y$ of the open brackets will be matched before position $i$, and the remaining $x - y$ open brackets will only be matched after position $i$. This means that position $i$ will be toggled only if $x - y$ is odd, and hence, $x - y + 2y = x + y = i$ must be odd as well. - Case 2: $b_i$ is a close bracket. Position $i$ will be toggled exactly $x - y + 1$ times as $y - 1$ of the open brackets will be matched before $i$, $1$ of the open bracket will be matched with position $i$, and the remaining $x - y$ open brackets will be matched after position $i$. This means that position $i$ will be toggled only if $x - y$ is even, and hence, $x - y + 2y = x + y = i$ must be even as well. 351 352 **Hint 2** 353 354 Every operation will always toggle $s_1$ and $s_n$. Furthermore, every operation will always toggle an even number of positions. 355 356 **Proof** 357 358 If $s$ is toggled at an open bracket, $s$ will be toggled at its matching close bracket as well. 359 360 **Hint 3** 361 362 If $s_1 \neq s_n$ or there is an odd number of $\texttt{1}$s in $s$, it is not possible to change all elements of $s$ to $\texttt{0}$. Otherwise, it is always possible. 363 364 **Hint 4** 365 366 If it is possible to change all elements of $s$ to $\texttt{0}$, at most $3$ operations are needed. 367 368 **Solution 1** 369 370 From hint 3, we know the cases where it is impossible to change all elements of $s$ to $\texttt{0}$. We will now only consider the case where it is possible to change all elements of $s$ to $\texttt{0}$. 371 372 Using hint 1, we can easily check whether it is possible to change all elements of $s$ to $\texttt{0}$ using only one operation by first constructing the bracket sequence and then checking whether the resultant bracket sequence is balanced. From now on, we will assume that it is not possible to change all elements of $s$ to $\texttt{0}$ using one operation. 373 374 Suppose $s_1 = s_n = \texttt{1}$. We know from hint 2 that each operation will always toggle $s_1$ and $s_n$, so since it is not possible to change all elements of $s$ to $\texttt{0}$ using one operation, we will need three operations. If we let the first operation be $b=\texttt{(()()}\ldots\texttt{()())}$, $s_1$ and $s_n$ will be toggled while the remaining elements stay the same. Now, $s_1 = s_n = \texttt{0}$, so if we can solve this case using only two operations, it means that we can solve the $s_1 = s_n = \texttt{1}$ case using only three operations. 375 376 To solve the final case where $s_1 = s_n = \texttt{0}$, we will look at a special balanced bracket sequences $b = \texttt{(()()}\ldots\texttt{()())}$. Notice that if we do an operation using this bracket sequence, only $s_1$ and $s_n$ will be toggled. Suppose there exist an index $i$ between $2$ and $2n - 2$ where we want to toggle both $s_i$ and $s_{i + 1}$. We can take the special balanced bracket sequence $b = \texttt{(()()}\ldots\texttt{()())}$, then swap $b_i$ and $b_{i + 1}$. This will always result in a balanced bracket sequence that will toggle $s_1$, $s_n$, as well as the desired $s_i$ and $s_{i + 1}$. This will allow us to change all elements of $s$ to $\texttt{0}$ in $2n$ moves as we can scan from $i = 2$ to $i = 2n - 2$ and do an operation toggling $s_i$ and $s_{i+1}$ if $s_i = \texttt{1}$. Since there is an even number of $\texttt{1}$s in $s$ from hint 3, toggling adjacent positions will always change all elements of $s$ to $\texttt{0}$. 377 378 To reduce the number of operations from $2n$ to $2$, notice that a lot of the operations can be parallelized into a single operation. Let $A_0$ represent the set of even indices between $2$ and $2n - 2$ where we want to toggle $s_i$ and $s_{i + 1}$. Similarly, let $A_1$ represent the set of odd indices between $2$ and $2n - 2$ where we want to toggle $s_i$ and $s_{i + 1}$. In a single operation, we can take the special balanced bracket sequence $b = \texttt{(()()}\ldots\texttt{()())}$, and swap $b_i$ and $b_{i + 1}$ for all $i$ that is in the set $A_0$. Since $A_0$ only contains even indices, the swaps are non-intersecting, and hence, the resultant bracket sequence will still be balanced and $s_1$, $s_n$, as well as $s_i$ and $s_{i + 1}$ will be toggled for all the desired even indices $i$. We can use the same strategy with $A_1$, starting with the same special balanced bracket sequence and then swapping $b_i$ and $b_{i + 1}$ for all $i$ that is in set $A_1$. Hence, after using these two operations, all elements of $s$ will change to $\texttt{0}$. 379 380 **Solution 2** 381 382 We will demonstrate a way to use $2$ bracket sequence to solve any binary string whose first and last element is $\texttt{0}$ and who also has an even number of $\texttt{1}$s. 383 384 Defined the balance of an (incomplete) bracket sequence as the number of open brackets minus the number of closed brakcets. For example, `((()` has balance $2$, `(()()((` has balance $3$ and `()` has balance $0$. 385 386 Using hint $1$ we can see that the resulting binary string will contain `0` at position $i$ iff the character at position $i$ in both bracket sequences is the same. Suppose the balance of your current bracket sequences is $(a,b)$. You can change it $(a\pm 1, b\pm 1)$. If both $\pm$ have the same parity, then the resulting binary string will contain $\texttt{0}$ at that position. 387 388 Now, we will demonstrate a greedy algorithm. 389 390 $(0,0) \to (1,1) \to (0,2),(2,2) \to (1,3),(1,1) \to (0,2),(2,2) \to \ldots \to (1,1) \to (0,0)$ 391 392 One can show by a simple parity argument that the second last balance must necessarily be $(1,1)$ since the number of $\texttt{1}$s in the string is even. 393 394 **Solution 3** 395 396 Similar to solution 2, we will demonstrate a way to use $2$ bracket sequence to solve any binary string whose first and last element is $\texttt{0}$ and who also has an even number of $\texttt{1}$s. 397 398 Using the same greedy argument in solution 2 (or by guessing), we know that we can always use two bracket sequences where the number of open brackets minus the number of close brackets is always between $0$ and $3$ for all prefixes of the bracket sequence. For convenience, we will define "balance" as the number of open brackets minus the number of close brackets. 399 400 Hence, we can do dynamic programming using the states $dp[i][balance1][balance2]$ which returns whether it is possible to create two bracket sequences $b1$ and $b2$ of length $i$ such that the balance of $b1$ and $b2$ are $balance1$ and $balance2$ respectively and $s[1, i]$ becomes all $\mathtt{0}$. The transition can be done by making sure that the balances stay between $0$ and $3$ and that $b1_i \neq b2_i$ if $s_i=\mathtt{1}$ and vice versa. 401 402 **Implementation** 403 404 ``` 405 #include <bits/stdc++.h> 406 using namespace std; 407 408 void solve(int n, string s) { 409 vector<int> a; 410 for (char &i : s) { 411 a.push_back(i & 1); 412 } 413 414 if (a.front() != a.back()) { 415 cout << -1 << endl; 416 return ; 417 } 418 419 if (count(a.begin(), a.end(), 1) % 2) { 420 cout << -1 << endl; 421 return ; 422 } 423 424 bool flipped = false; 425 if (a.front() == 1 && a.back() == 1) { 426 for (int &i : a) i ^= 1; 427 flipped = true; 428 } 429 430 string l(2 * n, '-'), r(2 * n, '-'); 431 int cnt = 0; 432 for (int i = 0; i < 2 * n; i++) { 433 if (a[i]) { 434 l[i] = (cnt) ? '(' : ')'; 435 r[i] = (cnt ^ 1) ? '(' : ')'; 436 cnt ^= 1; 437 } 438 } 439 440 int tot = count(a.begin(), a.end(), 0) / 2; 441 cnt = 0; 442 for (int i = 0; i < 2 * n; i++) { 443 if (!a[i]) { 444 if (cnt < tot) l[i] = '(', r[i] = '('; 445 else l[i] = ')', r[i] = ')'; 446 cnt++; 447 } 448 } 449 450 if (flipped) { 451 cout << 3 << endl; 452 cout << l << endl; 453 cout << r << endl; 454 for (int i = 0; i < n; i++) cout << "()"; 455 cout << endl; 456 } else { 457 cout << 2 << endl; 458 cout << l << endl; 459 cout << r << endl; 460 } 461 } 462 463 int main() { 464 int t; 465 cin >> t; 466 while (t--) { 467 int n; 468 cin >> n; 469 string s; 470 cin >> s; 471 solve(n, s); 472 } 473 474 return 0; 475 } 476 ``` 477 478 ## [1896G - Гонка пепе](/contest/1896/problem/G) 479 480 Writer: [thenymphsofdelphi](/profile/thenymphsofdelphi "Международный гроссмейстер thenymphsofdelphi") 481 482 **Hint 1** 483 484 Find the fastest pepe in $n + 1$ queries. 485 486 **Hint** 487 488 Divide $n^2$ pepes into $n$ groups $G_1, G_2, \dots, G_n$. For each group $G_i$, use $1$ query to find the fastest pepe in the group, let's call him the *head* of $G_i$. Finally, use $1$ query to find the fastest pepe of all the heads. 489 490 **Hint 2** 491 492 After knowing the fastest pepe, find the second fastest pepe in $n + 1$ queries. 493 494 **Hint** 495 496 Just remove the fastest pepe and repeat the process from hint 1. One of the groups will have size $n - 1$, but we can "steal" one non-head pepe from another already-queried group. 497 498 **Hint 3** 499 500 Note that the above process for Hint 2 uses a lot of repeated queries. Can we optimize it to $2$ queries? 501 502 **Hint** 503 504 Assume that the fastest pepe is the head of $G_i$. After removing him, we can recalculate the head of $G_i$ using $1$ query similar to hint 2. Then, use the second query on all the heads, similar to the last query of hint 1. 505 506 **Hint 4** 507 508 Solve the problem using $2n^2 - n + 1$ queries. 509 510 **Hint** 511 512 Our algorithm has three phases: 513 514 * Phase 1: Divide $n^2$ pepes into $n$ groups $G_1, G_2, \dots, G_n$. For each group $G_i$, use $1$ query to find the fastest pepe in the group, let's call this guy the *head* of $G_i$. 515 * Phase 2: Until there are $2n - 1$ pepes, repeat these two steps: 516 + Use $1$ query to find the fastest pepe of the heads of all groups, then remove him. Assume that this pepe is the head of $G_i$. 517 + Steal non-head pepes from other groups so that $|G_i| = n$, then use $1$ query to recalculate its head. 518 * Phase 3: Until there are $n - 1$ pepes, repeatedly find the fastest pepe using $2$ queries (or $1$ if there are only $n$ pepes left), then remove him. 519 520 Total number of queries is $n + 2(n^2 - 2n + 1) + 2(n - 1) + 1 = 2n^2 - n + 1$. 521 522 **Solution 1** 523 524 Call a pepe *slow* if it does not belong in the fastest $n^2 - n + 1$ pepes. Note that there are $n - 1$ slow pepes, and we do not care for their relative speed. After each query, we know that the fastest pepe cannot be slow. 525 526 We use the algorithm in hint 4 until there are $2n - 1$ pepes left. Since the head of $n$ groups cannot be slow, we are left with exactly $(2n - 1) - n = n - 1$ candidates for slow pepes. Once we determine the $n - 1$ slow pepes, we only need to find the ranking of the other $n$ pepes, which can be done using $n - 1$ queries. 527 528 Total number of queries is $n + 2(n^2 - 2n + 1) + (n - 1) = 2n^2 - 2n + 1$. 529 530 **Solution 2** 531 532 We will try to decrease the number of queries based on the fact that we can omit one query for recalculation when the size of a group decreases from $2$ to $1$. 533 534 We modify the algorithm in hint 4 to maintain an invariant: $|G_i| - |G_j| \le 1$ $\forall \, 1 \le i \lt j \le n$. In other words, we want to make the sizes of these groups as balanced as possible. 535 536 To maintain this, whenever we have $|G_j| - |G_i| = 2$ after removing some pepe, we can transfer any non-head pepe from $G_j$ to $G_i$ to balance these groups out. Next, to recalculate the head of $G_i$, we will "borrow" instead of "steal" from other groups. If the fastest pepe is borrowed from $G_j$, then we transfer a random non-head pepe in $G_i$ back to $G_j$. This works since the head of $G_j$ is faster than the head of $G_i$, which in turn is faster than the random pepe. 537 538 Finally, when there are $2n$ pepes left, all groups have the size of $2$, and we only need to use $1$ query for each pepe from later on. 539 540 Total number of queries is $n + 2(n^2 - 2n) + (n + 1) = 2n^2 - 2n + 1$. 541 542 **Implementation (Solution 1)** 543 544 ``` 545 #include <bits/stdc++.h> 546 547 using namespace std; 548 549 const int N = 30; 550 551 vector<int> buc[N]; 552 int buc_id[N * N], buc_max[N]; 553 int n; 554 555 int ask(vector<int> que) { 556 cout << "?"; 557 for (int i : que) cout << ' ' << i + 1; 558 cout << endl; 559 int res; cin >> res; 560 return res - 1; 561 } 562 563 int ask_all() { 564 vector<int> que; 565 for (int i = 0; i < n; i++) 566 if (buc[i].size()) 567 que.push_back(buc_max[i]); 568 for (int i = 0; i < n; i++) 569 for (int j : buc[i]) 570 if (int(que.size()) < n && j != buc_max[i]) 571 que.push_back(j); 572 return ask(que); 573 } 574 575 void answer(vector<int> ans) { 576 cout << "!"; 577 for (int i : ans) cout << ' ' << i + 1; 578 cout << endl; 579 } 580 581 void add(int id, int pepe) { 582 buc[id].push_back(pepe); 583 buc_id[pepe] = id; 584 } 585 586 void remove(int id, int pepe) { 587 buc[id].erase(find(buc[id].begin(), buc[id].end(), pepe)); 588 } 589 590 void send(int id, vector<int> &que) { 591 for (int pepe : buc[id]) 592 if (int(que.size()) < n && pepe != buc_max[id]) 593 que.push_back(pepe); 594 } 595 596 void check_balance() { 597 size_t min_size = n, max_size = 0; 598 for (int id = 0; id < n; id++) { 599 min_size = min(min_size, buc[id].size()); 600 max_size = max(max_size, buc[id].size()); 601 } 602 assert(max_size - min_size <= 1); 603 } 604 605 int main() { 606 cout << endl; 607 int t; cin >> t; 608 while (t--) { 609 cin >> n; 610 for (int id = 0; id < n; id++) 611 buc[id].clear(); 612 613 for (int pepe = 0; pepe < n * n; pepe++) { 614 buc_id[pepe] = pepe / n; 615 buc[pepe / n].push_back(pepe); 616 } 617 618 for (int id = 0; id < n; id++) 619 buc_max[id] = ask(buc[id]); 620 621 vector<int> ans; 622 623 /// balancing phase 624 for (int step = 0; step < n * n - 2 * n; step++) { 625 ans.push_back(ask_all()); 626 int last_id = buc_id[ans.back()]; 627 remove(last_id, ans.back()); 628 629 vector<int> que; 630 631 for (int pepe : buc[last_id]) 632 que.push_back(pepe); 633 634 /// find bucket with largest size != last_id 635 int max_id = (last_id == 0); 636 for (int id = 0; id < n; id++) 637 if (id != last_id && buc[id].size() > buc[max_id].size()) 638 max_id = id; 639 640 641 send(max_id, que); 642 643 for (int id = 0; id < n; id++) 644 if (id != max_id && id != last_id) 645 send(id, que); 646 647 buc_max[last_id] = ask(que); 648 int move_id = buc_id[buc_max[last_id]]; 649 if (move_id != last_id) { 650 remove(move_id, buc_max[last_id]); 651 add(move_id, buc[last_id].back()); 652 remove(last_id, buc[last_id].back()); 653 add(last_id, buc_max[last_id]); 654 } 655 656 if (buc[last_id].size() == buc[max_id].size() - 2) { 657 if (move_id == max_id) { 658 add(last_id, buc[move_id].back()); 659 remove(move_id, buc[move_id].back()); 660 } else { 661 for (int pepe : buc[max_id]) 662 if (pepe != buc_max[max_id]) { 663 add(last_id, pepe); 664 remove(max_id, pepe); 665 break; 666 } 667 } 668 } 669 670 check_balance(); 671 } 672 673 674 for (int step = 0; step < n + 1; step++) { 675 ans.push_back(ask_all()); 676 int last_id = buc_id[ans.back()]; 677 remove(last_id, ans.back()); 678 if (buc[last_id].size()) 679 buc_max[last_id] = buc[last_id][0]; 680 } 681 682 answer(ans); 683 } 684 } 685 ``` 686 687 **Implementation (Solution 2)** 688 689 ``` 690 #include <bits/stdc++.h> 691 using namespace std; 692 693 #define int long long 694 #define ll long long 695 #define ii pair<ll,ll> 696 #define iii pair<ii,ll> 697 #define fi first 698 #define se second 699 #define debug(x) cout << #x << ": " << x << endl 700 701 #define pub push_back 702 #define pob pop_back 703 #define puf push_front 704 #define pof pop_front 705 #define lb lower_bound 706 #define ub upper_bound 707 708 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 709 #define all(x) (x).begin(),(x).end() 710 #define sz(x) (int)(x).size() 711 712 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 713 714 int n; 715 vector<int> v[25]; 716 717 int ask(vector<int> v){ 718 cout<<"? "; for (auto it:v) cout<<it<<" "; cout<<endl; 719 int res; cin>>res; 720 return res; 721 } 722 723 vector<int> fix(vector<int> v){ 724 int t=ask(v); 725 rep(x,0,n) if (v[x]==t) swap(v[0],v[x]); 726 return v; 727 } 728 729 signed main(){ 730 ios::sync_with_stdio(0); 731 cin.tie(0); 732 cout.tie(0); 733 cin.exceptions(ios::badbit | ios::failbit); 734 735 int TC; 736 cin>>TC; 737 while (TC--){ 738 cin>>n; 739 rep(x,0,n){ 740 v[x].clear(); 741 rep(y,1,n+1) v[x].pub(x*n+y); 742 } 743 744 rep(x,0,n) v[x]=fix(v[x]); 745 746 vector<int> ans; 747 rep(x,0,n*n-2*n+1){ 748 vector<int> t; 749 rep(x,0,n) t.pub(v[x][0]); 750 int best=ask(t); 751 752 int idx=-1; 753 rep(x,0,n) if (t[x]==best) idx=x; 754 755 ans.pub(best); 756 v[idx].erase(v[idx].begin()); 757 758 rep(x,0,n) if (x!=idx){ 759 while (sz(v[x])>1 && sz(v[idx])<n){ 760 v[idx].pub(v[x].back()); 761 v[x].pob(); 762 } 763 } 764 v[idx]=fix(v[idx]); 765 } 766 767 vector<int> a,b; 768 rep(x,0,n){ 769 rep(y,0,sz(v[x])){ 770 if (y==0) a.pub(v[x][y]); 771 else b.pub(v[x][y]); 772 } 773 } 774 set<int> bad=set<int>(all(b)); 775 776 rep(x,0,n-1){ 777 a=fix(a); 778 ans.pub(a[0]); 779 a.erase(a.begin()); 780 a.pub(b.back()); b.pob(); 781 } 782 783 for (auto it:a) if (!bad.count(it)) ans.pub(it); 784 785 cout<<"! "; for (auto it:ans) cout<<it<<" "; cout<<endl; 786 } 787 788 } 789 ``` 790 791 ## [1896H2 - Цикличный Хэмминг (сложная версия)](/contest/1896/problem/H2) 792 793 Writer: [xuanquang1999](/profile/xuanquang1999 "Гроссмейстер xuanquang1999") 794 795 **Hint 1** 796 797 For any $c$ which is a cyclic shift of $t$, what will happen if $h(s,c) \gt 2^k$? 798 799 **Hint 2** 800 801 Try finding some useful relationship between $1$-s of $s$ and $1$-s of $c$. 802 803 **Hint** 804 805 There are exactly $n/2$ positions $i$ such that $s[i]=c[i]=1$. 806 807 **Hint 3** 808 809 Think about polynomial multiplication. 810 811 **Hint 1** 812 813 Consider $S\cdot T$, where $S=\sum s[i]x^i$ and $T=\sum t[2n-i-1]x^i$ (reversed coefficients). 814 815 **Hint 2** 816 817 What are some properties that the coefficients of $S\cdot T$ tell us? 818 819 **Hint** 820 821 Denote $A=S\cdot T$, we have $A[x^i]+A[x^{i+2n}]=n/2$. 822 823 **Hint 3** 824 825 Try factoring $S\cdot T$ into some irreducible polynomials. 826 827 **Hint 4** 828 829 Sort $0,1,\ldots,2n-1$ based on their bit-reversal values and build a binary tree on top of it. What condition should be satisfied on each level of the tree? 830 831 **Solution** 832 833 Consider the polynomial product $A=S\cdot T$, where $S=\sum s[i]x^i$ and $T=\sum t[2n-i-1]x^i$ (reversed coefficients). 834 835 **Claim 1.** For all $0\le i \lt 2n$, we have $A[x^i]+A[x^{i+2n}]=n/2$, where $A[x^k]$ denote the coefficient of $x^k$ in $A$. 836 837 **Claim 2.** We can express $A=(x+1)(x^2+1)(x^4+1)\ldots (x^n+1)(n/2+C(x-1))$ where $C$ is some polynomial with degree not greater than $2n-2$. 838 839 **Proof** 840 841 $ \begin{align} &(x+1)(x^2+1)(x^4+1)\ldots (x^n+1)(n/2+C(x-1))\\ =\ &C(x^{2n}-1)+n/2\cdot (x^0+x^1+x^2+\ldots+x^{2n-1}) \end{align} $ 842 843 It is easy to see that this satisfies claim 1. 844 845 **Claim 3.** Since $x^{2^p}+1$ is cyclotomic polynomial and hence irreducible for all $p$, each factor in $x+1,x^2+1,\ldots,x^n+1$ must divide at least one of $S$ and $T$. And under the constraints that each of $s$ and $t$ must have exactly $n$ $1$-s, this condition is also sufficient. 846 847 **Proof** 848 849 Let $A=(x+1)(x^2+1)(x^4+1)\ldots (x^n+1)\cdot D$. We have $A(1)=n^2$, hence $D(1)=n/2$, which means that $D$ has the form of $n/2+C(x-1)$. Therefore $A$ satisfies claim 2. 850 851 Recall $n=2^k$, define $f_s(mask)$ ($0\le mask \lt 2n$) as the number of string $s$ such that for each $p$ where $p$-th bit of $mask$ is on, $S$ is divisible by $x^{p}+1$. Define $f_t$ similarly for $T$. Define $f^{\prime}_t$ such that $f^{\prime}_t(mask)=f_t(mask\oplus (2n-1))$ where $\oplus$ denotes bitwise XOR. 852 853 The answer to the problem is $\displaystyle\sum_{mask} f_s(mask)\cdot \mu(f^{\prime}_t(mask))$ where $\mu$ denote [Mobius transform](https://codeforces.com/blog/entry/72488). The reason we need Mobius transform is that $mask_s$ does not represent all divisors, just a subset of it. 854 855 Let rearrange elements of $s$ into a new array $s^{\prime}$ so that $s^{\prime}[\text{reverse_bit}(i)]=s[i]$ (for example, with $n=8$, the new order will be $[0,8,4,12,2,6,10,14,1,9,5,13,3,11,7,15]$). Construct a perfect binary tree based on the array $s^{\prime}$. This binary will have $k+2$ levels from $0$ to $k+1$, starting at the root. 856 857 **Claim 4.** $S$ is divisible by $x^{2^p}+1$ if only if for every tree node at $p$-th level, the number of $1$-s of $s^{\prime}$ under both children are equal (the proof is left as an exercise for readers). 858 859 **Hint** 860 861 Group the positions by the remainder when divided by $2^p$, find the necessary condition for each group, and consider its position on the tree. 862 863 Consider the following dynamic programming: $dp_s[i][mask][num]$, where the levels in $mask$ satisfy claim 4 and $num$ is the number of $1$-s under $i$-th node on the tree. Denote $l$ as level of $i$-th node, transitions are: 864 865 * $dp_s[i][mask][num_1+num_2]\text{ += }dp_s[2i][mask][num_1]\cdot dp_s[2i+1][mask][num_2]$ 866 * $dp_s[i][mask+2^l][2\cdot num]\text{ += }dp_s[2i][mask][num]\cdot dp_s[2i+1][mask][num]$ 867 868 The above dp took $\mathcal{O}(n^3)$, which is sufficient to solve the easy version. 869 870 To solve the hard version, we will optimize the above transitions: 871 872 * The first transition is actually the convolution of $dp_s[2i][mask]$ and $dp_s[2i+1][mask]$, we can use FFT to optimize it. 873 * In the second transition, because $num$ is multiplied by $2$ every time, we can omit it and just make the transition to $dp_s[i][mask+2^l][num]$, reduce the length of $dp_s[i][mask+2^l]$ by two. 874 875 By careful analysis, we can show that the time complexity is now $\mathcal{O}(3^k\cdot k)$ (recall $n=2^k$) with a fair constant factor, which solved the hard version.