1867.md (20236B)
1 Source: https://codeforces.com/blog/entry/120353 2 3 Hello everyone! We're very sorry for the delay >_< 4 5 We hope you enjoyed the tasks! Sorry for too tight limits in C so that Java solutions don't pass (actually one of our authors nickname used to be "java." :D), we'll hopefully do a better job next time! Feel free to leave your feedback in the comments. 6 7 [1867A — green_gold_dog, array and permutation](https://codeforces.com/contest/1867/problem/A) 8 9 Author: [green_gold_dog](/profile/green_gold_dog "Grandmaster green_gold_dog") 10 11 **Tutorial** 12 13 Let's subtract $n$ from the minimum number, subtract $n - 1$ from the second minimum, $n - 2$ from the third $\ldots$, and subtract $1$ from the maximum. Then the number of distinct elements will be $n$. Obviously, it is impossible to achieve a better result. 14 15 Let's prove that the number of distinct elements will be equal to $n$. Suppose $c_i = c_j$, then without loss of generality, let's say that $b_i \gt b_j$, then $a_i \leq a_j$, which means $c_i = a_i - b_i$ < $a_j - b_j = c_j$. Contradiction. 16 17 Time Complexity: $O(n \log n)$ per test case. 18 19 **Solution** 20 21 ``` 22 #include <bits/stdc++.h> 23 24 using namespace std; 25 26 typedef long long ll; 27 28 void solve() { 29 ll n; 30 cin >> n; 31 vector<pair<ll, ll>> arr(n); 32 for (ll i = 0; i < n; i++) { 33 ll x; 34 cin >> x; 35 arr[i].first = x; 36 arr[i].second = i; 37 } 38 vector<ll> ans(n); 39 sort(arr.begin(), arr.end()); 40 reverse(arr.begin(),arr.end()); 41 for (ll i = 0; i < n; i++) { 42 ans[arr[i].second] = i + 1; 43 } 44 for (auto i : ans) { 45 cout << i << ' '; 46 } 47 cout << '\n'; 48 } 49 50 int main() { 51 ios_base::sync_with_stdio(false); 52 cin.tie(0); 53 cout.tie(0); 54 ll t = 1; 55 cin >> t; 56 for (ll i = 0; i < t; i++) { 57 solve(); 58 } 59 } 60 ``` 61 62 [1867B — XOR Palindromes](https://codeforces.com/contest/1867/problem/B) 63 64 Author: [ace5](/profile/ace5 "International Master ace5") 65 66 **Tutorial** 67 68 Firstly, a string is a palindrome if and only if for any $i$ ($1 \leq i \leq n$) $s_i = s_{n-i+1}$ (because when reversed, $s_i$ becomes $s_{n-i+1}$). 69 70 We can divide the characters into pairs, where each pair consists of $s_i$ and $s_{n-i+1}$. If $s_i = s_{n-i+1}$, then we need to have $l_i = l_{n-i+1}$ in order to obtain equal elements after XOR. Therefore, either $l_i = l_{n-i+1} = 0$ (with $0$ ones) or $l_i = l_{n-i+1} = 1$ (with $2$ ones). If $s_i \neq s_{n-i+1}$, then $l_i \neq l_{n-i+1}$ must hold ($1$ one in any case). Additionally, if $n$ is odd, then $l_{n/2+1}$ can be either $0$ or $1$ (with $0$ or $1$ ones). 71 72 We can iterate over the number of pairs where $l_i = l_{n-i+1}$ will have two ones, as well as whether there will be a one in the center or not. This way, we can obtain all possible numbers of ones in $l$, i.e., all good $i$. 73 74 Time Complexity: $O(n)$ per test case. 75 76 **Solution** 77 78 ``` 79 #include <bits/stdc++.h> 80 81 using namespace std; 82 83 int main() 84 { 85 ios_base::sync_with_stdio(false); 86 cin.tie(0); 87 int t; 88 cin >> t; 89 while(t--) 90 { 91 int n; 92 cin >> n; 93 string s; 94 cin >> s; 95 string t(n+1,'0'); 96 int ans = 0; 97 int max_1 = 0; 98 int max_2 = 0; 99 for(int i = 0;i <= n/2-1;++i) 100 { 101 if(s[i] == s[n-i-1]) 102 max_2++; 103 else 104 ans++; 105 } 106 if(n%2 == 1) 107 max_1++; 108 for(int j = 0;j <= max_2;++j) 109 { 110 for(int k = 0;k <= max_1;++k) 111 { 112 t[ans + j*2 + k] = '1'; 113 } 114 } 115 cout << t << "\n"; 116 } 117 } 118 ``` 119 120 [1867C-Salyg1n and the MEX Game](https://codeforces.com/contest/1867/problem/C) 121 122 Author: [salyg1n](/profile/salyg1n "Master salyg1n") 123 124 **Tutorial** 125 126 The correct strategy for Alice is to add the number $\operatorname{MEX}(S)$ to the set $S$ on the first move, and add the last removed number on the remaining moves. 127 128 Let m = $\operatorname{MEX}(S \cup {\operatorname{MEX}(S)})$, at the start of the game. In other words, m is equal to the second $\operatorname{MEX}$ of the set $S$. $m \geq 1$. 129 130 Notice that after the first move, $\operatorname{MEX}(S) = m$, and no matter what Bob removes, we will return that number to the set, so the result of the game will always be equal to $m$. 131 132 Let's prove that with Bob's optimal play, we cannot achieve a result greater than m. 133 134 Notice that the $\operatorname{MEX}$ of a set is the largest number k such that all numbers from $0$ to $k-1$ inclusive are present in the set. 135 136 Let $p_i$ be the number of numbers from $0$ to $i-1$ inclusive that appear in the set $S$. Then $\operatorname{MEX}(S)$ is equal to the maximum $i$ such that $p_i = i$. 137 138 If Bob removes the number $y$ during his turn, he decreases all values $p_i$ where $i \gt y$ by $1$. So, if $y = \operatorname{min}(S)$, Bob decreases all non-zero values $p_i$ by $1$. 139 140 Alice can increase some values $p_i$ by $1$ during her turn. Therefore, after Alice's first move, $\operatorname{MEX}(S)$ will no longer increase if Bob keeps removing the minimum, because no non-zero values of $p_i$ will increase (Bob decreases them by $1$, and Alice increases them by at most $1$). 141 142 It is obvious that in order to maximize $\operatorname{MEX}(S)$ after the first move, Alice needs to add the number $\operatorname{MEX}(S)$ to the set $S$. 143 144 We have proven that $R \leq m$ and provided a strategy that achieves a result of $m$. 145 146 Time Complexity: $O(n)$ per test case. 147 148 **Solution** 149 150 ``` 151 #include <iostream> 152 #include <vector> 153 154 using namespace std; 155 156 void solve() { 157 int n; 158 cin >> n; 159 vector<int> s(n); 160 for (int i = 0; i < n; ++i) 161 cin >> s[i]; 162 int mex = -1; 163 for (int i = 0; i < n; ++i) { 164 if (i == 0 && s[i] != 0) { 165 mex = 0; 166 break; 167 } 168 if (i > 0 && s[i] != s[i - 1] + 1) { 169 mex = s[i - 1] + 1; 170 break; 171 } 172 } 173 if (mex == -1) 174 mex = s[n - 1] + 1; 175 cout << mex << endl; 176 int y; 177 cin >> y; 178 while (y != -1) { 179 cout << y << endl; 180 cin >> y; 181 } 182 } 183 184 int main() { 185 int t; 186 cin >> t; 187 while (t--) 188 solve(); 189 190 return 0; 191 } 192 ``` 193 194 [1867D-Cyclic Operations](https://codeforces.com/contest/1867/problem/D) 195 196 Author: [ace5](/profile/ace5 "International Master ace5") 197 198 **Tutorial** 199 200 If $k = 1$, then we can change $b_i$ to $i$, so the answer is YES only if $b_i = i$, otherwise the answer is NO. 201 202 Otherwise, let's build an undirected graph with $n$ vertices and edges ($i, b_i$). Any component of this graph will look like a cycle (possibly of size $1$) to each vertex of which a tree is attached (possibly empty). 203 204 **Proof** 205 206 Let's assume that there are $x$ vertices in a component, then there are also $x$ edges in it (since each vertex has exactly one outgoing edge). We can construct a depth-first search (DFS) tree for this component, which will have $x - 1$ edges. Now, when we add the remaining edge ($u, v$), a cycle is formed in the component (formed by the edge ($u, v$) and the path between $u$ and $v$ in the DFS tree). Each vertex will have a tree attached to it, because before adding the edge, we had a tree. 207 208 Now it is claimed that if the cycle in each component has a size exactly $k$, then the answer is YES, otherwise NO. 209 210 **Proof** 211 212 Let's first consider the situation where the size of the cycle in some component is not $k$. Let the cycle contain vertices $v_1, v_2, \cdots, v_x$ in that order. Now let's look at the last operation in which one of the $l_i$ was equal to some element from the cycle. If the size of the cycle is less than $k$, then in the last operation there will be at least one vertex not from the cycle, which means that at least one vertex from the cycle will be replaced by a number that is not the next vertex in the cycle, which is incorrect because each vertex from the cycle should be replaced by the next vertex after it. If the size of the cycle is greater than $k$, then we will have a vertex from the cycle that will be replaced by a vertex that is not the next vertex in the cycle (otherwise we would have used all the vertices of the cycle, and there are more than $k$ of them). Therefore, in any case, there is no valid last operation with vertices from the cycle, so the answer is NO. 213 214 If the size of the cycle in a component is equal to $k$, then we can apply the following algorithm: 215 216 While there is at least one vertex $v$ in the component that is a leaf, we will perform the operation with $l = [v, b_v, b_{b_v}, \cdots]$ (all elements are distinct because we will enter the cycle and it has a size of $k$). After this operation, we will have $a_v = b_v$, and we can remove vertex $v$ (it had only $1$ outgoing edge). 217 218 When only the cycle remains, we can apply the operation for the vertices in the cycle, preserving the order, and then for all vertices in the component, we will have $a_v = b_v$. By doing this for all components, we will get $a = b$, which is what we wanted, so the answer is YES. 219 220 Time Complexity: $O(n)$ per test case. 221 222 **Solution** 223 224 ``` 225 #include <bits/stdc++.h> 226 227 using namespace std; 228 229 int main() 230 { 231 ios_base::sync_with_stdio(false); 232 cin.tie(0); 233 int t; 234 cin >> t; 235 while(t--) 236 { 237 int n,k; 238 cin >> n >> k; 239 int b[n]; 240 int vis[n]; 241 for(int j = 0;j < n;++j) 242 { 243 cin >> b[j]; 244 vis[j] = 0; 245 } 246 if(k == 1) 247 { 248 int no = 0; 249 for(int j = 0;j < n;++j) 250 { 251 if(b[j] != j+1) 252 { 253 no = 1; 254 } 255 } 256 cout << (no ? "NO\n" : "YES\n"); 257 continue; 258 } 259 int num[n]; 260 int no = 0; 261 int tgr = 1; 262 for(int j = 0;j < n;++j) 263 { 264 if(!vis[j]) 265 { 266 int ind = j; 267 int cnum = 0; 268 while(!vis[ind]) 269 { 270 vis[ind] = tgr; 271 num[ind] = cnum++; 272 ind = b[ind]-1; 273 } 274 if(vis[ind] != tgr) 275 { 276 tgr++; 277 continue; 278 } 279 if(cnum-num[ind] != k) 280 { 281 no = 1; 282 break; 283 } 284 tgr++; 285 } 286 } 287 cout << (no ? "NO\n" : "YES\n"); 288 } 289 } 290 ``` 291 292 [1867E1-Salyg1n and Array (simple version)](https://codeforces.com/contest/1867/problem/E1) 293 294 Author: [salyg1n](/profile/salyg1n "Master salyg1n") 295 296 **Tutorial** 297 298 Let's make queries to subarrays starting at positions $1$, $k + 1$, $2k + 1$, $\ldots$ $m \cdot k + 1$, as long as these queries are valid, meaning their right boundary does not exceed $n$. Let's save the $\operatorname{XOR}$ of all the answers to these queries. We will call these queries primary. 299 300 Now, we will shift the last subarray of the query one unit to the right and make a new query, as long as the right boundary does not exceed $n$. We will call these queries secondary. It is claimed that the $\operatorname{XOR}$ of the entire array will be equal to the $\operatorname{XOR}$ of all the queries. Let's prove this. 301 302 Let $i$ be the position at which the first secondary query starts. Notice that after this query, the subarray [$i$; $i + k - 2$] will turn into the subarray [$i + 1$; $i + k - 1$] and reverse. After the next query, the same thing will happen, the subarray will shift one unit to the right and reverse. Therefore, the prefixes of length $k-1$ of each secondary query will be the same, up to the reversal, which does not affect the $\operatorname{XOR}$. Since the number of secondary queries is equal to $n \operatorname{mod} k$, which is an even number, the $\operatorname{XOR}$ of these prefixes will not affect the $\operatorname{XOR}$ of all the secondary queries, which will therefore be equal to the $\operatorname{XOR}$ of the elements [$a_{i + k — 1}$; $a_n$], that is, all the elements that we did not consider in the primary queries. 303 304 The number of primary queries is equal to $\lfloor \frac{n}{k} \rfloor \leq k \leq 50$, since $n \leq k^2 \leq 2500$. 305 306 The number of secondary queries is equal to $n \operatorname{mod} k \lt k \lt = 50$, since $k^2 \leq 2500$. 307 308 The total number of queries does not exceed $100$. 309 310 **Solution** 311 312 ``` 313 #include <iostream> 314 315 using namespace std; 316 317 int ask(int i) { 318 cout << "? " << i << endl; 319 int x; 320 cin >> x; 321 return x; 322 } 323 324 void solve() { 325 int n, k; 326 cin >> n >> k; 327 int res = 0; 328 int i; 329 for (i = 1; i + k - 1 <= n; i += k) 330 res ^= ask(i); 331 for (; i <= n; ++i) 332 res ^= ask(i - k + 1); 333 cout << "! " << res << endl; 334 } 335 336 int main() { 337 int t; 338 cin >> t; 339 while (t--) 340 solve(); 341 return 0; 342 } 343 ``` 344 345 [1867E2-Salyg1n and Array (hard version)](https://codeforces.com/contest/1867/problem/E2) 346 347 Author: [salyg1n](/profile/salyg1n "Master salyg1n") 348 349 **Tutorial** 350 351 Let's make queries to subarrays starting at positions $1$, $k + 1$, $2k + 1$, $\ldots$ $m \cdot k + 1$, such that the size of the uncovered part is greater than $2 \cdot k$ and not greater than $3 \cdot k$. In other words, $2 \cdot k \lt n - (m + 1) \cdot k \le 3 \cdot k$. Let's keep the $\operatorname{XOR}$ of all the answers to these queries. We will call these queries primary. 352 353 Let the size of the remaining (uncovered) part be $x$ ($2 \cdot k \lt x \le 3 \cdot k$). Let's learn how to solve the problem for an array of size $x$ in three queries. 354 355 If $x = 3 \cdot k$, simply make queries to positions $1$, $k + 1$, $2 \cdot k + 1$. 356 357 Otherwise, let $y = x - k$. Note that $y$ is even, since $x$ and $k$ are even. 358 359 Make queries at positions $1$, $1 + \frac{y}{2}$, $1 + y$. 360 361 Note that after this query, the subarray [$1$; $k - \frac{y}{2}$] will turn into the subarray [$y/2 + 1$; $k$] and reverse. After the next query, the same thing will happen, the subarray will shift one unit to the right and reverse. Therefore, the prefixes of length $k - \frac{y}{2}$ for each query are the same, up to the reversal, which does not affect the $\operatorname{XOR}$. Since the number of queries in the second group is $3$, which is an odd number, the $\operatorname{XOR}$ of these prefixes will be taken into account exactly once in the $\operatorname{XOR}$ of all the queries, which will therefore be equal to the $\operatorname{XOR}$ of the elements. 362 363 The number of primary queries does not exceed $\lfloor \frac{n}{k} \rfloor \leq k \leq 50$, since $n \leq k^2 \leq 2500$. 364 365 The total number of queries does not exceed $53$. 366 367 **Solution** 368 369 ``` 370 #include <iostream> 371 372 using namespace std; 373 374 int ask(int i) { 375 cout << "? " << i << endl; 376 int x; 377 cin >> x; 378 return x; 379 } 380 381 void solve() { 382 int n, k; 383 cin >> n >> k; 384 int res = 0; 385 int i; 386 for (i = 1; n - i + 1 >= 2 * k; i += k) 387 res ^= ask(i); 388 if (n - i + 1 == k) { 389 res ^= ask(i); 390 cout << "! " << res << endl; 391 return; 392 } 393 int y = (n - i + 1 - k) / 2; 394 res ^= ask(i); 395 res ^= ask(i + y); 396 res ^= ask(i + 2 * y); 397 cout << "! " << res << endl; 398 } 399 400 int main() { 401 int t; 402 cin >> t; 403 while (t--) 404 solve(); 405 return 0; 406 } 407 ``` 408 409 [1867F-Most Different Tree](https://codeforces.com/contest/1867/problem/F) 410 411 Author: [green_gold_dog](/profile/green_gold_dog "Grandmaster green_gold_dog") 412 413 **Tutorial** 414 415 Here we say that the answer for tree $G'$ is the number of subtrees in $P(G')$ that have an isomorphic subtree in $P(G)$. 416 417 Let's find a tree $T$ of minimum size that has no isomorphic tree in $P(G)$. Let the size of tree $T$ be $x$. Then take a chain of size $n - x$, and let the root of $T$ be the kid of the last vertex on the chain. We say that this is the tree $G'$ we were looking for (with the root of $G'$ being the first vertex of the chain). The number of matching subtrees will be at most $x - 1$, since all subtrees of the vertices on the chain and the subtree $T$ itself will not have isomorphic trees in $P(G)$, because $T$ lies entirely in them, and $T$ has no isomorphic tree in $P(G)$. Therefore, the answer is not greater than $n - (n - x) - 1 = x - 1$. 418 419 Let's prove why the answer cannot be less than $x - 1$: suppose there exists a tree $G*$ for which the answer is less than $x - 1$. Let's find a subtree of minimum size whose size is at least $x$ (it always exists, since we can take the entire tree for example). In this subtree, there are at least $x - 1$ other subtrees, whose sizes are less than $x$ (because in the previous step we chose a subtree of minimum size not less than $x$). And since all trees of size less than $x$ have isomorphic trees in $P(G)$ (by definition $T$ is the tree of minimum size that has no isomorphic tree in $P(G)$ and its size is $x$), the number of matching subtrees in tree $G*$ is at least $x - 1$, which is a contradiction. 420 421 Therefore in our case the answer is $x - 1$. 422 423 Now let's solve the second part of the problem — finding $T$. To do this, let's first find all trees of size 1, then of size 2, then 3, 4 and so on until we find a tree that has no isomorphic subtree in $P(G)$. One can see that if we generate all trees of size up to 15 we will definitely find $T$ there. Within each size, let's number the trees in the order in which we've generated them. To find all trees of size $x$ if we are given all trees of size $x - 1$ and smaller, let's say that the sizes of the children of the root of the tree we generate must not decrease, and if the sizes are the same, their positions in the order must not decrease. Then, we can iterate over the first child, then among the smaller and suitable ones, the second child, then the third, and so on until the total size of the tree becomes exactly $x$. This way, we will enumerate all trees of size $x$ in complexity of their total number (since we will not consider any tree twice and will not consider any extra trees). Let's do this until we find a tree that is not in $P(G)$. 424 425 Hashes can be used to compare trees for isomorphism. For more details, read the [blog post](https://codeforces.com/blog/entry/113465) 426 427 Time Complexity: $O(n \log n)$. 428 429 **Solution** 430 431 ``` 432 #include <bits/stdc++.h> 433 434 using namespace std; 435 436 const int MAXSZ = 15; 437 438 void rec(int ns, int last, vector<int>& now, vector<vector<int>>& aint, vector<int>& col, vector<int>& sz, int& ss, int sns) { 439 if (ss < 0) { 440 return; 441 } 442 if (ns == 0) { 443 col.back()++; 444 aint.push_back(now); 445 ss -= sns; 446 return; 447 } 448 for (int i = min(last, col[ns] - 1); i >= 0; i--) { 449 now.push_back(i); 450 rec(ns - sz[i], i, now, aint, col, sz, ss, sns); 451 now.pop_back(); 452 } 453 } 454 455 void dfs(int v, int p, vector<vector<int>>& arr, vector<int>& num, map<vector<int>, int>& m, vector<int>& sz) { 456 vector<int> now; 457 sz[v] = 1; 458 for (auto i : arr[v]) { 459 if (i != p) { 460 dfs(i, v, arr, num, m, sz); 461 sz[v] += sz[i]; 462 if (sz[v] <= MAXSZ) { 463 now.push_back(num[i]); 464 } 465 } 466 } 467 if (sz[v] > MAXSZ) { 468 num[v] = -1; 469 return; 470 } 471 stable_sort(now.begin(), now.end()); 472 reverse(now.begin(), now.end()); 473 num[v] = m[now] - 1; 474 } 475 476 void dfs2(int x, int p, vector<vector<int>>& aint, vector<int>& ans) { 477 if (p >= 0) { 478 ans.push_back(p); 479 } 480 int now = ans.size(); 481 for (auto i : aint[x]) { 482 dfs2(i, now, aint, ans); 483 } 484 } 485 486 void solve() { 487 int n; 488 cin >> n; 489 vector<vector<int>> aint(1); 490 vector<vector<int>> arr(n); 491 for (int i = 1; i < n; i++) { 492 int a, b; 493 cin >> a >> b; 494 a--; 495 b--; 496 arr[a].push_back(b); 497 arr[b].push_back(a); 498 } 499 map<vector<int>, int> m; 500 vector<int> col(1, 0), sz(1, 1); 501 col.push_back(1); 502 for (int i = 2; i <= MAXSZ; i++) { 503 vector<int> now; 504 col.push_back(col.back()); 505 int ss = n; 506 rec(i - 1, aint.size() - 1, now, aint, col, sz, ss, i); 507 while (sz.size() < col.back()) { 508 sz.push_back(i); 509 } 510 if (ss < 0) { 511 break; 512 } 513 } 514 for (int i = 0; i < col.back(); i++) { 515 m[aint[i]] = i + 1; 516 } 517 vector<int> num(n), szi(n, 1); 518 dfs(0, 0, arr, num, m, szi); 519 set<int> s; 520 for (int i = 0; i < col.back(); i++) { 521 s.insert(i); 522 } 523 for (auto i : num) { 524 s.erase(i); 525 } 526 int x = *s.begin(); 527 vector<int> ans; 528 if (sz[x] > n) { 529 for (int i = 0; i < n; i++) { 530 for (auto j : arr[i]) { 531 if (i < j) { 532 cout << i + 1 << ' ' << j + 1 << '\n'; 533 } 534 } 535 } 536 return; 537 } 538 for (int i = 0; i < n - sz[x] - 1; i++) { 539 ans.push_back(i); 540 } 541 dfs2(x, n - sz[x] - 1, aint, ans); 542 for (int i = 0; i < ans.size(); i++) { 543 cout << ans[i] + 1 << ' ' << i + 2 << '\n'; 544 } 545 } 546 547 int main() { 548 ios_base::sync_with_stdio(false); 549 cin.tie(0); 550 cout.tie(0); 551 int t = 1; 552 //cin >> t; 553 for (int i = 0; i < t; i++) { 554 solve(); 555 } 556 } 557 ```