1712.md (13304B)
1 Source: https://codeforces.com/blog/entry/105919 2 3 Thanks for participating in the round, we hope you liked the problems! 4 5 **Solve count predictions (official div. 2)** 6 7 | Handle | A | B | C | D | E1 | E2 | F | 8 | --- | --- | --- | --- | --- | --- | --- | --- | 9 | [Vladithur](/profile/Vladithur "Мастер Vladithur") | 16K | 8K | 3K | 900 | 500 | 50 | 4 | 10 | [GlowCheese](/profile/GlowCheese "Мастер GlowCheese") | 14K | 9K | 5K | 500 | ? | ? | ? | 11 | [thanhchauns2](/profile/thanhchauns2 "Кандидат в мастера thanhchauns2") | 14K | 8K | 2K | 1K | 500 | ? | ? | 12 | [QBaraki](/profile/QBaraki "Эксперт QBaraki") | 14K | 7K | 2K | 1K | 500 | 24 | 5 | 13 | [welleyth](/profile/welleyth "Мастер welleyth") | 16K | 10K | 4K | 1.5K | 600 | 130 | 2 | 14 | [Kon567889](/profile/Kon567889 "Мастер Kon567889") | 14K | 10K | 5K | 2K | ? | ? | 5 | 15 16 [1712A - Чудесная перестановка](/contest/1712/problem/A "Codeforces Round 813 (Div. 2)") 17 18 **Hint** 19 20 The smallest possible sum is $1 + 2 + \ldots + k$. 21 22 **Tutorial** 23 24 Tutorial is loading... 25 26 **Solution** 27 28 ``` 29 #include <bits/stdc++.h> 30 31 #define all(x) (x).begin(), (x).end() 32 #define allr(x) (x).rbegin(), (x).rend() 33 #define gsize(x) (int)((x).size()) 34 35 const char nl = '\n'; 36 typedef long long ll; 37 typedef long double ld; 38 39 using namespace std; 40 41 int main() { 42 ios::sync_with_stdio(0); cin.tie(0); 43 44 int T; 45 cin >> T; 46 while (T--) { 47 int n, k; 48 cin >> n >> k; 49 vector<int> a(n); 50 for (int i = 0; i < n; i++) cin >> a[i]; 51 52 vector<int> b = a; 53 sort(all(b)); 54 int x = b[k - 1]; 55 56 int ans = 0; 57 for (int i = 0; i < k; i++) { 58 if (a[i] > x) ans++; 59 } 60 cout << ans << nl; 61 } 62 } 63 ``` 64 65 Bonus: solve for every $k$ from $1$ to $n$ for $n \le 10^5$. 66 67 [1712B - Жалкая перестановка](/contest/1712/problem/B "Codeforces Round 813 (Div. 2)") 68 69 **Hints** 70 71 **Hint 1** 72 73 In an optimal answer, for all $1 \le i \le n$, $\operatorname{lcm}(i, p_i) = i \cdot p_i$. 74 75 **Hint 2** 76 77 $\operatorname{lcm}(x, x + 1) = x \cdot (x + 1)$. 78 79 **Hint 3** 80 81 $\operatorname{lcm}(x, x + 1) + \operatorname{lcm}(x + 1, x) = x^2 + (x + 1)^2 - 1$. 82 83 **Tutorial** 84 85 Tutorial is loading... 86 87 **Solution** 88 89 ``` 90 #include <bits/stdc++.h> 91 92 #define all(x) (x).begin(), (x).end() 93 #define allr(x) (x).rbegin(), (x).rend() 94 #define gsize(x) (int)((x).size()) 95 96 const char nl = '\n'; 97 typedef long long ll; 98 typedef long double ld; 99 100 using namespace std; 101 102 int main() { 103 ios::sync_with_stdio(0); cin.tie(0); 104 105 int T; 106 cin >> T; 107 while (T--) { 108 int n; 109 cin >> n; 110 if (n % 2 == 0) { 111 for (int i = 1; i <= n; i += 2) { 112 cout << i + 1 << ' ' << i << ' '; 113 } 114 cout << nl; 115 } else { 116 cout << 1 << ' '; 117 for (int i = 2; i <= n; i += 2) { 118 cout << i + 1 << ' ' << i << ' '; 119 } 120 cout << nl; 121 } 122 } 123 } 124 ``` 125 126 Bonus: try to prove the solution without the editorial! 127 128 [1712C - Очередная задача про сортировку](/contest/1712/problem/C "Codeforces Round 813 (Div. 2)") 129 130 **Hints** 131 132 **Hint 1** 133 134 The operation only decreases numbers. 135 136 **Hint 2** 137 138 An array is sorted if there is no index $i$ such that $a_i \gt a_{i + 1}$. 139 140 **Hint 3** 141 142 Suppose there is an index $i$ such that $a_i \gt a_{i + 1}$. What operations do you need to perform to make $a_i \le a_{i + 1}$? 143 144 **Tutorial** 145 146 Tutorial is loading... 147 148 **Solution** 149 150 ``` 151 #include <bits/stdc++.h> 152 153 #define all(x) (x).begin(), (x).end() 154 #define allr(x) (x).rbegin(), (x).rend() 155 #define gsize(x) (int)((x).size()) 156 157 const char nl = '\n'; 158 typedef long long ll; 159 typedef long double ld; 160 161 using namespace std; 162 163 int main() { 164 ios::sync_with_stdio(0); cin.tie(0); 165 166 int T; 167 cin >> T; 168 while (T--) { 169 int n; 170 cin >> n; 171 172 vector<int> a(n); 173 map<int, vector<int>> p; 174 for (int i = 0; i < n; i++) { 175 cin >> a[i]; 176 p[a[i]].push_back(i); 177 } 178 179 int ans = 0; 180 set<int> ts; 181 for (int i = 0; i < n - 1; i++) { 182 if (a[i] > a[i + 1]) ts.insert(i); 183 } 184 185 while (!ts.empty()) { 186 int i = *ts.begin(); 187 int x; 188 if (a[i] > 0) { 189 x = a[i]; 190 } else { 191 x = a[i + 1]; 192 } 193 194 for (int j: p[x]) { 195 a[j] = 0; 196 ts.erase(j - 1); 197 ts.erase(j); 198 if (j > 0 && a[j - 1] > a[j]) ts.insert(j - 1); 199 if (j + 1 < n && a[j] > a[j + 1]) ts.insert(j); 200 } 201 ans++; 202 } 203 204 cout << ans << nl; 205 } 206 } 207 ``` 208 209 Bonus: solve for when $a_i$ can also be negative. 210 211 [1712D - Пустой граф](/contest/1712/problem/D "Codeforces Round 813 (Div. 2)") 212 213 **Hints** 214 215 **Hint 1** 216 217 $\operatorname{d}(u; v) \le 2 \cdot \min(a_1 \ldots a_n)$ 218 219 **Hint 2** 220 221 *diameter* $\le 2 \cdot \min(a_1 \ldots a_n)$ 222 223 **Hint 3** 224 225 *diameter* $\le \max\limits_{1 \le i \le n - 1}{\min(a_i,a_{i+1})}$ 226 227 **Hint 4** 228 229 Binary search on the answer or do a clever greedy. 230 231 **Tutorial** 232 233 Tutorial is loading... 234 235 **Solution** 236 237 ``` 238 #include <bits/stdc++.h> 239 240 #define all(x) (x).begin(), (x).end() 241 #define allr(x) (x).rbegin(), (x).rend() 242 #define gsize(x) (int)((x).size()) 243 244 const char nl = '\n'; 245 typedef long long ll; 246 typedef long double ld; 247 248 using namespace std; 249 250 const int inf = 1000000000; 251 252 bool f(vector<int> a, int k, int ans) { 253 int n = gsize(a); 254 int dk = 0; 255 for (int i = 0; i < n; i++) { 256 if (a[i] * 2 < ans) { 257 a[i] = inf; 258 k--; 259 dk++; 260 } 261 } 262 263 if (k < 0) return false; 264 if ((k > 0 && dk > 0) || k >= 2) return true; 265 266 if (k == 1 && dk == 0) { 267 return *max_element(all(a)) >= ans; 268 } 269 270 for (int i = 0; i < n - 1; i++) { 271 if (min(a[i], a[i + 1]) >= ans) return true; 272 } 273 274 return false; 275 } 276 277 void solve() { 278 int n, k; 279 cin >> n >> k; 280 vector<int> a(n); 281 for (int i = 0; i < n; i++) cin >> a[i]; 282 283 int lb = 0, ub = inf, tans = 0; 284 while (lb <= ub) { 285 int tm = (lb + ub) / 2; 286 if (f(a, k, tm)) { 287 tans = tm; 288 lb = tm + 1; 289 } else { 290 ub = tm - 1; 291 } 292 } 293 294 cout << tans << nl; 295 } 296 297 int main() { 298 ios::sync_with_stdio(0); cin.tie(0); 299 300 int T; 301 cin >> T; 302 while (T--) solve(); 303 } 304 ``` 305 306 Bonus: solve for every $k$ from $1$ to $n$. 307 308 [1712E2 - Сумма НОК (сложная версия)](/contest/1712/problem/E2 "Codeforces Round 813 (Div. 2)") 309 310 **Hints** 311 312 **Hint 1** 313 314 Count the number of "bad" triplets such that $\operatorname{lcm}(i, j, k) \lt i + j + k$. 315 316 **Hint 2** 317 318 $\operatorname{lcm}(i, j, k) \le 2 \cdot k$ in a bad triplet. 319 320 **Hint 3** 321 322 A triplet is bad iff $\operatorname{lcm}(i, j, k) = k$ or ($\operatorname{lcm}(i, j, k) = 2 \cdot k$ and $i + j \gt k$). 323 324 **Hint 4** 325 326 $\operatorname{lcm}(i, j, k) = x$ implies $i$, $j$, and $k$ are all divisors of $x$. 327 328 **Hint 5** 329 330 For every $k$, iterate over all pairs of divisors of $2 \cdot k$. 331 332 **Hint 6** 333 334 Think of the "bad" triplets as of segments $[i; k]$ with some weight. 335 336 **Hint 7** 337 338 Solve in offline. 339 340 **Tutorial** 341 342 Tutorial is loading... 343 344 **Solution** 345 346 ``` 347 #include <bits/stdc++.h> 348 349 #define all(x) (x).begin(), (x).end() 350 #define allr(x) (x).rbegin(), (x).rend() 351 #define gsize(x) (int)((x).size()) 352 353 const char nl = '\n'; 354 typedef long long ll; 355 typedef long double ld; 356 357 using namespace std; 358 359 const int maxn = 200000; 360 361 int t[(maxn + 1) * 4]; 362 363 void update(int v, int tl, int tr, int i, int x) { 364 t[v] += x; 365 if (tl != tr - 1) { 366 int tm = (tl + tr) / 2; 367 if (i < tm) update(2*v + 1, tl, tm, i, x); 368 else update(2*v + 2, tm, tr, i, x); 369 } 370 } 371 372 int query(int v, int tl, int tr, int l, int r) { 373 if (l >= r) return 0; 374 if (tl == l && tr == r) return t[v]; 375 else { 376 int tm = (tl + tr) / 2; 377 int r1 = query(2*v + 1, tl, tm, l, min(r, tm)); 378 int r2 = query(2*v + 2, tm, tr, max(l, tm), r); 379 return r1 + r2; 380 } 381 } 382 383 384 int main() { 385 ios::sync_with_stdio(0); cin.tie(0); 386 387 vector<vector<int>> d(2*maxn + 1); 388 389 for (int i = 1; i <= maxn; i++) { 390 for (int j = i; j <= 2*maxn; j += i) { 391 d[j].push_back(i); 392 } 393 } 394 395 vector<vector<pair<int, int>>> segs(maxn + 1); 396 397 for (int k = 1; k <= maxn; k++) { 398 for (int ti = 0; ti < gsize(d[2*k]); ti++) { 399 int i = d[2*k][ti], ct = 0; 400 401 for (int tj = ti + 1; tj < gsize(d[2*k]); tj++) { 402 int j = d[2*k][tj]; 403 if (j >= k) break; 404 if (i + j > k || (k % i == 0 && k % j == 0)) ct++; 405 } 406 407 if (ct > 0) { 408 segs[i].emplace_back(k, ct); 409 } 410 } 411 } 412 413 414 415 int T; 416 cin >> T; 417 418 vector<ll> ans(T); 419 vector<array<int, 3>> queries; 420 421 for (int i = 0; i < T; i++) { 422 ll l, r; 423 cin >> l >> r; 424 queries.push_back({l, r, i}); 425 ans[i] = (r - l + 1) * (r - l) * (r - l - 1) / 6; 426 } 427 428 sort(all(queries)); 429 430 int ti = T - 1; 431 for (int i = maxn; i >= 1; i--) { 432 433 // Update ST 434 for (auto [r, ct]: segs[i]) { 435 update(0, 0, maxn + 1, r, ct); 436 } 437 438 // Get Answers 439 while (ti >= 0 && queries[ti][0] == i) { 440 ans[queries[ti][2]] -= query(0, 0, maxn + 1, i, queries[ti][1] + 1); 441 ti--; 442 } 443 } 444 for (int i = 0; i < T; i++) cout << ans[i] << nl; 445 } 446 ``` 447 448 Bonus: solve the problem in $\mathcal{O}((n + t) \log n)$ or better. 449 450 [1712F - Триаметр](/contest/1712/problem/F "Codeforces Round 813 (Div. 2)") 451 452 **Hints** 453 454 **Hint 1** 455 456 Let $f_v$ be the distance to the closest vertex $\in L$ to $v$. You can calculate it for every vertex in $O(n)$. 457 458 **Hint 2** 459 460 The distance in the new graph $\operatorname{d'}(u, v)$ is equal to $\min(\operatorname{d}(u, v), f_u + f_v + x)$ 461 462 **Hint 3** 463 464 Suppose there is a vertex $v$ with $f_v \gt 0$. Then there is always a vertex $u$ in the subtree of $v$ such that $f_u \lt f_v$ and $depth_u$ > $depth_v$. 465 466 **Hint 4** 467 468 Think small-to-large merging. 469 470 **Hint 5** 471 472 Maintain the largest value of $depth_v$ over all $v$ with $f_v = i$ for all needed $i$. 473 474 **Hint 6** 475 476 In this problem, small-to-large merging works in $O(n)$. 477 478 **Hint 7** 479 480 The diameter is $\le n$. So you can increase it by $1$ at most $n$ times. 481 482 **Tutorial** 483 484 Tutorial is loading... 485 486 **Solution** 487 488 ``` 489 #include <bits/stdc++.h> 490 491 #define all(x) (x).begin(), (x).end() 492 #define allr(x) (x).rbegin(), (x).rend() 493 #define gsize(x) (int)((x).size()) 494 495 const char nl = '\n'; 496 typedef long long ll; 497 typedef long double ld; 498 499 using namespace std; 500 501 const int maxn = 1000000; 502 int f[maxn], d[maxn]; 503 vector<int> g[maxn], g2[maxn], val[maxn]; 504 int n, q; 505 506 vector<int> ans, x; 507 508 void solve() { 509 510 for (int v = n - 1; v >= 0; v--) { 511 for (int u: g[v]) { 512 if (gsize(val[u]) > gsize(val[v])) swap(val[u], val[v]); 513 for (int fu = 0; fu < gsize(val[u]); fu++) { 514 for (int qi = 0; qi < q; qi++) { 515 while (true) { 516 int fv = max(0, ans[qi] - fu - x[qi]); 517 if (fv < gsize(val[v]) && 518 val[v][fv] + val[u][fu] - 2*d[v] >= ans[qi]) ans[qi]++; 519 else break; 520 } 521 } 522 } 523 for (int fu = 0; fu < gsize(val[u]); fu++) { 524 val[v][fu] = max(val[v][fu], val[u][fu]); 525 } 526 val[u].clear(); 527 val[u].shrink_to_fit(); 528 } 529 { 530 int fu = f[v]; 531 for (int qi = 0; qi < q; qi++) { 532 while (true) { 533 int fv = max(0, ans[qi] - fu - x[qi]); 534 if (fv < gsize(val[v]) && 535 val[v][fv] - d[v] >= ans[qi]) ans[qi]++; 536 else break; 537 } 538 } 539 if (fu == gsize(val[v])) { 540 val[v].push_back(d[v]); 541 } 542 } 543 } 544 545 for (int i = 0; i < q; i++) { 546 ans[i]--; 547 } 548 } 549 550 int main() { 551 ios::sync_with_stdio(0); cin.tie(0); 552 553 cin >> n; 554 555 vector<int> deg(n); 556 for (int i = 1; i < n; i++) { 557 int p; 558 cin >> p; 559 d[i] = d[p - 1] + 1; 560 g[p - 1].push_back(i); 561 g2[i].push_back(p - 1); 562 } 563 564 { 565 queue<int> qe; 566 vector<bool> used(n, false); 567 for (int i = 0; i < n; i++) { 568 if (gsize(g2[i]) + gsize(g[i]) == 1) { 569 qe.push(i); 570 used[i] = true; 571 } 572 } 573 574 while (!qe.empty()) { 575 int v = qe.front(); 576 qe.pop(); 577 for (int u: g[v]) { 578 if (used[u]) continue; 579 f[u] = f[v] + 1; 580 qe.push(u); 581 used[u] = true; 582 } 583 584 for (int u: g2[v]) { 585 if (used[u]) continue; 586 f[u] = f[v] + 1; 587 qe.push(u); 588 used[u] = true; 589 } 590 } 591 } 592 593 cin >> q; 594 for (int i = 0; i < q; i++) { 595 int tx; 596 cin >> tx; 597 x.push_back(tx); 598 ans.push_back(0); 599 } 600 601 solve(); 602 603 for (int tans: ans) cout << tans << ' '; 604 cout << nl; 605 } 606 ``` 607 608 Bonus: solve for $n, q \le 10^6$. 609 610 **Don't forget to rate the problems!** 611 612 **Problem Feedback** 613 614 **A** 615 616 * Good problem 617 * Mid problem 618 * Bad problem 619 620 **B** 621 622 * Good problem 623 * Mid problem 624 * Bad problem 625 626 **C** 627 628 * Good problem 629 * Mid problem 630 * Bad problem 631 632 **D** 633 634 * Good problem 635 * Mid problem 636 * Bad problem 637 638 **E1** 639 640 * Good problem 641 * Mid problem 642 * Bad problem 643 644 **E2** 645 646 * Good problem 647 * Mid problem 648 * Bad problem 649 650 **F** 651 652 * Good problem 653 * Mid problem 654 * Bad problem 655 656 PS: Solution codes probably will be added later. 657 658 **UPD: explanations of the references:** 659 660 **Click here** 661 662 Hope you liked them! 663 664 **A** 665 666 The quote is just a modification of the original title of KonoSuba. 667 668 **B** 669 670 This is just something I invented, no reference here. Hope you liked the short poem! 671 672 **C** 673 674 The quote is the meme "people die when they are killed" in the Fate series, changed to fit the programming context. And the title is just "Fate Zero" changed to "Sort Zero". 675 676 **D** 677 678 "Do you have a wish?" is a recurring phrase in the LN series [HakoMari](https://myanimelist.net/manga/55215/Utsuro_no_Hako_to_Zero_no_Maria), referring to the wish granting "boxes". The title is just "Empty Box" changed to "Empty Graph". Also, "O_o" is a reference to one of the main characters, "O". 679 680 **E** 681 682 The quote can probably be traced to many origins, but I personally modified the quote "We are legion, for we are many" from the series 86. There were also a lot of 6's and 8's in the sample, which might have helped you guess. 683 684 **F** 685 686 I didn't really think about this one, just modified a quote from Vivy a bit. 687 688 **UPD2: added solution codes (better late than never...)**