2184.md (15312B)
1 Source: https://codeforces.com/blog/entry/150033 2 3 We hope you enjoyed the contest! Thank you for participating! This is our third official round on Codeforces, so we would be happy to hear your feedback in the comments and in the mini-survey below. 4 5 **How did you like the contest?** 6 7 * Excellent: 8 * Good: 9 * Average: 10 * Bad: 11 * Terrible: 12 13 **Which problems did you like (you can choose multiple)?** 14 15 * A: 16 * B: 17 * C: 18 * D: 19 * E: 20 * F: 21 * G: 22 23 **Which problems did you not like (you can choose multiple)?** 24 25 * A: 26 * B: 27 * C: 28 * D: 29 * E: 30 * F: 31 * G: 32 33 [2184A - Social Experiment](/contest/2184/problem/A "Codeforces Round 1072 (Div. 3)") 34 35 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [fstilus](/profile/fstilus "Expert fstilus") 36 37 **Hint** 38 39 How many people can be in one civilization? 40 41 **Answer** 42 43 Any non-negative number of people, except for the number $1$. 44 45 **Editorial** 46 47 Tutorial is loading... 48 49 **Solution** 50 51 ``` 52 #include <bits/stdc++.h> 53 54 using namespace std; 55 56 int main() { 57 int t; 58 cin >> t; 59 60 while (t--) { 61 int n; 62 cin >> n; 63 if (n == 2) cout << "2\n"; 64 if (n == 3) cout << "3\n"; 65 if (n >= 4) cout << n % 2 << '\n'; 66 } 67 68 return 0; 69 } 70 ``` 71 72 [2184B - Hourglass](/contest/2184/problem/B "Codeforces Round 1072 (Div. 3)") 73 74 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [fstilus](/profile/fstilus "Expert fstilus") 75 76 **Hint** 77 78 How many minutes of sand will remain in the upper half of the hourglass immediately after the second flip? 79 80 **Answer** 81 82 $s$ minutes. 83 84 **Editorial** 85 86 Tutorial is loading... 87 88 **Solution** 89 90 ``` 91 #include <bits/stdc++.h> 92 93 using namespace std; 94 95 int main() { 96 int t; 97 cin >> t; 98 99 while (t--) { 100 int s, k, m; 101 cin >> s >> k >> m; 102 103 if (s <= k) cout << max(0, s - m % k) << '\n'; 104 else cout << (((m % (2 * k)) < k) ? s - m % k : k - m % k) << '\n'; 105 } 106 107 return 0; 108 } 109 ``` 110 111 [2184C - Huge Pile](/contest/2184/problem/C "Codeforces Round 1072 (Div. 3)") 112 113 Idea: [Friendiks](/profile/Friendiks "Grandmaster Friendiks"); developer: [fstilus](/profile/fstilus "Expert fstilus") 114 115 **Hint 1** 116 117 Why is brute force ineffective? How can it be improved? 118 119 **Answer** 120 121 Because the same numbers are visited multiple times. 122 123 **Hint 2** 124 125 How many distinct values can be obtained starting from the number $n$? 126 127 **Answer** 128 129 $O(\log n)$. 130 131 **Editorial** 132 133 Tutorial is loading... 134 135 **Solution** 136 137 ``` 138 #include <bits/stdc++.h> 139 140 using namespace std; 141 142 int main() { 143 int t; 144 cin >> t; 145 146 while (t--) { 147 int n, k; 148 cin >> n >> k; 149 150 int l = n, r = n; 151 int cnt = 0; 152 while (r != 1) { 153 if (l <= k && k <= r) break; 154 l = l / 2; 155 r = r / 2 + r % 2; 156 cnt++; 157 } 158 if (l <= k && k <= r) cout << cnt << '\n'; 159 else cout << -1 << '\n'; 160 } 161 162 return 0; 163 } 164 ``` 165 166 [2184D - Unfair Game](/contest/2184/problem/D "Codeforces Round 1072 (Div. 3)") 167 168 Idea: [Friendiks](/profile/Friendiks "Grandmaster Friendiks"); developer: [Friendiks](/profile/Friendiks "Grandmaster Friendiks") 169 170 **Hint 1** 171 172 Alice's winning strategy is related to bits. 173 174 **Hint 2** 175 176 Alice's optimal number of moves depends only on the most significant bit and the number of set bits. 177 178 **Hint 3** 179 180 The number $n$ is a power of two, which means if you subtract $1$, any subset of bits of $n-1$ will not exceed $n-1$. 181 182 **Editorial** 183 184 Tutorial is loading... 185 186 **Solution** 187 188 ``` 189 #include <bits/stdc++.h> 190 191 using namespace std; 192 193 int c_n_k[31][31]; 194 195 int main() { 196 for (int i = 0; i < 30; ++i) { 197 for (int j = 0; j < 30; ++j) { 198 if (i < j) c_n_k[i][j] = 0; 199 else if (j == 0) c_n_k[i][j] = 1; 200 else c_n_k[i][j] = c_n_k[i - 1][j] + c_n_k[i - 1][j - 1]; 201 } 202 } 203 204 int t; 205 cin >> t; 206 207 while (t--) { 208 int n, k; 209 cin >> n >> k; 210 211 int d = 0; 212 while (n % 2 == 0) { 213 n /= 2; 214 ++d; 215 } 216 217 int ans = 0; 218 for (int max_bit = 0; max_bit < d; ++max_bit) { 219 for (int cnt_bit = 1; cnt_bit <= max_bit + 1; ++cnt_bit) { 220 if (max_bit + cnt_bit <= k) continue; 221 ans += c_n_k[max_bit][cnt_bit - 1]; 222 } 223 } 224 225 if (d + 1 > k) ++ans; 226 cout << ans << "\n"; 227 } 228 229 return 0; 230 } 231 ``` 232 233 **Bonus** 234 235 Solve the problem when $n$ is any integer from $1$ to $10^9$, not necessarily a power of two. 236 237 [2184E - Exquisite Array](/contest/2184/problem/E "Codeforces Round 1072 (Div. 3)") 238 239 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [fstilus](/profile/fstilus "Expert fstilus") 240 241 **Hint 1** 242 243 If some array is $k$-exquisite, then any of its subsegments of length at least $2$ is also $k$-exquisite. 244 245 **Hint 2** 246 247 If $k_1 \gt k_2$ and some array is $k_1$-exquisite, then it is also $k_2$-exquisite. 248 249 **Hint 3** 250 251 If some array of length $m$ is $k$-exquisite, how many $k$-exquisite subsegments does it have? 252 253 **Answer** 254 255 $\frac{m \cdot (m - 1)}{2}$. 256 257 **Hint 4** 258 259 For a fixed $k$, come up with a way to divide the entire original permutation into segments, each of which is either $k$-exquisite or of length $1$, so that you can use the formula from the previous hint. 260 261 **Hint 5** 262 263 How to transition from the segmentation for $k+1$ to the segmentation for $k$? 264 265 **Answer** 266 267 You need to find all positions where the difference between the elements of the permutation equals $k$, and merge the corresponding segments. 268 269 **Hint 6** 270 271 Determine how the answer changes with each merging of two segments. 272 273 **Editorial** 274 275 Tutorial is loading... 276 277 **Solution** 278 279 ``` 280 #include <bits/stdc++.h> 281 282 using namespace std; 283 284 vector <int> parent; 285 vector <int> rnk; 286 vector <int> sz; 287 288 void make_set(int v) { 289 parent[v] = v; 290 rnk[v] = 0; 291 sz[v] = 1; 292 } 293 294 int find_set(int v) { 295 if (v == parent[v]) 296 return v; 297 return parent[v] = find_set(parent[v]); 298 } 299 300 void union_sets(int a, int b) { 301 a = find_set(a); 302 b = find_set(b); 303 if (a != b) { 304 if (rnk[a] < rnk[b]) 305 swap (a, b); 306 parent[b] = a; 307 if (rnk[a] == rnk[b]) 308 ++rnk[a]; 309 sz[a] += sz[b]; 310 } 311 } 312 313 long long cnt(int x) { 314 x = find_set(x); 315 return (long long)sz[x] * (sz[x] - 1) / 2; 316 } 317 318 int main() { 319 int t; 320 cin >> t; 321 322 while (t--) { 323 int n; 324 cin >> n; 325 326 map <int, vector <int>> m; 327 int pr; 328 for (int i = 0; i < n; i++) { 329 int a; 330 cin >> a; 331 if (i > 0) 332 m[abs(a - pr)].push_back(i); 333 pr = a; 334 } 335 336 parent.resize(n); 337 rnk.resize(n); 338 sz.resize(n); 339 for (int i = 0; i < n; i++) make_set(i); 340 341 vector <long long> ans; 342 long long cur = 0; 343 for (int i = n - 1; i > 0; i--) { 344 for (auto y : m[i]) { 345 cur -= cnt(y); 346 cur -= cnt(y - 1); 347 union_sets(y, y - 1); 348 cur += cnt(y); 349 } 350 ans.push_back(cur); 351 } 352 353 reverse(ans.begin(), ans.end()); 354 for (auto x : ans) cout << x << ' '; 355 cout << '\n'; 356 357 parent.clear(); 358 rnk.clear(); 359 sz.clear(); 360 } 361 362 return 0; 363 } 364 ``` 365 366 [2184F - Cherry Tree](/contest/2184/problem/F "Codeforces Round 1072 (Div. 3)") 367 368 Idea: [gravitsapa](/profile/gravitsapa "International Master gravitsapa"); developer: [gravitsapa](/profile/gravitsapa "International Master gravitsapa") 369 370 **Hints for the first method** 371 372 **Hint 1** 373 374 Come up with a dynamic programming array $dp[u][k]$ with $O(n^2)$ states, where $u$ is the vertex number, $k$ is an additional parameter, and $dp[u][k]$ indicates whether it is possible to collect all the cherries in the subtree of vertex $u$ given that the additional parameter equals $k$. 375 376 **Answer** 377 378 You can use an additional parameter equal to the number of vertices in the subtree of vertex $u$ that were shaken. 379 380 **Hint 2** 381 382 The parameter $k$ should be considered modulo $3$. Thus, the number of states in the dynamic programming becomes $O(n)$. 383 384 **Hint 3** 385 386 Where will the answer to the problem be located? 387 388 **Answer** 389 390 The answer to the problem is located in $dp[1][0]$. 391 392 **Hint 4** 393 394 What will be the base case for the dynamic programming? 395 396 **Answer** 397 398 If vertex $u$ is a leaf, then $dp[u][0] = False, dp[u][1] = True, dp[u][2] = False$. 399 400 **Hint 5** 401 402 To recalculate the dynamic programming $dp[u]$, two cases need to be considered: whether vertex $u$ was shaken or not. If vertex $u$ was shaken, then it is obviously the only vertex in the entire subtree that was shaken. 403 404 **Hint 6** 405 406 If vertex $u$ was not shaken, then it is necessary to collect cherries in each of its children independently. The information on how this can be done for child $v$ is stored in $dp[v]$. 407 408 **Hint 7** 409 410 To recalculate $dp[u]$ through its children, dynamic programming needs to be used again. 411 412 **Hints for the second method** 413 414 **Hint 1** 415 416 Initially, we will only shake the root vertex. Then we will take some vertex that needs to be shaken and replace it with its children. This way, we can obtain any correct solution. 417 418 **Hint 2** 419 420 During this process, the number of selected vertices changes depending on the number of children of the vertex being replaced. Only the number of children modulo $3$ matters. 421 422 **Hint 3** 423 424 For each vertex that is not a leaf, we can record the number of its children modulo $3$ and find a pattern between the answer and these numbers. 425 426 **Editorial** 427 428 Tutorial is loading... 429 430 **Solution 1** 431 432 ``` 433 #include <bits/stdc++.h> 434 435 using namespace std; 436 437 const int MAXN = 200001; 438 439 int n; 440 vector <int> graph[MAXN]; 441 vector <bool> dp[MAXN]; 442 443 void merge_dp(vector <bool>& lhs, vector <bool>& rhs, vector <bool>& result) { 444 for (int i = 0; i < 3; ++i) { 445 if (!lhs[i]) continue; 446 for (int j = 0; j < 3; ++j) { 447 if (!rhs[j]) continue; 448 result[(i + j) % 3] = true; 449 } 450 } 451 } 452 453 void dfs(int u, int p) { 454 vector <int> child; 455 456 for (auto v : graph[u]) if (v != p) { 457 dfs(v, u); 458 child.push_back(v); 459 } 460 461 dp[u].resize(3); 462 463 if (!child.empty()) { 464 dp[u][0] = true; 465 for (auto v : child) { 466 vector <bool> result(3, false); 467 468 merge_dp(dp[u], dp[v], result); 469 dp[u] = result; 470 } 471 } 472 473 dp[u][1] = true; 474 } 475 476 signed main() { 477 ios::sync_with_stdio(false); 478 cin.tie(0); 479 480 int t; 481 cin >> t; 482 while (t--) { 483 cin >> n; 484 for (int i = 1; i <= n; ++i) { 485 graph[i].clear(); 486 dp[i].clear(); 487 } 488 for (int i = 0; i < n - 1; ++i) { 489 int u, v; 490 cin >> u >> v; 491 graph[u].push_back(v); 492 graph[v].push_back(u); 493 } 494 495 dfs(1, -1); 496 497 cout << (dp[1][0] ? "YES" : "NO") << '\n'; 498 } 499 500 return 0; 501 } 502 ``` 503 504 **Solution 2** 505 506 ``` 507 #include <bits/stdc++.h> 508 509 using namespace std; 510 511 const int MAXN = 200001; 512 513 int n; 514 vector <int> graph[MAXN]; 515 bool ans; 516 517 int dfs(int u, int p) { 518 vector <int> child; 519 int cnt = 0; 520 521 for (auto v : graph[u]) if (v != p) { 522 cnt++; 523 auto t = dfs(v, u); 524 if (t != 0) { 525 child.push_back(t); 526 } 527 } 528 529 if (child.size() > 1) { 530 ans = true; 531 return 0; 532 } 533 534 int type = cnt == 0 ? 0 : (cnt + 2) % 3; 535 vector <int> ord; 536 if (type) { 537 ord.push_back(type); 538 } 539 if (!child.empty()) { 540 ord.push_back(child[0]); 541 } 542 if (ord.size() == 2 && ord[0] + ord[1] != 3) { 543 ans = true; 544 return 0; 545 } 546 if (ord.size() >= 1) return ord[0]; 547 return 0; 548 } 549 550 signed main() { 551 ios::sync_with_stdio(false); 552 cin.tie(0); 553 554 int t; 555 cin >> t; 556 557 while (t--) { 558 cin >> n; 559 for (int i = 1; i <= n; ++i) { 560 graph[i].clear(); 561 } 562 563 for (int i = 0; i < n - 1; ++i) { 564 int u, v; 565 cin >> u >> v; 566 graph[u].push_back(v); 567 graph[v].push_back(u); 568 } 569 570 ans = false; 571 int res = dfs(1, 1); 572 if (res == 2) { 573 ans = true; 574 } 575 576 cout << (ans ? "YES" : "NO") << '\n'; 577 } 578 579 return 0; 580 } 581 ``` 582 583 [2184G - Nastiness of Segments](/contest/2184/problem/G "Codeforces Round 1072 (Div. 3)") 584 585 Idea: [Friendiks](/profile/Friendiks "Grandmaster Friendiks"); developer: [Friendiks](/profile/Friendiks "Grandmaster Friendiks") 586 587 **Hint 1** 588 589 Fix $L$ and $R$ and define functions of integer $d$: $f(d) = d$, $g(d) = \min(a_L, \dots, a_{L+d})$, where $0 \le d \le R-L$. What can be said about these functions? 590 591 **Answer** 592 593 $f(d)$ is increasing, $g(d)$ is non-increasing. 594 595 **Hint 2** 596 597 How many times can the problem condition be satisfied if expressed through $f$ and $g$? 598 599 **Answer** 600 601 The condition is equivalent to the intersection of $f(d)$ and $g(d)$, meaning there is at most one suitable point. 602 603 **Hint 3** 604 605 Since the function $h(d) = f(d) - g(d)$ is monotonic, the only candidate for the intersection point is the minimum $d$ such that $h(d) \ge 0$ (or $f(d) \ge g(d)$). 606 607 **Hint 4** 608 609 Segment tree. 610 611 **Editorial** 612 613 Tutorial is loading... 614 615 **Solution** 616 617 ``` 618 #include <bits/stdc++.h> 619 620 using namespace std; 621 622 const int MAXN = 2e5 + 7; 623 624 int a[MAXN], st[4 * MAXN]; 625 626 void build(int v, int l, int r) { 627 if (l + 1 == r) { 628 st[v] = a[l]; 629 return; 630 } 631 int m = (r + l) / 2; 632 build(v * 2 + 1, l, m); 633 build(v * 2 + 2, m, r); 634 st[v] = min(st[v * 2 + 1], st[v * 2 + 2]); 635 } 636 637 void upd(int v, int l, int r, int i, int x) { 638 if (i < l || r <= i) return; 639 if (l + 1 == r) { 640 a[i] = x; 641 st[v] = x; 642 return; 643 } 644 int m = (r + l) / 2; 645 upd(v * 2 + 1, l, m, i, x); 646 upd(v * 2 + 2, m, r, i, x); 647 st[v] = min(st[v * 2 + 1], st[v * 2 + 2]); 648 } 649 650 int getMin(int v, int l, int r, int lq, int rq) { 651 if (rq <= l || r <= lq) return (int) 1e6; 652 if (lq <= l && r <= rq) return st[v]; 653 int m = (r + l) / 2; 654 return min(getMin(v * 2 + 1, l, m, lq, rq), getMin(v * 2 + 2, m, r, lq, rq)); 655 } 656 657 int ans, currMn; 658 659 void findInter(int v, int l, int r, int lq, int rq) { 660 if (rq <= l || r <= lq || ans != (int) 1e6) return; 661 if (lq <= l && r <= rq && min(currMn, st[v]) > r - lq - 1) { 662 currMn = min(currMn, st[v]); 663 return; 664 } 665 if (l + 1 == r) { 666 ans = l; 667 return; 668 } 669 int m = (r + l) / 2; 670 findInter(v * 2 + 1, l, m, lq, rq); 671 findInter(v * 2 + 2, m, r, lq, rq); 672 } 673 674 int main() { 675 int t; 676 cin >> t; 677 678 while (t--) { 679 int n, q; 680 cin >> n >> q; 681 for (int i = 0; i < n; ++i) cin >> a[i]; 682 683 build(0, 0, n); 684 while (q--) { 685 int idx; 686 cin >> idx; 687 688 if (idx == 1) { 689 int i, x; 690 cin >> i >> x; 691 upd(0, 0, n, i - 1, x); 692 } else { 693 int l, r; 694 cin >> l >> r; 695 l--; 696 697 if (getMin(0, 0, n, l, r) > r - l) { 698 cout << "0\n"; 699 continue; 700 } 701 702 ans = currMn = (int) 1e6; 703 findInter(0, 0, n, l, r); 704 cout << (ans != (int) 1e6 && getMin(0, 0, n, l, ans + 1) == ans - l) << "\n"; 705 } 706 } 707 } 708 709 return 0; 710 } 711 ```