92109.md (16301B)
1 Source: https://codeforces.com/blog/entry/158572 2 3 Thank you everyone for participating in the round! We hope you enjoyed the problems :) 4 5 ### [2280A - Are They the Same?](/contest/2280/problem/A "Codeforces Round 1133 (Div. 2)") 6 7 Problem author: [conqueror_of_tourist](/profile/conqueror_of_tourist "International Grandmaster conqueror_of_tourist") 8 9 **Hint** 10 11 What happens when $k$ is even? What happens when $k$ is odd? 12 13 **Solution** 14 15 Tutorial is loading... 16 17 **Code** 18 19 ``` 20 for _ in range(int(input())): 21 n, k = list(map(int, input().split())) 22 a = list(map(lambda x: int(x) % 2, input().split())) 23 b = list(map(lambda x: int(x) % 2, input().split())) 24 25 if k % 2 == 0: 26 print("YES" if a.count(0) <= b.count(0) else "NO") 27 else: 28 print("YES" if b.count(0) <= a.count(0) else "NO") 29 ``` 30 31 ### [2280B - Secret String Patterns](/contest/2280/problem/B "Codeforces Round 1133 (Div. 2)") 32 33 Problem author: [applepi216](/profile/applepi216 "Master applepi216") 34 35 **Hint** 36 37 What must all strings whose answer is ``NO'' look like? 38 39 **Solution** 40 41 Tutorial is loading... 42 43 **Code** 44 45 ``` 46 import sys 47 48 for _ in range(int(input())): 49 n = int(input()) 50 print("?", 1, n) 51 sys.stdout.flush() 52 ct = int(input()) 53 if ct == 0: 54 print("! NO") 55 continue 56 print("?", 1, ct) 57 sys.stdout.flush() 58 x = int(input()) 59 if x == ct: 60 print("! NO") 61 else: 62 print("! YES") 63 ``` 64 65 ### [2279A - Reverse and Double](/contest/2279/problem/A "Codeforces Round 1133 (Div. 1)") 66 67 Problem author: [conqueror_of_tourist](/profile/conqueror_of_tourist "International Grandmaster conqueror_of_tourist") 68 69 **Hint 1** 70 71 Where is it useful to "cut" the array to decrease the gap value? 72 73 **Hint 2** 74 75 Consider separately the cases where the gap value is unique, occurs twice, and occurs three or more times. 76 77 **Solution** 78 79 Tutorial is loading... 80 81 **Code** 82 83 ``` 84 #include <bits/stdc++.h> 85 using namespace std; 86 87 template <class T, T (*f)(T, T), T (*unit)()> struct Seg { 88 vector<T> s; int n; 89 Seg(int n = 0, T def = unit()) : s(2*n, def), n(n) {} 90 void update(int pos, T val) { 91 for (s[pos += n] = val; pos /= 2;) 92 s[pos] = f(s[pos * 2], s[pos * 2 + 1]); 93 } 94 T query(int b, int e) { // query [b, e) 95 T ra = unit(), rb = unit(); 96 for (b += n, e += n; b < e; b /= 2, e /= 2) { 97 if (b % 2) ra = f(ra, s[b++]); 98 if (e % 2) rb = f(s[--e], rb); 99 } 100 return f(ra, rb); 101 } 102 103 T get(int x) { return s[x+n]; } 104 }; 105 106 using T = int; 107 T f(T a, T b) { return max(a, b); } 108 T unit() { return 0; } 109 110 int main() { 111 cin.tie(0)->sync_with_stdio(0); 112 113 int t; cin >> t; 114 while (t--) { 115 int n; cin >> n; 116 vector<int> a(n); 117 for (int i = 0; i < n; i++) cin >> a[i]; 118 119 Seg<T, f, unit> rmq(n - 1); 120 vector<int> mx; 121 int val = -1; 122 for (int i = 0; i < n - 1; i++) { 123 rmq.update(i, abs(a[i + 1] - a[i])); 124 if (abs(a[i + 1] - a[i]) > val) 125 mx = {i}, val = abs(a[i + 1] - a[i]); 126 else if (abs(a[i + 1] - a[i]) == val) 127 mx.push_back(i); 128 } 129 130 if (mx.size() >= 3) { 131 cout << val << "\n"; 132 continue; 133 } 134 135 auto calc = [&](int i, int j) { 136 int v2 = 2 * rmq.query(i, j); 137 if (i > 0) v2 = max({v2, rmq.query(0, i - 1), abs(a[i - 1] - 2 * a[j])}); 138 if (j < n - 1) v2 = max({v2, rmq.query(j + 1, n - 1), abs(a[j + 1] - 2 * a[i])}); 139 return v2; 140 }; 141 142 if (mx.size() == 2) { 143 int i = mx[0], j = mx[1]; 144 cout << min(val, calc(i + 1, j)) << "\n"; 145 continue; 146 } 147 148 int i = mx[0]; 149 for (int j = 0; j <= i; j++) { 150 val = min(val, calc(j, i)); 151 } 152 for (int j = i + 1; j < n; j++) { 153 val = min(val, calc(i + 1, j)); 154 } 155 156 cout << val << "\n"; 157 } 158 } 159 ``` 160 161 ### [2279B - Balanced Subsets](/contest/2279/problem/B "Codeforces Round 1133 (Div. 1)") 162 163 Problem author: [conqueror_of_tourist](/profile/conqueror_of_tourist "International Grandmaster conqueror_of_tourist") 164 165 **Hint 1** 166 167 Suppose that $|S|\ge 2$. Can you say anything about the *minimum* number of unstable elements in it? 168 169 **Hint 2** 170 171 Consider DP. 172 173 **Solution** 174 175 Tutorial is loading... 176 177 **Code** 178 179 ``` 180 #include <bits/stdc++.h> 181 using namespace std; 182 183 using ll = long long; 184 #define rep(i, a, b) for(int i = a; i < (b); ++i) 185 #define all(x) (x).begin(), (x).end() 186 #define sz(x) (int)(x).size() 187 188 const ll MOD = 998244353; 189 190 mt19937 rng(time(0)); 191 192 int main() { 193 cin.tie(0)->sync_with_stdio(0); 194 195 int t; cin >> t; 196 while (t--) { 197 int n; cin >> n; 198 vector<int> a(n); 199 rep(i,0,n) cin >> a[i]; 200 201 vector<bool> s; 202 s.push_back(true); 203 for (int i = 1; i < n; i++) { 204 if (a[i] == a[i - 1] + 1) { 205 s.push_back(1); 206 } else if (a[i] == a[i - 1] + 2) { 207 s.push_back(0); s.push_back(1); 208 } else { 209 s.push_back(0); s.push_back(0); s.push_back(1); 210 } 211 } 212 s.push_back(0); 213 214 int m = sz(s); 215 assert(m < 3 * n); 216 ll ans = (1ll * (n + 1) * n / 2) % MOD; // n + (n C 2) 217 vector<ll> dp1(m + 1, 1); // ((1110)|(110))* 218 vector<ll> dp2(m + 1, 0); // 10((1110)|(110))* 219 for (int i = 1; i < m; i++) { 220 if (s[i - 1]) dp2[i + 1] = 1; 221 if (i >= 2 && s[i - 1] && s[i - 2]) { 222 dp1[i + 1] += dp1[i - 2]; 223 dp2[i + 1] += dp2[i - 2]; 224 } 225 if (i >= 3 && s[i - 1] && s[i - 2] && s[i - 3]) { 226 dp1[i + 1] += dp1[i - 3]; 227 dp2[i + 1] += dp2[i - 3]; 228 } 229 dp1[i + 1] %= MOD; 230 dp2[i + 1] %= MOD; 231 ans += dp1[i + 1] - 1 + dp2[i + 1]; 232 } 233 for (int i = 1; i < m; i++) { 234 if (s[i - 1]) { // can end in 10 235 ans += dp1[i - 1] + dp2[i - 1]; 236 } 237 } 238 s.push_back(0); s.push_back(0); 239 // we've overcounted 2 * 10, 110, 101 substrings 240 for (int i = 0; i < m; i++) { 241 if (s[i]) ans -= 2; 242 if (s[i] && s[i + 1]) ans -= 1; 243 if (s[i] && s[i + 2]) ans -= 1; 244 } 245 246 cout << ((ans + MOD) % MOD) << "\n"; 247 248 } 249 250 } 251 ``` 252 253 ### [2279C - Anti-Productive](/contest/2279/problem/C "Codeforces Round 1133 (Div. 1)") 254 255 Problem author: [conqueror_of_tourist](/profile/conqueror_of_tourist "International Grandmaster conqueror_of_tourist") 256 257 **Hint 1** 258 259 What should the array look like after applying your operations? (Equivalently, what operations should you apply?) 260 261 **Hint 2** 262 263 Consider casing on the *second largest* element. 264 265 **Solution** 266 267 Tutorial is loading... 268 269 **Code** 270 271 ``` 272 #include <bits/stdc++.h> 273 using namespace std; 274 275 using ll = long long; 276 #define rep(i, a, b) for(int i = a; i < (b); ++i) 277 #define all(x) (x).begin(), (x).end() 278 279 int main() { 280 cin.tie(0)->sync_with_stdio(0); 281 282 int t; cin >> t; 283 while (t--) { 284 int n; ll L; cin >> n >> L; 285 vector<ll> a(n); 286 rep(i,0,n) cin >> a[i]; 287 sort(all(a)); 288 if (L == 1) { 289 cout << accumulate(all(a), 0ll) - a[n - 1] << "\n"; 290 continue; 291 } 292 if (a[n - 1] * a[n - 2] < L) { 293 cout << "0\n"; 294 continue; 295 } 296 ll x = a[n - 1]; 297 ll y = 1; 298 while ((y + 1) * (y + 1) < L) ++y; 299 int start = n - 2; 300 ll curr = 0; 301 302 auto mx = [&](ll z) { 303 if (z == 0) return 0ll; 304 return max(0ll, x - (L - 1) / z); 305 }; 306 307 while (start >= 0 && a[start] >= y) { 308 curr += (a[start] - y); 309 --start; 310 } 311 ll ans = curr + mx(y); 312 --y; 313 for (; y >= 0; --y) { 314 curr += (n - 2 - start); 315 while (start >= 0 && a[start] >= y) --start; 316 ans = min(ans, curr + mx(y)); 317 } 318 cout << ans << "\n"; 319 } 320 } 321 ``` 322 323 ### [2279D - Meta Graph](/contest/2279/problem/D "Codeforces Round 1133 (Div. 1)") 324 325 Problem author: [FlakeLCR](/profile/FlakeLCR "Master FlakeLCR") 326 327 We apologize for the weak test data on this problem. 328 329 **Hint 1** 330 331 The graph is quite huge. Do you need all of it? 332 333 **Hint 2** 334 335 Try to show that you only need to keep around $O(m + n)$ edges while preserving the shortest path. 336 337 **Solution** 338 339 Tutorial is loading... 340 341 **Code** 342 343 ``` 344 #include <bits/stdc++.h> 345 using namespace std; 346 347 #define rep(i, a, b) for(int i = a; i < (b); ++i) 348 #define all(x) (x).begin(), (x).end() 349 #define sz(x) (int)(x).size() 350 351 mt19937 rng(time(0)); 352 353 int main() { 354 cin.tie(0)->sync_with_stdio(0); 355 356 int t; cin >> t; 357 while (t--) { 358 int n, m; cin >> n >> m; 359 int w, x, y, z; cin >> w >> x >> y >> z; --w, --x, --y, --z; 360 vector<array<int, 2>> edges(m); 361 vector<array<int, 2>> v; 362 rep(i,0,n) { 363 v.push_back({w, i}); 364 v.push_back({y, i}); 365 v.push_back({i, i}); 366 } 367 368 rep(i,0,m) { 369 int a, b; cin >> a >> b; --a, --b; 370 edges[i] = {a, b}; 371 v.push_back({a, b}); 372 v.push_back({b, a}); 373 } 374 375 sort(all(v)); 376 v.resize(unique(all(v)) - v.begin()); 377 378 int N = sz(v); 379 380 auto find = [&](int i, int j) -> int { 381 return lower_bound(all(v), array{i, j}) - v.begin(); 382 }; 383 384 vector<vector<int>> h(N); 385 for (auto [a, b] : edges) { 386 int wa = find(w, a), wb = find(w, b), 387 ya = find(y, a), yb = find(y, b), 388 aa = find(a, a), ab = find(a, b), 389 ba = find(b, a), bb = find(b, b); 390 391 for (auto [p1, p2] : vector{array{wa, wb}, {ya, yb}, {aa, ab}, {ba, bb}, {ab, ba}}) { 392 h[p1].push_back(p2); 393 h[p2].push_back(p1); 394 } 395 } 396 397 vector<int> dist(N, -1); 398 queue<pair<int, int>> q; 399 q.emplace(find(w, x), 0); 400 while (!q.empty()) { 401 auto [vtx, d] = q.front(); 402 q.pop(); 403 if (dist[vtx] >= 0) continue; 404 dist[vtx] = d; 405 for (auto a : h[vtx]) { 406 if (dist[a] < 0) q.emplace(a, d + 1); 407 } 408 } 409 410 cout << dist[find(y, z)] << "\n"; 411 } 412 } 413 ``` 414 415 ### [2279E - Save Me!](/contest/2279/problem/E "Codeforces Round 1133 (Div. 1)") 416 417 Problem author: [conqueror_of_tourist](/profile/conqueror_of_tourist "International Grandmaster conqueror_of_tourist") 418 419 **Hint 1** 420 421 Can you upper bound the answer? 422 423 **Hint 2** 424 425 The answer is at most $2\cdot 25 - 1 = 49$. Can you use this fact to construct a solution running in time $O(n\cdot 2^{49})$? 426 427 **Hint 3** 428 429 Please refer to the previous hint first. Can you make your solution faster to $O(n\cdot \varphi^{49})$? 430 431 **Hint 4** 432 433 Consider Meet In The Middle. 434 435 **Solution** 436 437 Tutorial is loading... 438 439 **Code** 440 441 ``` 442 #include <bits/stdc++.h> 443 using namespace std; 444 445 #define pb push_back 446 #define eb emplace_back 447 #define mp make_pair 448 #define all(v) v.begin(), v.end() 449 #define sz(v) (int)v.size() 450 #define sq(a) ((a)*(a)) 451 452 #define per(i,a,b) for (int i = (b)-1; i >= a; i--) 453 #define rep(i,a,b) for (int i=a; i<b; i++) 454 455 #define FOR(i,a,b) for (int i=a; i<b; i++) 456 #define F0R(i,a) for (int i=0; i<a; i++) 457 #define ROF(i,a,b) for (int i = (b)-1; i >= a; i--) 458 #define R0F(i,a) for (int i = (a)-1; i >= 0; i--) 459 460 #define FAST ios::sync_with_stdio(0); cin.tie(0); 461 #define finish(x) return cout << x << endl, 0; 462 #define dbg(x) cerr << ">>> " << #x << " = " << x << endl; 463 #define _ << " _ " << 464 465 #define ll long long 466 467 template<class T> bool ckmin(T&a, T&b) { bool B = a > b; a = min(a,b); return B; } 468 template<class T> bool ckmax(T&a, T&b) { bool B = a < b; a = max(a,b); return B; } 469 470 typedef long double ld; 471 typedef pair<int,int> pi; 472 typedef pair<ld,ld> pld; 473 typedef complex<ld> cd; 474 475 typedef vector<int> vi; 476 typedef vector<ld> vld; 477 typedef vector<vector<int>> vvi; 478 479 const ld PI = acos(-1.0); 480 const ld EPS = 1e-7; 481 const int MOD = 998244353; 482 483 const int MX = 25; 484 const int BIG = 100; 485 486 void solve() { 487 int n; cin >> n; 488 vector<int> a(n); 489 rep(i, 0, n) { 490 cin >> a[i]; 491 } 492 493 if (*min_element(all(a)) == 0) { 494 cout << "0" << "\n"; 495 return; 496 } 497 498 vector<pair<int, int>> seen; 499 500 auto left = [&](auto && self, int i, int cost, int v) { 501 int op = v ^ a[i]; 502 seen.push_back({op, cost}); 503 504 if (i == 0) return; 505 if (cost + 1 <= MX) { 506 self(self, i - 1, cost + 1, op); 507 } 508 509 if (cost + 2 <= MX) { 510 self(self, i - 1, cost + 2, v); 511 } 512 }; 513 514 int best = BIG; 515 516 auto right = [&](auto && self, int i, int cost, int v) { 517 int op = v ^ a[i]; 518 519 auto it = upper_bound(all(seen), mp(op, -1)); 520 if (it != seen.end()) { 521 auto [u, v] = *it; 522 if (u == op) best = min(best, cost + v - 1); 523 } 524 525 if (i + 1 == n) return; 526 if (cost + 1 <= MX) { 527 self(self, i + 1, cost + 1, op); 528 } 529 530 if (cost + 2 <= MX) { 531 self(self, i + 1, cost + 2, v); 532 } 533 }; 534 535 if (n > MX) { 536 best = 2 * MX - 1; 537 } 538 539 rep(i, 0, n - 1) { 540 seen.clear(); 541 seen.reserve(514228); 542 543 left(left, i, 1, 0); 544 assert (sz(seen) <= 514228); 545 sort(all(seen)); 546 547 right(right, i + 1, 1, 0); 548 } 549 550 if (best == BIG) best = -1; 551 cout << best << endl; 552 } 553 554 int32_t main() { FAST 555 int t; 556 cin >> t; 557 558 while (t--) solve(); 559 560 return 0; 561 } 562 ``` 563 564 ### [2279F - The Stones of Nim](/contest/2279/problem/F "Codeforces Round 1133 (Div. 1)") 565 566 Problem author: [applepi216](/profile/applepi216 "Master applepi216") 567 568 **Hint 1** 569 570 Recall how one wins in Nim. Next, note that this problem essentially reduces to solving each prefix quickly. 571 572 **Hint 2** 573 574 This is, under the hood, a matroid problem. For each new value, try to construct an "exchange" graph using the matroid basis exchange property to determine if it's possible to insert the element. 575 576 **Hint 3** 577 578 Please refer to the previous hint first. It gives an $O(n^3\log^2 n)$ time algorithm. To improve this, consider if you need the full graph or if you can "thin" it. 579 580 **Hint 4** 581 582 Make sure your XOR basis operations are of optimal complexity. 583 584 **Solution** 585 586 Tutorial is loading... 587 588 **Code** 589 590 ``` 591 #include <bits/stdc++.h> 592 using namespace std; 593 594 constexpr int LOG = 14; 595 596 struct xor_basis { 597 vector<int> inner; 598 vector<int> base; 599 vector<int> comb; 600 601 xor_basis(): base(LOG), comb(LOG) {} 602 603 int represent(int mask) { 604 int c = 0; 605 for (int i = 0; i < LOG; i++) { 606 if (!(mask & (1 << i))) continue; 607 if (!base[i]) return -1; 608 mask ^= base[i], c ^= comb[i]; 609 } 610 return c; 611 } 612 613 bool independent(int mask) { 614 for (int i = 0; i < LOG; i++) { 615 if (!(mask & (1 << i))) continue; 616 if (!base[i]) return true; 617 mask ^= base[i]; 618 } 619 return false; 620 } 621 622 void swap(int out, int in) { 623 int pos = find(inner.begin(), inner.end(), out) - inner.begin(); 624 int c = represent(in); 625 inner[pos] = in; 626 for (int i = 0; i < LOG; i++) if (comb[i] >> pos & 1) comb[i] ^= c ^ (1 << pos); 627 } 628 629 bool insert(int mask) { 630 int sv = mask, c = 1 << inner.size(); 631 for (int i = 0; i < LOG; i++) { 632 if (!(mask & (1 << i))) continue; 633 634 if (!base[i]) { 635 base[i] = mask, comb[i] = c, inner.push_back(sv); 636 return true; 637 } 638 mask ^= base[i], c ^= comb[i]; 639 } 640 return false; 641 } 642 }; 643 644 void solve() { 645 int n; cin >> n; 646 vector<int> a(n), s(n); 647 for (int i = 0; i < n; i++) cin >> a[i]; 648 649 vector<xor_basis> bases; 650 bases.emplace_back(); 651 652 auto add = [&](int idx) { 653 for (int i = 0; i < bases.size(); i++) { 654 if (bases[i].independent(s[idx])) { 655 bases[i].insert(s[idx]); // special case 656 return; 657 } 658 } 659 660 int N = 2*n + bases.size(); 661 662 vector<int> smap(N, -1); 663 for (int i = 0; i < bases.size(); i++) for (auto x : bases[i].inner) smap[x - 1] = i; 664 for (int i = 0; i < bases.size(); i++) smap[i + 2*n] = i; 665 666 vector<int> par(N, -2); 667 vector<int> q; 668 q.push_back(s[idx] - 1); par[s[idx] - 1] = -1; 669 int found = -1; 670 for (int head = 0; head < q.size(); head++) { 671 int vtx = q[head]; 672 673 int x = vtx + 1, next_idx = (smap[vtx] + 1) % bases.size(); 674 675 if (x == s[idx] || bases.size() > 1) { 676 if (bases[next_idx].independent(x)) { 677 par[2 * n + next_idx] = vtx, found = 2 * n + next_idx; 678 break; 679 } 680 int z = bases[next_idx].represent(x); 681 for (int p = 0; p < bases[next_idx].inner.size(); p++) { 682 if (z >> p & 1) { 683 int y = bases[next_idx].inner[p] - 1; 684 if (par[y] == -2) par[y] = vtx, q.push_back(y); 685 } 686 } 687 } 688 } 689 690 if (found < 0) { // easy case -- no path 691 bases.emplace_back(); 692 bases.back().insert(s[idx]); 693 return; 694 } else { 695 int p = par[found]; 696 assert(bases[smap[found]].insert(p + 1)); 697 while (p + 1 != s[idx]) { 698 int prev = par[p]; 699 bases[smap[p]].swap(p + 1, prev + 1); 700 p = prev; 701 } 702 } 703 }; 704 705 auto print_sol = [&]() { 706 cout << bases.size() << "\n"; 707 for (const auto& base : bases) { 708 cout << base.inner.size(); 709 for (auto x : base.inner) { 710 cout << " " << x; 711 } 712 cout << "\n"; 713 } 714 }; 715 716 for (int i = 0; i < n; i++) { 717 int k = (i == 0 ? 0 : bases.size()); 718 s[i] = a[i] ^ k; 719 add(i); 720 } 721 print_sol(); 722 } 723 724 int main() { 725 cin.tie(0)->sync_with_stdio(0); 726 727 int t; cin >> t; 728 while (t--) solve(); 729 } 730 ```