2132.md (17794B)
1 Source: https://codeforces.com/blog/entry/145692 2 3 We hope you enjoyed the contest! Thank you for participating! This is our second 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 * C1: 18 * C2: 19 * D: 20 * E: 21 * F: 22 * G: 23 24 **Which problems did you not like (you can choose multiple)?** 25 26 * A: 27 * B: 28 * C1: 29 * C2: 30 * D: 31 * E: 32 * F: 33 * G: 34 35 [2132A - Homework](/contest/2132/problem/A "Codeforces Round 1043 (Div. 3)") 36 37 Idea: [Wileyne](/profile/Wileyne "Expert Wileyne"); developer: [Wileyne](/profile/Wileyne "Expert Wileyne") 38 39 **Editorial** 40 41 Tutorial is loading... 42 43 **Solution** 44 45 ``` 46 #include <bits/stdc++.h> 47 48 using namespace std; 49 50 void solve() { 51 string a, b, c; 52 int n, m; 53 cin >> n >> a; 54 cin >> m >> b >> c; 55 string add_left = ""; 56 for (int i = 0; i < m; ++i) { 57 if (c[i] == 'V') { 58 add_left += b[i]; 59 } else { 60 a += b[i]; 61 } 62 } 63 reverse(add_left.begin(), add_left.end()); 64 cout << add_left + a << '\n'; 65 } 66 67 int main() { 68 int t; 69 cin >> t; 70 while (t--) 71 solve(); 72 return 0; 73 } 74 ``` 75 76 [2132B - The Secret Number](/contest/2132/problem/B "Codeforces Round 1043 (Div. 3)") 77 78 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [fstilus](/profile/fstilus "Expert fstilus") 79 80 **Hint** 81 82 If Vadim appends $k$ zeros to the number $x$, what will be the ratio between $n$ and $x$? 83 84 **Answer** 85 86 $n = x \cdot (10^k + 1)$ 87 88 **Editorial** 89 90 Tutorial is loading... 91 92 **Solution** 93 94 ``` 95 #include <bits/stdc++.h> 96 97 using namespace std; 98 99 int main() { 100 int t; 101 cin >> t; 102 103 while (t--) { 104 long long r; 105 cin >> r; 106 107 long long d = 11; 108 vector <long long> ans; 109 while (r >= d) { 110 if (r % d == 0) 111 ans.push_back(r / d); 112 d = (d - 1) * 10 + 1; 113 } 114 115 cout << (int)ans.size() << '\n'; 116 for (int i = (int)ans.size() - 1; i >= 0; --i) 117 cout << ans[i] << ' '; 118 cout << '\n'; 119 } 120 121 return 0; 122 } 123 ``` 124 125 [2132C1 - The Cunning Seller (easy version)](/contest/2132/problem/C1 "Codeforces Round 1043 (Div. 3)") 126 127 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [KotlechkovEgor](/profile/KotlechkovEgor "Master KotlechkovEgor") 128 129 **Hint 1** 130 131 Does it make sense to use the same type of deal more than 2 times? 132 133 **Hint 2** 134 135 The solution with the minimum number of deals is unique. 136 137 **Hint 3** 138 139 Ternary numeral system. 140 141 **Editorial** 142 143 Tutorial is loading... 144 145 **Solution** 146 147 ``` 148 #include <bits/stdc++.h> 149 150 using namespace std; 151 152 int main() { 153 vector <long long> cost; 154 long long c = 3; 155 long long cnt = 1; 156 for (int i = 0; i < 21; ++i) { 157 cost.push_back(c); 158 c = 3 * c + cnt; 159 cnt *= 3; 160 } 161 162 int t; 163 cin >> t; 164 while (t--) { 165 long long n; 166 cin >> n; 167 long long min_k = 0; 168 long long min_cost = 0; 169 int sz = 0; 170 while (n) { 171 min_k += n % 3; 172 min_cost += (n % 3) * cost[sz]; 173 n /= 3; 174 sz++; 175 } 176 cout << min_cost << '\n'; 177 } 178 179 return 0; 180 } 181 ``` 182 183 [2132C2 - The Cunning Seller (hard version)](/contest/2132/problem/C2 "Codeforces Round 1043 (Div. 3)") 184 185 Idea: [Boodoochai](/profile/Boodoochai "Expert Boodoochai"); developer: [KotlechkovEgor](/profile/KotlechkovEgor "Master KotlechkovEgor") 186 187 **Hint 1** 188 189 What is more profitable: 3 deals for $3^x$ watermelons each, or 1 deal for $3^{x+1}$ watermelons? 190 191 **Hint 2** 192 193 Recall the solution to problem C1. 194 195 **Editorial** 196 197 Tutorial is loading... 198 199 **Solution** 200 201 ``` 202 #include <bits/stdc++.h> 203 204 using namespace std; 205 206 int main() { 207 vector <long long> cost; 208 long long c = 3; 209 long long cnt = 1; 210 for (int i = 0; i < 21; ++i) { 211 cost.push_back(c); 212 c = 3 * c + cnt; 213 cnt *= 3; 214 } 215 216 int t; 217 cin >> t; 218 while (t--) { 219 long long n, k; 220 cin >> n >> k; 221 vector <long long> tr; 222 long long min_k = 0; 223 while (n) { 224 tr.push_back(n % 3); 225 min_k += n % 3; 226 n /= 3; 227 } 228 if (min_k > k) { 229 cout << -1 << '\n'; 230 continue; 231 } 232 k -= min_k; 233 k /= 2; 234 for (int i = (int)tr.size() - 1; i >= 1; --i) { 235 if (tr[i] <= k) { 236 tr[i - 1] += 3 * tr[i]; 237 k -= tr[i]; 238 tr[i] = 0; 239 } else { 240 tr[i - 1] += k * 3; 241 tr[i] -= k; 242 break; 243 } 244 } 245 ll an = 0; 246 for (int i = (int)tr.size() - 1; i >= 0; --i) 247 an += cost[i] * tr[i]; 248 cout << an << '\n'; 249 } 250 251 return 0; 252 } 253 ``` 254 255 [2132D - From 1 to Infinity](/contest/2132/problem/D "Codeforces Round 1043 (Div. 3)") 256 257 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developer: [fstilus](/profile/fstilus "Expert fstilus") 258 259 **Hint 1** 260 261 Find out which number the $k$-th digit belongs to in the infinite sequence. Let this number be $n$. Instead of analyzing the sequence, we can calculate the sum of the sums of the digits of all integers from $0$ to $n - 1$ and add to this the sum of the required digits of the number $n$. 262 263 **Hint 2** 264 265 Mentally add leading zeros to all numbers from $0$ to $n - 1$ so that their lengths become the same. The sum of the sums of the digits will not change, but it will be more convenient to determine the formulas in this case. 266 267 **Editorial** 268 269 Tutorial is loading... 270 271 **Solution** 272 273 ``` 274 #include <bits/stdc++.h> 275 276 using namespace std; 277 278 int main() { 279 int t; 280 cin >> t; 281 282 while (t--) { 283 long long k; 284 cin >> k; 285 long long cur = 9, len = 1; 286 while (k - cur * len > 0) { 287 k -= cur * len; 288 cur *= 10; 289 len++; 290 } 291 string s = to_string(cur / 9 + (k - 1) / len); 292 long long ans = 0; 293 for (int i = 0; i < (k - 1) % len + 1; i++) 294 ans += s[i] - '0'; 295 long long pr_s = 0; 296 for (int i = 0; i < s.length(); i++) { 297 int curd = s[i] - '0'; 298 if (curd) 299 ans += curd * (len - 1) * cur / 2 + curd * (2 * pr_s + curd - 1) / 2 * cur / 9; 300 cur /= 10, len--; 301 pr_s += curd; 302 } 303 cout << ans << '\n'; 304 } 305 306 return 0; 307 } 308 ``` 309 310 [2132E - Arithmetics Competition](/contest/2132/problem/E "Codeforces Round 1043 (Div. 3)") 311 312 Idea: [EzikBro](/profile/EzikBro "Master EzikBro"); developer: [EzikBro](/profile/EzikBro "Master EzikBro") 313 314 **Hint 1** 315 316 If we know how many specific cards Vadim should take, and how many should take Kostya (for example when $x + y = z$). How can we then obtain the maximum possible sum? 317 318 **Hint 2** 319 320 We need to quickly compute the sum of the $x$ maximum elements in array $a$ and the sum of the $y$ maximum elements in array $b$. What should we do to be able to compute this for arbitrary $x$ and $y$ in $O(1)$? 321 322 **Hint 3** 323 324 How can we solve this problem if $x = n$ and $y = m$ — that is, each person can choose any number of cards, as long as their total is $z$? 325 326 **Hint 4** 327 328 If $x = n$ and $y = m$, then the optimal set of $z$ cards consists of $x'$ maximum cards from Vadim and $y'$ maximum cards from Kostya (where $x' + y' = z$). How should we adjust this optimal answer if the optimal number for Vadim or Kostya exceeds their limits (that is, if $x \lt x'$ or $y \lt y'$)? 329 330 **Editorial** 331 332 Tutorial is loading... 333 334 **Solution 1** 335 336 ``` 337 #include <bits/stdc++.h> 338 339 using namespace std; 340 341 void solve() { 342 int n, m, q; 343 cin >> n >> m >> q; 344 vector <int> a(n), b(m); 345 for (int i = 0; i < n; i++) 346 cin >> a[i]; 347 for (int i = 0; i < m; i++) 348 cin >> b[i]; 349 sort(a.rbegin(), a.rend()); 350 sort(b.rbegin(), b.rend()); 351 352 vector <long long> pa(n + 1), pb(m + 1); 353 for (int i = 0; i < n; i++) 354 pa[i + 1] = pa[i] + a[i]; 355 for (int i = 0; i < m; i++) 356 pb[i + 1] = pb[i] + b[i]; 357 358 vector <pair <int, int>> ans(n + m + 1); 359 int l = 0, r = 0; 360 for (int i = 1; i < ans.size(); i++) { 361 if (l < n && r < m) { 362 if (a[l] < b[r]) 363 r++; 364 else 365 l++; 366 } 367 else if (l == n) 368 r++; 369 else if (r == m) 370 l++; 371 ans[i] = { l, r }; 372 } 373 374 for (int i = 0; i < q; i++) { 375 int x, y, z; 376 cin >> x >> y >> z; 377 l = ans[z].first, r = ans[z].second; 378 if (l > x) 379 cout << pa[x] + pb[z - x] << '\n'; 380 else if (r > y) 381 cout << pa[z - y] + pb[y] << '\n'; 382 else 383 cout << pa[l] + pb[r] << '\n'; 384 } 385 } 386 387 int main() { 388 int t; 389 cin >> t; 390 while (t--) 391 solve(); 392 return 0; 393 } 394 ``` 395 396 **Solution 2** 397 398 ``` 399 #include <bits/stdc++.h> 400 401 using namespace std; 402 403 void solve() { 404 int n, m, q; 405 cin >> n >> m >> q; 406 vector <int> a(n), b(m); 407 for (int i = 0; i < n; i++) 408 cin >> a[i]; 409 for (int i = 0; i < m; i++) 410 cin >> b[i]; 411 sort(a.rbegin(), a.rend()); 412 sort(b.rbegin(), b.rend()); 413 414 vector <long long> pa(n + 1), pb(m + 1); 415 for (int i = 0; i < n; i++) 416 pa[i + 1] = pa[i] + a[i]; 417 for (int i = 0; i < m; i++) 418 pb[i + 1] = pb[i] + b[i]; 419 420 for (int i = 0; i < q; i++) { 421 int x, y, z; 422 cin >> x >> y >> z; 423 424 int l = max(0, z - y); 425 int r = min(z, x); 426 while (l + 2 < r) { 427 int m1 = (l + l + r) / 3; 428 int m2 = (l + r + r) / 3; 429 if (pa[m1] + pb[z - m1] > pa[m2] + pb[z - m2]) { 430 r = m2; 431 } else { 432 l = m1; 433 } 434 } 435 436 long long s = 0; 437 for (int i = l; i <= r; i++) 438 s = max(s, pa[i] + pb[z - i]); 439 440 cout << s << '\n'; 441 } 442 } 443 444 int main() { 445 int t; 446 cin >> t; 447 while (t--) 448 solve(); 449 return 0; 450 } 451 ``` 452 453 [2132F - Rada and the Chamomile Valley](/contest/2132/problem/F "Codeforces Round 1043 (Div. 3)") 454 455 Idea: [Friendiks](/profile/Friendiks "Master Friendiks"), [Wileyne](/profile/Wileyne "Expert Wileyne"); developers: [Friendiks](/profile/Friendiks "Master Friendiks"), [Wileyne](/profile/Wileyne "Expert Wileyne") 456 457 **Hint 1** 458 459 Recall or learn what bridges are and understand how this is related to the lanes that lie on all paths from $1$ to $n$. 460 461 **Hint 2** 462 463 How to find all the bridges that lie on every path from $1$ to $n$? 464 465 **Hint 3** 466 467 Solve the problem for the case where $n = q$ and $c_i = i$. 468 469 **Hint 4** 470 471 How to find the nearest vertex from a given set of vertices $S$ for each vertex? 472 473 **Editorial** 474 475 Tutorial is loading... 476 477 **Solution** 478 479 ``` 480 #include <bits/stdc++.h> 481 482 using namespace std; 483 484 vector <vector <int>> g; 485 vector <bool> used; 486 vector <int> d, h; 487 vector <pair <int, int>> edges; 488 vector <int> cut, path; 489 int mark = 1; 490 491 void dfs(int v, int p, int n) { 492 used[v] = true; 493 d[v] = h[v] = (p == -1 ? 0 : d[p] + 1); 494 if (v == n) mark = 0; 495 for (auto e : g[v]) { 496 int to = edges[e].first + edges[e].second - v; 497 if (to == p) continue; 498 if (used[to]) 499 h[v] = min(h[v], d[to]); 500 else { 501 path[e] ^= mark; 502 dfs(to, v, n); 503 path[e] ^= mark; 504 h[v] = min(h[v], h[to]); 505 if (h[to] > d[v]) cut[e] = 1; 506 } 507 } 508 } 509 510 int main() { 511 int t; 512 cin >> t; 513 while (t--) { 514 int n, m; 515 cin >> n >> m; 516 517 g.assign(n + 1, {}); 518 used.assign(n + 1, false); 519 d.assign(n + 1, 0); 520 h.assign(n + 1, 0); 521 edges = {}; 522 cut.assign(m, false); 523 path.assign(m, false); 524 mark = 1; 525 for (int i = 0; i < m; ++i) { 526 int a, b; 527 cin >> a >> b; 528 edges.push_back({a, b}); 529 g[a].push_back(i); 530 g[b].push_back(i); 531 } 532 533 dfs(1, -1, n); 534 535 vector <int> ans(n + 1, n + m); 536 vector <int> dist(n + 1, n + m); 537 queue <int> q; 538 for (int i = 0; i < m; ++i) { 539 if (cut[i] && path[i]) { 540 ans[edges[i].first] = min(ans[edges[i].first], i + 1); 541 ans[edges[i].second] = min(ans[edges[i].second], i + 1); 542 if (dist[edges[i].first]) { 543 dist[edges[i].first] = 0; 544 q.push(edges[i].first); 545 } 546 if (dist[edges[i].second]) { 547 dist[edges[i].second] = 0; 548 q.push(edges[i].second); 549 } 550 } 551 } 552 553 while (!q.empty()) { 554 int v = q.front(); 555 q.pop(); 556 for (auto e : g[v]) { 557 int to = edges[e].first + edges[e].second - v; 558 if (dist[to] > dist[v] + 1) { 559 dist[to] = dist[v] + 1; 560 ans[to] = ans[v]; 561 q.push(to); 562 } 563 else if (dist[to] == dist[v] + 1) 564 ans[to] = min(ans[to], ans[v]); 565 } 566 } 567 568 int Q; 569 cin >> Q; 570 while (Q--) { 571 int v; 572 cin >> v; 573 if (ans[v] == n + m) cout << -1; 574 else cout << ans[v]; 575 if (t || Q) cout << '\n'; 576 } 577 } 578 579 return 0; 580 } 581 ``` 582 583 [2132G - Famous Choreographer](/contest/2132/problem/G "Codeforces Round 1043 (Div. 3)") 584 585 Idea: [fstilus](/profile/fstilus "Expert fstilus"); developers: [fstilus](/profile/fstilus "Expert fstilus"), [pskobx](/profile/pskobx "Master pskobx") 586 587 **Hint 1** 588 589 There is no point in adding new symbols both above and below the original table simultaneously. Similarly, there is no point in adding symbols both to the left and to the right of the table at the same time. 590 591 **Hint 2** 592 593 The center of the optimal answer table lies within the original one. 594 595 **Hint 3** 596 597 We do not need to construct the answer; it is sufficient to check that an answer exists for the current center. Think about how to do this. 598 599 **Hint 4** 600 601 An answer exists for the current center if the subtable, which is the intersection of the original table and the one rotated around the center by $180^{\circ}$, becomes identical to the original when rotated by $180^{\circ}$. This subtable must contain at least one of the corners of the original table. 602 603 **Hint 5** 604 605 The checking of centers can be replaced by the checking of subtables that contain at least one of the corners of the original table. 606 607 **Hint 6** 608 609 To check the subtables to see if they become identical to the original when rotated by $180^{\circ}$, we can use hashing. 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 MOD = 998244353; 623 const int P[2] = { 107, 61 }; 624 int BP[2]; 625 626 long long bin_pow(long long a, int n) { 627 long long ret = 1; 628 while (n) { 629 if (n & 1) ret = (ret * a) % MOD; 630 a = (a * a) % MOD; 631 n >>= 1; 632 } 633 return ret; 634 } 635 636 inline int add(int a, int b) { 637 int res = a + b; 638 if (res >= MOD) return res - MOD; 639 return res; 640 } 641 642 inline int sub(int a, int b) { 643 int res = a - b; 644 if (res < 0) return res + MOD; 645 return res; 646 } 647 648 inline int mult(int a, int b) { 649 long long res = (long long)a * b; 650 if (res >= MOD) return res % MOD; 651 return res; 652 } 653 654 int main() { 655 int t; 656 cin >> t; 657 658 BP[0] = bin_pow(P[0], MOD - 2); 659 BP[1] = bin_pow(P[1], MOD - 2); 660 vector <int> pows[2]; 661 vector <int> bpows[2]; 662 for (int j = 0; j < 2; j++) { 663 pows[j].resize(1e6, 1); 664 bpows[j].resize(1e6, 1); 665 for (int i = 1; i < 1e6; i++) { 666 pows[j][i] = mult(pows[j][i - 1], P[j]); 667 bpows[j][i] = mult(bpows[j][i - 1], BP[j]); 668 } 669 } 670 671 while (t--) { 672 int n, m; 673 cin >> n >> m; 674 675 vector <string> f(n); 676 for (int i = 0; i < n; i++) 677 cin >> f[i]; 678 679 vector <vector <int>> hash(n + 2, vector <int> (m + 2, 0)); 680 vector <vector <int>> bhash(n + 2, vector <int> (m + 2, 0)); 681 for (int i = 1; i <= n; i++) { 682 for (int j = 1; j <= m; j++) { 683 int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][i - 1], pows[1][j - 1])); 684 hash[i][j] = add(sub(add(hash[i - 1][j], hash[i][j - 1]), hash[i - 1][j - 1]), cur); 685 } 686 } 687 for (int i = n; i >= 1; i--) { 688 for (int j = m; j >= 1; j--) { 689 int cur = mult((f[i - 1][j - 1] - 'a' + 1), mult(pows[0][n - i], pows[1][m - j])); 690 bhash[i][j] = add(sub(add(bhash[i + 1][j], bhash[i][j + 1]), bhash[i + 1][j + 1]), cur); 691 } 692 } 693 694 auto isp = [&](int x1, int y1, int x2, int y2) { 695 int hsh = add(sub(sub(hash[x2][y2], hash[x1-1][y2]), hash[x2][y1-1]), hash[x1-1][y1-1]); 696 int bhsh = add(sub(sub(bhash[x1][y1], bhash[x2+1][y1]), bhash[x1][y2+1]), bhash[x2+1][y2+1]); 697 hsh = mult(hsh, mult(bpows[0][x1 - 1], bpows[1][y1 - 1])); 698 bhsh = mult(bhsh, mult(bpows[0][n - x2], bpows[1][m - y2])); 699 return hsh == bhsh; 700 }; 701 702 int mn = n * m * 4; 703 for (int i = 1; i <= n; i++) { 704 for (int j = 1; j <= m; j++) { 705 if (isp(1, 1, i, j)) mn = min(mn, (2 * n - i) * (2 * m - j)); 706 if (isp(1, j, i, m)) mn = min(mn, (2 * n - i) * (m + j - 1)); 707 if (isp(i, 1, n, j)) mn = min(mn, (n + i - 1) * (2 * m - j)); 708 if (isp(i, j, n, m)) mn = min(mn, (n + i - 1) * (m + j - 1)); 709 } 710 } 711 712 cout << mn - m * n << '\n'; 713 } 714 715 return 0; 716 } 717 ```