1893.md (13182B)
1 Source: https://codeforces.com/blog/entry/122074 2 3 I'm very very sorry to all Div2 participants for unclearness in statement of A, and not including notes in the statement of B, hope it didnt ruined a contest for you. Thank you all for participating, I hope you enjoyed non-empty subset of the problems! You can rate the problems of the round in the corresponding spoilers. 4 5 [1894A - Secret Sport](/contest/1894/problem/A "Codeforces Round 908 (Div. 2)") 6 7 **Hint 1** 8 9 You can always bruteforce $X$ and $Y$, and check every pair of $(X, Y)$ separately, but there is a tRiCkY solution that involves zero implementation. 10 11 **Hint 2** 12 13 Have you ever watched a game of tennis, a game of volleyball, e.t.c? 14 15 **Tutorial** 16 17 Tutorial is loading... 18 19 **Solution** 20 21 [231849364](/contest/1894/submission/231849364 "Submission 231849364 by sevlll777") 22 23 ``` 24 #include <bits/stdc++.h> 25 26 using namespace std; 27 28 void solve() { 29 int n; 30 cin >> n; 31 string s; 32 cin >> s; 33 cout << s.back() << '\n'; 34 } 35 36 signed main() { 37 ios::sync_with_stdio(false); 38 cin.tie(nullptr); 39 cout.tie(nullptr); 40 int t; 41 cin >> t; 42 while (t--) { 43 solve(); 44 } 45 } 46 ``` 47 48 **Rate the problem** 49 50 * Didnt solve 51 * Good problem 52 * Average problem 53 * Bad problem 54 * tROlll pRoBlEm 55 56 [1894B - Two Out of Three](/contest/1894/problem/B "Codeforces Round 908 (Div. 2)") 57 58 **Hint 1** 59 60 Everything is symmetrical, so you can fix beforehand any exact two conditions you are aimed to satisfy. 61 62 **Hint 2** 63 64 You need to not satisfy $3$rd condition, so it doesnt really make sense to color any elements that not used in satisfying conditions $1$ and $2$ in colors $b_i = 2, b_i = 3$. And to satisfy conditions $1$ and $2$ one element is enough. 65 66 **Tutorial** 67 68 Tutorial is loading... 69 70 **Solution** 71 72 [231849397](/contest/1894/submission/231849397 "Submission 231849397 by sevlll777") 73 74 ``` 75 #include <bits/stdc++.h> 76 77 using namespace std; 78 const int N = 100; 79 80 void solve() { 81 int n; 82 cin >> n; 83 vector<int> a(n); 84 for (int i = 0; i < n; i++) { 85 cin >> a[i]; 86 } 87 vector<int> b(n, 1); 88 vector<vector<int>> inds(N + 1); 89 for (int i = 0; i < n; i++) { 90 inds[a[i]].push_back(i); 91 } 92 int k = 2; 93 for (int x = 1; x <= N; x++) { 94 if ((int) inds[x].size() >= 2) { 95 b[inds[x][0]] = k; 96 k++; 97 if (k > 3) { 98 break; 99 } 100 } 101 } 102 if (k <= 3) { 103 cout << "-1\n"; 104 } else { 105 for (int i = 0; i < n; i++) { 106 cout << b[i] << ' '; 107 } 108 cout << '\n'; 109 } 110 } 111 112 signed main() { 113 ios::sync_with_stdio(false); 114 cin.tie(nullptr); 115 cout.tie(nullptr); 116 int t; 117 cin >> t; 118 while (t--) { 119 solve(); 120 } 121 } 122 ``` 123 124 **Rate the problem** 125 126 * Didnt solve 127 * Good problem 128 * Average problem 129 * Bad problem 130 131 [1893A - Anonymous Informant](/contest/1893/problem/A "Codeforces Round 908 (Div. 1)") 132 133 **Hint 1** 134 135 How to rollback one operation? Is rollback uniquely determined? 136 137 **Hint 1.1** 138 139 Of course it is. 140 141 **Hint 2** 142 143 After performing operation $a_x = x$ always becomes a last element of array. 144 145 **Tutorial** 146 147 Tutorial is loading... 148 149 **Solution** 150 151 [231849420](/contest/1893/submission/231849420 "Submission 231849420 by sevlll777") 152 153 ``` 154 #include <bits/stdc++.h> 155 156 using namespace std; 157 158 void solve() { 159 int n, k; 160 cin >> n >> k; 161 vector<int> a(n); 162 for (int i = 0; i < n; i++) { 163 cin >> a[i]; 164 } 165 k = min(k, n); 166 int last = n - 1; 167 for (int _ = 0; _ < k; _++) { 168 if (a[last] > n) { 169 cout << "No\n"; 170 return; 171 } 172 last += n - a[last]; 173 if (last >= n) { 174 last -= n; 175 } 176 } 177 cout << "Yes\n"; 178 } 179 180 signed main() { 181 ios::sync_with_stdio(false); 182 cin.tie(nullptr); 183 cout.tie(nullptr); 184 int t; 185 cin >> t; 186 while (t--) { 187 solve(); 188 } 189 } 190 ``` 191 192 **Rate the problem** 193 194 * Didnt solve 195 * Good problem 196 * Average problem 197 * Bad problem 198 199 [1893B - Neutral Tonality](/contest/1893/problem/B "Codeforces Round 908 (Div. 1)") 200 201 **Hint 1** 202 203 Lower bound for answer: $LIS(a)$ 204 205 **Hint 2** 206 207 Upper bound for answer: $LIS(a)+1$, you can insert $b$'s in decreasing order anywhere. When you can't achieve $LIS(a)$? 208 209 **Hint 3** 210 211 Solve for $m = 1$ 212 213 **Tutorial** 214 215 Tutorial is loading... 216 217 **Solution** 218 219 [231849445](/contest/1893/submission/231849445 "Submission 231849445 by sevlll777") 220 221 ``` 222 #include <bits/stdc++.h> 223 224 #define pb push_back 225 #define all(x) x.begin(), (x).end() 226 #define rall(x) x.rbegin(), (x).rend() 227 using namespace std; 228 229 void solve() { 230 int n, m; 231 cin >> n >> m; 232 vector<int> a(n), b(m), c(n + m); 233 for (int i = 0; i < n; i++) { 234 cin >> a[i]; 235 } 236 for (int i = 0; i < m; i++) { 237 cin >> b[i]; 238 } 239 sort(rall(b)); 240 merge(all(a), all(b), c.begin(), greater<int>()); 241 for (int i = 0; i < n + m; i++) { 242 cout << c[i] << ' '; 243 } 244 cout << '\n'; 245 } 246 247 signed main() { 248 ios::sync_with_stdio(false); 249 cin.tie(nullptr); 250 cout.tie(nullptr); 251 int t; 252 cin >> t; 253 while (t--) { 254 solve(); 255 } 256 } 257 ``` 258 259 **Rate the problem** 260 261 * Didnt solve 262 * Good problem 263 * Average problem 264 * Bad problem 265 266 [1893C - Freedom of Choice](/contest/1893/problem/C "Codeforces Round 908 (Div. 1)") 267 268 **Hint 1** 269 270 It makes sense to try to solve case $m = 1$ first, to get general understanding of the problem, some observations will be usefull in full solution. 271 272 **Hint 1.1** 273 274 What size can a multiset $X$ have? 275 276 **Hint 1.2** 277 278 If $r - l \gt n$, the answer to the problem is $0$. Now we are left in the case of $r - l \leq n$. So we can iterate over all sizes from $l$ to $r$, for each of them find the minimum anti-beauty that can have a set of this size, and take the minimum of all this for the answer. 279 280 **Hint 2** 281 282 For bigger $m$ you need to find a fast enough way to count minimal anti-beauty with fixed size, everything else remains the same. 283 284 **Tutorial** 285 286 Tutorial is loading... 287 288 **Solution** 289 290 [231849477](/contest/1893/submission/231849477 "Submission 231849477 by sevlll777") 291 292 ``` 293 #include <bits/stdc++.h> 294 295 #define pb push_back 296 #define int long long 297 #define all(x) x.begin(), (x).end() 298 using namespace std; 299 300 void solve() { 301 int m; 302 cin >> m; 303 vector<int> n(m), l(m), r(m); 304 vector<vector<int>> a(m); 305 vector<vector<int>> c(m); 306 vector<int> sumc(m); 307 int suml = 0, sumr = 0, sumn = 0; 308 for (int i = 0; i < m; i++) { 309 cin >> n[i] >> l[i] >> r[i]; 310 sumn += n[i]; 311 suml += l[i]; 312 sumr += r[i]; 313 a[i].resize(n[i]); 314 for (int j = 0; j < n[i]; j++) { 315 cin >> a[i][j]; 316 } 317 c[i].resize(n[i]); 318 for (int j = 0; j < n[i]; j++) { 319 cin >> c[i][j]; 320 sumc[i] += c[i][j]; 321 } 322 } 323 324 if (sumr - suml > sumn) { 325 cout << "0\n"; 326 return; 327 } 328 329 map<int, int> sumr_a; 330 map<int, vector<pair<int, int>>> indexes; 331 for (int i = 0; i < m; i++) { 332 for (int j = 0; j < n[i]; j++) { 333 sumr_a[a[i][j]] += r[i]; 334 indexes[a[i][j]].pb({i, j}); 335 } 336 } 337 338 int ans = (int) 2e18; 339 for (int len = suml; len <= sumr; len++) { 340 int xsize = 0, must_len = 0; 341 xsize += sumr - sumr_a[len]; 342 for (auto &[i, pos] : indexes[len]) { 343 int cnt_not_len = sumc[i] - c[i][pos]; 344 if (cnt_not_len < l[i]) { 345 xsize += l[i]; 346 must_len += l[i] - cnt_not_len; 347 } else { 348 xsize += min(cnt_not_len, r[i]); 349 } 350 } 351 ans = min(ans, must_len + max(0LL, len - xsize)); 352 } 353 cout << ans << '\n'; 354 } 355 356 signed main() { 357 ios::sync_with_stdio(false); 358 cin.tie(nullptr); 359 cout.tie(nullptr); 360 int t; 361 cin >> t; 362 while (t--) { 363 solve(); 364 } 365 } 366 ``` 367 368 **Rate the problem** 369 370 * Didnt solve 371 * Good problem 372 * Average problem 373 * Bad problem 374 375 [1893D - Colorful Constructive](/contest/1893/problem/D "Codeforces Round 908 (Div. 1)") 376 377 **Hints: Natural Way** 378 379 **Hint 1** 380 381 Solve the problem if $s_i = d_i$ for all $i$. 382 383 **Hint 1.1** 384 385 Simple greedy should work. 386 387 **Hint 2** 388 389 Solve the problem if $s_i = 2 \cdot d_i$ for all $i$. 390 391 **Hint 3** 392 393 Solve the problem if $d_i$ divides $s_i$ for all $i$. 394 395 **Hint 4** 396 397 You can treat remainder $(s_i \mod d_i)$ separately, as an individual shelf. 398 399 **Hints: Believers Way** 400 401 **Hint -1** 402 403 What is the most obvious greedy you can do? 404 405 **Hint -2** 406 407 What is the second most obvious greedy you can do? 408 409 **Hint -3** 410 411 What is the third most obvious greedy you can do? 412 413 **Hint -4** 414 415 It's probably correct at this point, just proof by AC! 416 417 **Tutorial** 418 419 Tutorial is loading... 420 421 **Solution** 422 423 [231849510](/contest/1893/submission/231849510 "Submission 231849510 by sevlll777") 424 425 ``` 426 #include <bits/stdc++.h> 427 428 #define pb push_back 429 #define all(x) x.begin(), (x).end() 430 #define rall(x) x.rbegin(), (x).rend() 431 using namespace std; 432 433 void solve() { 434 int n, m; 435 cin >> n >> m; 436 vector<int> a(n); 437 for (int i = 0; i < n; i++) { 438 cin >> a[i]; 439 } 440 vector<int> s(m), d(m); 441 for (int i = 0; i < m; i++) { 442 cin >> s[i]; 443 } 444 for (int i = 0; i < m; i++) { 445 cin >> d[i]; 446 } 447 vector<int> cnt(n + 1); 448 for (int i = 0; i < n; i++) { 449 cnt[a[i]]++; 450 } 451 452 set<pair<int, int>> cubes; 453 for (int x = 1; x <= n; x++) { 454 if (cnt[x] == 0) continue; 455 cubes.insert({cnt[x], x}); 456 } 457 458 vector<vector<int>> ans(m); 459 460 for (int i = 0; i < m; i++) { 461 ans[i].assign(s[i], 0); 462 for (int j = 0; j < s[i]; j++) { 463 if (j >= d[i]) { 464 if (cnt[ans[i][j - d[i]]] > 0) { 465 cubes.insert({cnt[ans[i][j - d[i]]], ans[i][j - d[i]]}); 466 } 467 } 468 if (cubes.empty()) { 469 cout << "-1\n"; 470 return; 471 } 472 ans[i][j] = (*cubes.rbegin()).second; 473 cubes.erase(*cubes.rbegin()); 474 cnt[ans[i][j]]--; 475 } 476 for (int j = s[i]; j < s[i] + d[i]; j++) { 477 if (cnt[ans[i][j - d[i]]] > 0) { 478 cubes.insert({cnt[ans[i][j - d[i]]], ans[i][j - d[i]]}); 479 } 480 } 481 } 482 483 for (int i = 0; i < m; i++) { 484 for (int j = 0; j < s[i]; j++) { 485 cout << ans[i][j] << ' '; 486 } 487 cout << '\n'; 488 } 489 490 } 491 492 493 signed main() { 494 ios::sync_with_stdio(false); 495 cin.tie(nullptr); 496 cout.tie(nullptr); 497 int t; 498 cin >> t; 499 while (t--) { 500 solve(); 501 } 502 } 503 ``` 504 505 **Rate the problem** 506 507 * Didnt solve 508 * Good problem 509 * Average problem 510 * Bad problem 511 512 [1893E - Cacti Symphony](/contest/1893/problem/E "Codeforces Round 908 (Div. 1)") 513 514 **Hint 1** 515 516 Cacti is a trap, don't think about it for now, it will help later. 517 518 **Hint 2** 519 520 Well, you need to make some observations. Start with observations about determining edges weights, it seems reasonable because edge always have exactly $2$ adjacent vertices. 521 522 **Hint 3** 523 524 Edge is good <=> Exactly one of the adjacent vertexes have a same weight as an edge. 525 526 **Hint 4** 527 528 Direct edges, such that every edge goes from vertex with same weight as edge to another vertex. In this reality try to find easier equivalent condition for ``vertice is good``. 529 530 **Hint 5** 531 532 Vertex is good <=> InDegree of vertex is an odd integer. 533 534 **Hint 6** 535 536 Now you just have two separate problems: 1) Direct all edges, such that InDegree of each vertex is odd; 2) Color all vertexes in 3 colors such that any 2 adjacent vertexes have different color. Time to remember about cacti. 537 538 **Tutorial** 539 540 Tutorial is loading... 541 542 **Solution** 543 544 [231849553](/contest/1893/submission/231849553 "Submission 231849553 by sevlll777") 545 546 ``` 547 #include <bits/stdc++.h> 548 549 typedef long long ll; 550 #define pb push_back 551 552 using namespace std; 553 554 const int M = 998244353; 555 const int N = 500500; 556 vector<pair<int, int>> g[N]; 557 set<int> bridgesV[N]; 558 bitset<N> used; 559 int h[N], d[N]; 560 ll bridges = 0; 561 ll solo = 0; 562 563 int binpow(ll a, ll x) { 564 ll ans = 1; 565 while (x) { 566 if (x % 2) { 567 ans *= a; 568 ans %= M; 569 } 570 a *= a; 571 a %= M; 572 x /= 2; 573 } 574 return (int) ans; 575 } 576 577 void dfs(int v, int p = -1) { 578 if (p != -1) { 579 d[v] = h[p] + 1; 580 h[v] = h[p] + 1; 581 } 582 used[v] = true; 583 for (auto &[u, w] : g[v]) { 584 if (u == p) continue; 585 if (!used[u]) { 586 dfs(u, v); 587 d[v] = min(d[v], d[u]); 588 if (h[v] < d[u]) { 589 bridgesV[v].insert(u); 590 bridgesV[u].insert(v); 591 bridges += w + 1; 592 solo += w; 593 } 594 } else { 595 d[v] = min(d[v], h[u]); 596 } 597 } 598 } 599 600 int calc_dp(ll n) { 601 n %= (M - 1); 602 if (n == 1) return 3; 603 if (n == 2) return 0; 604 int val = binpow(2, n); 605 if (n % 2 == 1) { 606 val += M - 2; 607 } else { 608 val += 2; 609 } 610 val %= M; 611 return val; 612 } 613 614 signed main() { 615 ios::sync_with_stdio(false); 616 cin.tie(nullptr); 617 cout.tie(nullptr); 618 int n, m; 619 cin >> n >> m; 620 for (int i = 0; i < m; i++) { 621 int a, b, w; 622 cin >> a >> b >> w; 623 a--; 624 b--; 625 g[a].pb({b, w}); 626 g[b].pb({a, w}); 627 } 628 if (n % 2 != m % 2) { 629 cout << "0\n"; 630 return 0; 631 } 632 dfs(0); 633 used.reset(); 634 635 ll ans = 1; 636 for (int v = 0; v < n; v++) { 637 if (!used[v]) { 638 ll cs = 0; 639 vector<int> q = {v}; 640 used[v] = true; 641 while (!q.empty()) { 642 int u = q.back(); 643 q.pop_back(); 644 for (auto &[uu, w] : g[u]) { 645 if (bridgesV[u].find(uu) != bridgesV[u].end()) continue; 646 cs += w + 1; 647 if (!used[uu]) { 648 used[uu] = true; 649 q.pb(uu); 650 } 651 } 652 } 653 cs /= 2; 654 cs = max(cs, 1LL); 655 ans *= calc_dp(cs); 656 ans %= M; 657 } 658 } 659 ans *= binpow(3, solo); 660 ans %= M; 661 int w = (2 * binpow(3, M - 2)) % M; 662 ans *= binpow(w, bridges); 663 ans %= M; 664 int cycles = (m + 1) - n; 665 ans *= binpow(2, cycles); 666 ans %= M; 667 cout << ans << '\n'; 668 } 669 ``` 670 671 **Rate the problem** 672 673 * Didnt solve 674 * Good problem 675 * Average problem 676 * Bad problem