2108.md (19841B)
1 Source: https://codeforces.com/blog/entry/142512 2 3 #### [2108A - Permutation Warm-Up](/contest/2108/problem/A "Codeforces Round 1022 (Div. 2)") 4 5 Author: [eugenechka.boyko.2_0-0](/profile/eugenechka.boyko.2_0-0 "Expert eugenechka.boyko.2_0-0") 6 7 **Solution** 8 9 Let’s start with $p = [1, 2, 3, …, n]$. For this $p$, $f(p) = 0$. 10 11 Let’s move $n$ to the beginning one position at a time. It’s easy to see that we increase the answer by $2$ at each step. 12 13 Now, let’s move $n - 1$ to position $2$, then $n - 2$ to position $3$, and so on, until we reach $p = [n, n - 1, …, 2, 1]$. 14 For this $p$, $f(p) = \lfloor \frac{n^2}{2} \rfloor$. 15 16 While doing this, we obtained every even value from $0$ to $\lfloor \frac{n^2}{2} \rfloor$, since we were adding $+2$ at each step. 17 18 Let’s prove that we can’t get any other values. 19 20 First of all, it’s easy to see that we can’t obtain a value less than $0$ or greater than $\lfloor \frac{n^2}{2} \rfloor$. 21 22 Second, we can only obtain even values, because each swap changes the answer by an even number. 23 24 So the answer is $\lfloor \frac{n^2}{4} \rfloor + 1$ 25 26 Time complexity : $\text{O}(1)$. 27 28 **Code** 29 30 ``` 31 #include <iostream> 32 #include <vector> 33 using namespace std; 34 typedef long long int ll; 35 #define SPEEDY std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); 36 #define forn(i, n) for (ll i = 0; i < ll(n); ++i) 37 38 void solution(){ 39 ll n;cin>>n; 40 ll k=n/2; 41 if (n%2){cout<<k*(k+1)+1;return;} 42 cout<<k*k+1; 43 } 44 45 int main() { 46 SPEEDY; 47 int t; cin>>t; 48 while (t--){ 49 solution(); 50 cout << '\n'; 51 } return 0; 52 } 53 ``` 54 55 #### [2108B - SUMdamental Decomposition](/contest/2108/problem/B "Codeforces Round 1022 (Div. 2)") 56 57 Author: [eugenechka.boyko.2_0-0](/profile/eugenechka.boyko.2_0-0 "Expert eugenechka.boyko.2_0-0") 58 59 **Solution** 60 61 Let $x \gt 1$, and let $c$ denote the number of 1-bits in its binary representation. Clearly, when $n \le c$, it is optimal to simply distribute distinct powers of two across the elements of the array, resulting in the minimum achievable sum of $x$. If, however, $n \gt c$, then it is obviously beneficial to add only ones to the extra $n - c$ elements. In the case where $n - c$ is odd, we will also need to add one more one to one of the $c$ blocks with powers of two so that the $\text{XOR}$ of all ones equals $x$ $\text{mod}$ $2$. 62 63 If $x = 1$, then for odd $n$ we can clearly just fill all array elements with ones. Otherwise, we need to use the pair $[2, 3]$, whose $\text{XOR}$ is $1$, resulting in the minimum score of $n + 3$. 64 65 In the remaining case of $x = 0$, the situation is nearly identical to the previous one, with the exception that no valid example exists for $n = 1$ (this is the only case with an answer of $-1$). So for even $n$, the answer is simply $n$, and otherwise it’s $n + 3$ (since we use the triple $1 \oplus 2 \oplus 3 = 0$). 66 67 The time complexity is $\text{O}(1)$ per test. 68 69 **Code** 70 71 ``` 72 #include <bits/stdc++.h> 73 using namespace std; 74 typedef long long int ll; 75 76 void solution(){ 77 int n,x;cin>>n>>x; 78 int bits=__builtin_popcountll(x); 79 if (n<=bits){cout<<x;return;} 80 if ((n-bits)%2==0)cout<<x+n-bits; 81 else{ 82 if (x>1){cout<<x+n-bits+1;return;} 83 if (x==1){cout<<n+3;return;} 84 else{ 85 if (n==1){cout<<-1;return;} 86 else cout<<n+3; 87 } 88 } 89 } 90 91 int main() { 92 ios::sync_with_stdio(false); 93 cin.tie(nullptr); 94 cout.tie(nullptr); 95 int t=1; 96 cin>>t; 97 while (t--){ 98 solution(); 99 cout << '\n'; 100 } return 0; 101 } 102 ``` 103 104 #### [2108C - Neo's Escape](/contest/2108/problem/C "Codeforces Round 1022 (Div. 2)") 105 106 Author: [suprend](/profile/suprend "Expert suprend") 107 108 **Solution** 109 110 Note that consecutive buttons with the same weight do not affect the result, so we will keep only one of them in such sequences. 111 112 In the resulting array, we find peaks (local maxima — elements that are strictly greater than both of their neighbors). The number of such peaks is the answer, because: 113 114 — Each peak is separated from others by smaller elements. Therefore, the only way to reach a peak is by creating a clone there. 115 116 — If a button was visited, we can return to it. 117 118 — Any element other than a peak can be reached from a larger neighbor, since we have already visited it. Thus, creating clones in all other elements is not necessary. 119 120 Complexity: $\text{O}(n)$ 121 122 **Code** 123 124 ``` 125 #include <iostream> 126 #include <vector> 127 128 using namespace std; 129 130 int main() { 131 int tt = 1; 132 cin >> tt; 133 while(tt--){ 134 int n; cin >> n; 135 vector<int> a; 136 a.push_back(-1e9); 137 for (int i = 0; i < n; i++){ 138 int x; cin >> x; 139 if (a.back() == x); 140 else a.push_back(x); 141 } 142 a.push_back(-1e9); 143 144 int ans = 0; 145 for (int i = 1; i < a.size() - 1; i++) 146 if (a[i - 1] < a[i] && a[i] > a[i + 1]) ans++; 147 148 cout << ans << endl; 149 } 150 } 151 ``` 152 153 #### [2108D - Needle in a Numstack](/contest/2108/problem/D "Codeforces Round 1022 (Div. 2)") 154 155 Author: [m3tr0](/profile/m3tr0 "Expert m3tr0") 156 157 **Solution** 158 159 Let $k = 4$ and the following array is guessed: 160 161 [ 2 4 3 1 2 4 3 1 2 1 3 2 4 1 3 2 4 1 ] 162 163 For clarity, let's divide it into groups of $k$ elements: 164 165 [ 2 4 3 1 ] [ 2 4 3 1 ] [ 2 1 3 2 ] [ 4 1 3 2 ] [ 4 1 ] 166 167 By statement, the lengths of the left and right sides are at least $k$. Let's request the left $k$ and right $k$ elements. We will mark all the elements of the left array in red, and all the elements of the right array in blue: 168 169 [ 2 4 3 1 ] [ 2 4 3 1 ] [ 2 1 3 2 ] [ 4 1 3 2 ] [ 4 1 ] 170 171 Let's add two numbers to our array on the right (for clarity of permutations): 172 173 [ 2 4 3 1 ] [ 2 4 3 1 ] [ 2 1 3 2 ] [ 4 1 3 2 ] [ 4 1 3 2 ] 174 175 We got the permutations in a "normalized" form: $[2, 4, 3, 1]$ and $[4, 1, 3, 2]$. Let's take any position where the elements in the permutations differ. Let it be the second position. Note all the elements at the selected positions in the guessed array: 176 177 [ 2 4 3 1 ] [ 2 4 3 1 ] [ 2 1 3 2 ] [ 4 1 3 2 ] [ 4 1 3 2 ] 178 179 Among them, we find boundary elements via **binary search** for $\log\frac{n}{k}$ queries: 180 181 [ 2 4 3 1 ] [ 2 4 3 1 ] [ 2 1 3 2 ] [ 4 1 3 2 ] [ 4 1 3 2 ] 182 183 Next, consider the segment between these boundary elements: 184 185 [ 2 4 3 1 ] [ 2 4 3 1 ] [ 2 1 3 2 ] [ 4 1 3 2 ] [ 4 1 3 2 ] 186 187 We are not interested in positions that match in both permutations (in our case, this is only the third position). Let's discard the elements in these positions: 188 189 [ 2 4 3 1 ] [ 2 4 3 1 ] [ 2 1 3 2 ] [ 4 1 3 2 ] [ 4 1 3 2 ] 190 191 Using binary search, we find the boundary elements for $\log k$ queries: 192 193 [ 2 4 3 1 ] [ 2 4 3 1 ] [ 2 1 3 2 ] [ 4 1 3 2 ] [ 4 1 3 2 ] 194 195 If there are "no-man's land" between the boundary elements, then there is no single solution and we output $-1$. In our case, there are no such elements, the problem is solved: 196 197 [ 2 4 3 1 ] [ 2 4 3 1 ] [ 2 1 3 2 ] [ 4 1 3 2 ] [ 4 1 ] 198 199 Total complexity: $2k + \log\frac{n}{k} + \log k$ queries. 200 201 **Code** 202 203 ``` 204 #include <cstdio> 205 #include <cstdlib> 206 #define MIN(X, Y) (((X) < (Y)) ? (X) : (Y)) 207 #define MAX(X, Y) (((X) > (Y)) ? (X) : (Y)) 208 typedef long long l; 209 210 l a[55], b[55], ui[55]; 211 212 l ask(l v) { 213 printf("? %lld\n", v + 1); 214 fflush(stdout); 215 l t; scanf("%lld", &t); 216 return t; 217 } 218 219 void noans() { 220 printf("! -1\n"); 221 fflush(stdout); 222 } 223 224 void ans(l a, l b) { 225 printf("! %lld %lld\n", a, b); 226 fflush(stdout); 227 } 228 229 void solve() { 230 l n, k; scanf("%lld %lld", &n, &k); 231 232 for (l i = 0; i < k; ++i) a[i] = ask(i); 233 for (l i = n - k; i < n; ++i) b[i % k] = ask(i); 234 235 l uc = 0; 236 for (l i = 0; i < k; ++i) if (a[i] != b[i]) ui[uc++] = i; 237 238 if (!uc) { 239 if (n == k * 2) ans(k, k); 240 else noans(); 241 return; 242 } 243 244 l le = ui[0], ri = ui[0] + (n - 1) / k * k; 245 while (le + k != ri) { 246 l mid = le + (ri - le) / k / 2 * k; 247 if (ask(mid) == a[ui[0]]) le = mid; 248 else ri = mid; 249 } 250 251 l lee = 0, rii = uc; 252 while (lee + 1 != rii) { 253 l mid = (lee + rii) / 2; 254 if (ask(le - ui[0] + ui[mid]) == a[ui[mid]]) lee = mid; 255 else rii = mid; 256 } 257 258 l pos1 = MAX(le - ui[0] + ui[lee], k - 1); 259 l pos2 = MIN(le - ui[0] + ((rii == uc) ? (ui[0] + k) : ui[rii]), n - k); 260 261 if (pos1 + 1 != pos2) { noans(); return; } 262 ans(pos2, n - pos2); 263 } 264 265 int main() { 266 l t; scanf("%lld", &t); 267 while (t--) solve(); 268 } 269 ``` 270 271 #### [2108E - Spruce Dispute](/contest/2108/problem/E "Codeforces Round 1022 (Div. 2)") 272 273 Author: [eugenechka.boyko.2_0-0](/profile/eugenechka.boyko.2_0-0 "Expert eugenechka.boyko.2_0-0") 274 275 **Solution** 276 277 Let’s assume we have already removed one of the edges from the original tree. Then, we are left with a tree containing an even number of vertices, namely $n - 1$. 278 Note that the maximum possible sum of distances between same-colored balls in this tree will be achieved if, for every edge, all vertices in its smaller subtree are of different colors. In that case, the edge will contribute the maximum possible number of times to the answer — specifically, $\min(a, b)$, where $a$ and $b$ are the sizes of the subtrees connected by this edge (since, obviously, no more paths can pass through this edge). 279 Great — now let’s root our tree at its centroid, which is a vertex that splits the tree into subtrees whose sizes do not exceed half of the total size. It can be proven that such a vertex always exists in any tree (and if there are two such vertices, we can pick either). 280 Now, let’s divide all vertices into groups based on which child subtree of the centroid they belong to, adding the centroid itself to the smallest group. Notice that the sizes of all groups still do not exceed $\frac{n - 1}{2}$. Therefore, we can pair up the vertices in such a way that each pair contains vertices from different groups. This can be done greedily using a heap in $O(n \log n)$, or by running DFS from the centroid and coloring vertices modulo $\frac{n - 1}{2}$ (clearly, with this method, no group will have two vertices of the same color), which has complexity $O(n)$. 281 Thus, we are left to determine which edge we should remove so that the total sum of the minimal subtree sizes across all edges in the original tree decreases as little as possible. Note that, since initially the tree has an odd number of vertices, its centroid is uniquely defined and will not change no matter which edge we remove. At the same time, since all paths pass through the centroid, the total sum of their lengths can be rewritten as the sum of distances to the centroid. 282 Now, let’s make two observations: 283 284 1. It is more beneficial to remove a leaf than any other type of vertex. 285 2. Among all leaves, it is best to remove the one closest to the centroid. 286 287 The second observation follows directly from the first and the earlier remark, so we only need to justify the first one. But this is fairly obvious: when we remove an edge, besides subtracting the depth of its nearest vertex, we also decrease the depths of all vertices in its subtree by one. Therefore, it will always be better to remove deeper edges rather than shallower ones. 288 As a result, after finding the centroid in $O(n)$, we get an overall complexity of $O(n \log n)$ (if we use a heap) or $O(n)$. 289 290 **Code** 291 292 ``` 293 #include <cstdio> 294 #include <vector> 295 296 #define S 200005 297 298 using namespace std; 299 typedef long long l; 300 301 l coloring[S], centroid, best, best_dist, n, color; 302 vector<vector<l>> g; 303 304 l search_centroid(l u, l from) { 305 l sum = 0; 306 bool f = true; 307 for (l v : g[u]) if (v != from) { 308 l t = search_centroid(v, u); 309 if (t > n / 2) f = false; 310 sum += t; 311 } 312 313 if (f && n - 1 - sum <= n / 2) centroid = u; 314 return sum + 1; 315 } 316 317 void make_coloring(l u, l from, l dist) { 318 coloring[u] = (color++) % (n / 2) + 1; 319 if (g[u].size() == 1 && dist < best_dist) { 320 best_dist = dist; 321 best = u; 322 } 323 for (l v : g[u]) if (v != from) 324 make_coloring(v, u, dist + 1); 325 } 326 327 void solve() { 328 centroid = -1, best_dist = S, color = 0; 329 scanf("%lld", &n); 330 g.assign(n, vector<l>()); 331 for (l i = 0; i < n - 1; ++i) { 332 l u, v; scanf("%lld %lld", &u, &v); --u, --v; 333 g[u].push_back(v); g[v].push_back(u); 334 } 335 336 search_centroid(1543 % n, -1); 337 make_coloring(centroid, -1, 0); 338 339 l bbest = max(best, g[best][0]); 340 coloring[centroid] = coloring[bbest]; 341 coloring[bbest] = 0; 342 343 printf("%lld %lld\n", best + 1, g[best][0] + 1); 344 for (l i = 0; i < n; ++i) { 345 if (i) printf(" "); 346 printf("%lld", coloring[i]); 347 } 348 printf("\n"); 349 } 350 351 int main() { 352 l tc; scanf("%lld", &tc); 353 while (tc--) solve(); 354 } 355 ``` 356 357 #### [2108F - Fallen Towers](/contest/2108/problem/F "Codeforces Round 1022 (Div. 2)") 358 359 Author: [m3tr0](/profile/m3tr0 "Expert m3tr0") 360 361 **Solution** 362 363 It can be shown that for any array $ A $ obtained after collapsing all $ n $ towers, we can also obtain any other array $ B $ whose elements do not exceed the elements of $ A $. A strict formal proof is provided in the spoiler below; here is a brief explanation. Suppose $ k $ blocks fell onto the $ i $-th tower over the entire process. Then, for its height in the final array to be $ A_i $, $ A_i $ blocks must have fallen after its collapse, while the remaining $ k - A_i $ blocks fell before. Thus, we can always rearrange the order in which the towers collapse so that its height becomes $ B_i \leq A_i $. In other words, we ensure that $ B_i $ blocks fall onto the $ i $-th tower after its collapse, and $ k - B_i $ fall before. 364 365 From this claim about the possibility of obtaining a smaller array, two facts follow: 366 367 1. For any answer $\text{MEX} = x$, we can also obtain the answer $ x - 1 $. This means we can apply **binary search on the answer**. 368 2. For any answer $\text{MEX} = x$, we can achieve it in the form $[0, 0, 0, 0, \ldots, 1, 2, 3, \ldots, x - 1]$. Thus, at each iteration of the binary search, we need to check the possibility of obtaining such an array. To do this, we traverse the towers from left to right, tracking the number of cubes that fall onto each tower at some point and collapsing each tower after the required number of cubes have fallen onto it. The most efficient way to track the number of cubes is using the scanline method. 369 370 In total, there are $\text{O}(\log n)$ iterations in the binary search over the answer and $\text{O}(n)$ operations per iteration. 371 372 The final complexity is $\text{O}(n \log n)$. 373 374 **Formal proof** 375 376 Let the array $a$ of length $n$ be some input data for the problem. 377 378 Let $r$ and $r'$ be arrays of length $n$ such that $\forall i : 0 \leq r'_i \leq r_i$. 379 380 **Assertion 1**: Suppose there exists a permutation $p$ such that the tower with index $i$ collapses $p_i$-th in order, resulting in the array $r$. Then, there exists a permutation $p'$ such that the tower with index $i$ collapses $p'_i$-th in order, resulting in the array $r'$. 381 382 $\square$ 383 384 Let $s_i$ be the total number of towers that ever fell onto position $i$ when collapsing the towers in the order $p$. Note that out of these, $r_i$ towers were collapsed later than the $i$-th, and the rest were collapsed earlier. The height of the $i$-th tower at the moment of its collapse is $a_i + (s_i - r_i)$. 385 386 **Inductive hypothesis**: There exists a permutation $p^{(k)}$ of numbers from $1$ to $k \leq n$ such that if the $i$-th tower is collapsed $p^{(k)}_i$-th in order, then: 387 388 1. The resulting height at the $i$-th position will be $r'_i$. 389 2. The number (denoted as $s^{(k)}_i$) of towers that fell onto position $i$ when collapsing the towers in the order $p^{(k)}$ is greater than or equal to $s_i$. 390 391 **Base case**: The permutation $p^{(1)} = [1]$. After collapsing, the tower's height becomes $0$, so $r'_1 = r_1 = 0$ in any resulting array. $s^{(1)}_1 = s_1 = 0$. 392 393 **Inductive step**: Suppose the permutation $p^{(k - 1)}$ exists. We prove the existence of $p^{(k)}$. 394 395 $\forall i \leq k - 1$, the height of the $i$-th tower at the moment of collapse under the order $p^{(k - 1)}$ is no less than under the order $p$: 396 397 $ (s^{(k - 1)}_i \geq s_i \land r'_i \leq r_i) ~~~ \Longrightarrow ~~~ a_i + (s^{(k - 1)}_i - r'_i) \geq a_i + (s_i - r_i) $ 398 399 From this, it follows that when collapsing in the order $p^{(k - 1)}$, at least $s_k$ towers will fall onto position $k$ (let their count be $x \geq s_k \geq r'_k$). This is because the heights at the moment of collapse for all towers $i \lt k$ have either remained the same or increased. 400 401 If $x \gt r'_k$, let tower $j$ be the $(x - r'_k)$-th tower among those that fell onto position $k$. Then, collapse tower $k$ immediately after tower $j$. If $x = r'_k$, collapse tower $k$ first. In both cases, after collapsing $k$, $r'_k$ towers will fall onto it, and its height will become $r'_k$. 402 403 Formally, for $x \gt r'_k$, the permutation $p^{(k)}$ is constructed as follows: 404 405 1. $\forall i \lt k : p^{(k - 1)}_i \leq p^{(k - 1)}_j \Rightarrow p^{(k)}_i = p^{(k - 1)}_i$ 406 2. $p^{(k)}_k = p^{(k - 1)}_j + 1$ 407 3. $\forall i \lt k : p^{(k - 1)}_i \gt p^{(k - 1)}_j \Rightarrow p^{(k)}_i = p^{(k - 1)}_i + 1$ 408 409 For $x = r'_k$: 410 411 1. $p^{(k)}_k = 1$ 412 2. $\forall i \lt k : p^{(k)}_i = p^{(k - 1)}_i + 1$ 413 414 The array $s^{(k)}$ is constructed as $\forall i \lt k : s^{(k)}_i = s^{(k - 1)}_i$ and $s^{(k)}_k = x$. 415 416 **The induction is proven**. Thus, we set $p' = p^{(n)}$, and the assertion is proven. 417 418 $\blacksquare$ 419 420 **Corollary 1**: If we can obtain $\text{MEX}(r) \gt 0$ as the answer to the problem for the resulting array $r$, then we can also obtain $\text{MEX}(r) - 1$ as the answer to the problem. 421 422 $\square$ 423 424 Set $r'_i = \max(0, r_i - 1)$. Then, by Assertion 1, $r'$ can be obtained as the resulting array. $\text{MEX}(r') = \text{MEX}(r) - 1$. 425 426 $\blacksquare$ 427 428 **Corollary 2**: If we can obtain $\text{MEX}(r)$ as the answer to the problem for the resulting array $r$, then we can obtain $\text{MEX}(r') = \text{MEX}(r)$ for the resulting array $r'$, where $r'_i = \max(0, (\text{MEX}(r) - 1) - (n - i))$. 429 430 $\square$ 431 432 By Assertion 1, $r'$ can be obtained as the resulting array. 433 434 $\blacksquare$ 435 436 We can perform binary search on the answer (from Corollary 1), and at each iteration, when checking the answer $x$, verify whether we can obtain the resulting array $r$ of the form $r_i = \max(0, (x - 1) - (n - i))$ (from Corollary 2). 437 438 **Code** 439 440 ``` 441 #include <cstdio> 442 #include <algorithm> 443 #include <cstring> 444 445 #define S 100005 446 447 typedef long long l; 448 449 l a[S], d[S], n; 450 451 bool check(l ans) { 452 memset(d, 0, sizeof(l) * n); 453 l acc = 0; 454 455 for (l i = 0; i < n; ++i) { 456 acc -= d[i]; 457 458 l need = std::max(0LL, i - (n - ans)); 459 if (acc < need) return false; 460 461 l end = i + a[i] + (acc++) - need + 1; 462 if (end < n) ++d[end]; 463 } 464 465 return true; 466 } 467 468 void solve() { 469 scanf("%lld", &n); 470 for (l i = 0; i < n; ++i) scanf("%lld", &a[i]); 471 472 l le = 1, ri = n + 1, mid; 473 while (ri - le > 1) { 474 mid = (le + ri) / 2; 475 if (check(mid)) le = mid; 476 else ri = mid; 477 } 478 479 printf("%lld\n", le); 480 } 481 482 int main() { 483 l tc; scanf("%lld", &tc); 484 while (tc--) solve(); 485 } 486 ```