2262.md (34082B)
1 Source: https://codeforces.com/blog/entry/156688 2 3 Thank you to everyone who participated! 4 5 We are sorry for the poor testcases on C1, along with C1 and C2's solutions being so similar to the recent Div3 E. 6 7 [2263A - Min Max Game](/contest/2263/problem/A "Codeforces Round 1120 (Div. 2)") 8 9 Author: [kondasujay2](/profile/kondasujay2 "International Master kondasujay2") 10 11 **Tutorial** 12 13 Tutorial is loading... 14 15 **Solution** 16 17 ``` 18 #include <bits/stdc++.h> 19 using namespace std; 20 21 void tc() { 22 int n; cin >> n; 23 int cnt = 0; 24 vector<int> a(n); 25 for(int i = 0; i < n; i++) { 26 cin >> a[i]; 27 cnt += a[i]; 28 } 29 if(cnt >= n - cnt) { 30 cout << "Bessie\n"; 31 } else { 32 cout << "Elsie\n"; 33 } 34 } 35 36 int main() { 37 ios::sync_with_stdio(false), cin.tie(nullptr); 38 int t; cin >> t; 39 while(t--) tc(); 40 } 41 ``` 42 43 **Rate the problem** 44 45 * Amazing: 46 * Good: 47 * Ok: 48 * Bad: 49 * Terrible: 50 51 [2263B - Min Matrices](/contest/2263/problem/B "Codeforces Round 1120 (Div. 2)") 52 53 Author: [sukon](/profile/sukon "Candidate Master sukon") 54 55 **Tutorial** 56 57 Tutorial is loading... 58 59 **Solution** 60 61 ``` 62 #include<bits/stdc++.h> 63 64 using namespace std; 65 66 void solve() { 67 int n, k; cin >> n >> k; 68 int x = k-n+1; 69 if(!(1 <= x && x <= n)) { cout << -1; return; } 70 vector<vector<int>> ans(n, vector<int>(n)); 71 ans[0][0] = 1; 72 int on = 2; 73 for(int i = 1; i < x; i++) { 74 ans[0][i] = on; on++; 75 ans[i][0] = on; on++; 76 } 77 for(int i = x; i < n; i++) { 78 ans[i][i] = on; on++; 79 } 80 81 for(int i = 0; i < n; i++) { 82 for(int j = 0; j < n; j++) { 83 if(!ans[i][j]) { 84 ans[i][j] = on; on++; 85 } 86 } 87 } 88 89 for(int j = 0; j < n; j++) { 90 if(j) cout << "\n"; 91 for(auto &i : ans[j]) cout << i << " "; 92 } 93 } 94 95 int main() { 96 ios::sync_with_stdio(false); 97 cin.tie(nullptr); 98 int t; cin >> t; 99 while(t--) { 100 solve(); 101 if(t) cout << "\n"; 102 } 103 } 104 ``` 105 106 **Rate the problem** 107 108 * Amazing: 109 * Good: 110 * Ok: 111 * Bad: 112 * Terrible: 113 114 [2263C1 - Floor of MEX (Easy Version)](/contest/2263/problem/C1 "Codeforces Round 1120 (Div. 2)") / [2262A1 - Floor of MEX (Easy Version)](/contest/2262/problem/A1 "Codeforces Round 1120 (Div. 1)") 115 116 Author: [CutSandstone](/profile/CutSandstone "Candidate Master CutSandstone") 117 118 **Tutorial** 119 120 Tutorial is loading... 121 122 **Solution** 123 124 ``` 125 #include <bits/stdc++.h> 126 using namespace std; 127 128 void tc() { 129 int n; cin >> n; 130 vector<int> b(n + 1); 131 for(int i = 1; i <= n; i++) cin >> b[i]; 132 vector<pair<int, int>> goodivs; 133 vector<pair<int, int>> badivs; 134 for(int i = 1; i <= n; i++) { 135 badivs.push_back({b[i] * i, (b[i] + 1) * i - 1}); 136 for(int j = 0; j < b[i]; j++) { 137 goodivs.push_back({j * i, (j + 1) * i - 1}); 138 } 139 } 140 vector<int> d(n + 1); 141 for(auto [l, r] : badivs) { 142 d[min(n, l)]++; 143 d[min(n, r + 1)]--; 144 } 145 int csm = 0; 146 vector<int> gnums; 147 for(int i = 0; i < n; i++) { 148 csm += d[i]; 149 if(csm == 0) { 150 gnums.push_back(i); 151 } 152 } 153 cout << gnums.size() << endl; 154 for(int i : gnums) cout << i << " "; 155 cout << endl; 156 } 157 158 int main() { 159 ios::sync_with_stdio(false), cin.tie(nullptr); 160 int t; cin >> t; 161 while(t--) tc(); 162 } 163 ``` 164 165 **Rate the problem** 166 167 * Amazing: 168 * Good: 169 * Ok: 170 * Bad: 171 * Terrible: 172 173 [2263C2 - Floor of MEX (Hard Version)](/contest/2263/problem/C2 "Codeforces Round 1120 (Div. 2)") / [2262A2 - Floor of MEX (Hard Version)](/contest/2262/problem/A2 "Codeforces Round 1120 (Div. 1)") 174 175 Author: [kondasujay2](/profile/kondasujay2 "International Master kondasujay2") 176 177 **Tutorial** 178 179 Tutorial is loading... 180 181 **Solution** 182 183 ``` 184 #include <bits/stdc++.h> 185 using namespace std; 186 187 const int MOD = 1e9 + 7; 188 189 void tc() { 190 int n; cin >> n; 191 vector<int> b(n + 1); 192 for(int i = 1; i <= n; i++) cin >> b[i]; 193 vector<pair<int, int>> goodivs; 194 vector<pair<int, int>> badivs; 195 for(int i = 1; i <= n; i++) { 196 if(b[i] > (n - 1) / i + 1) { 197 cout << 0 << endl; 198 return; 199 } 200 badivs.push_back({b[i] * i, (b[i] + 1) * i - 1}); 201 for(int j = 0; j < b[i]; j++) { 202 goodivs.push_back({j * i, (j + 1) * i - 1}); 203 } 204 } 205 vector<int> d(n + 1); 206 for(auto [l, r] : badivs) { 207 d[min(n, l)]++; 208 d[min(n, r + 1)]--; 209 } 210 int csm = 0; 211 vector<int> gnums; 212 for(int i = 0; i < n; i++) { 213 csm += d[i]; 214 if(csm == 0) { 215 gnums.push_back(i); 216 } 217 } 218 set<pair<int, int>> st; 219 sort(goodivs.begin(), goodivs.end(), [&] (pair<int, int> iv, pair<int, int> iv2) { 220 return iv.second - iv.first < iv2.second - iv2.first; 221 }); 222 for(auto [l, r] : goodivs) { 223 auto it = st.lower_bound({l, 0}); 224 if(it != st.end() && it->second <= r) { 225 continue; 226 } 227 st.insert({l, r}); 228 } 229 230 vector<pair<int, int>> impivs(st.begin(), st.end()); 231 int l = 0, r = 0; 232 vector<int> dp(impivs.size() + 1); 233 dp[0] = 1; 234 int poss = 1; 235 for(int i : gnums) { 236 while(l < impivs.size() && impivs[l].second < i) { 237 poss += MOD - dp[l]; 238 poss %= MOD; 239 l++; 240 } 241 while(r < impivs.size() && impivs[r].first <= i) r++; 242 dp[r] += poss; 243 dp[r] %= MOD; 244 poss += poss; 245 poss %= MOD; 246 } 247 cout << dp[impivs.size()] << endl; 248 } 249 250 int main() { 251 ios::sync_with_stdio(false), cin.tie(nullptr); 252 int t; cin >> t; 253 while(t--) tc(); 254 } 255 ``` 256 257 **Rate the problem** 258 259 * Amazing: 260 * Good: 261 * Ok: 262 * Bad: 263 * Terrible: 264 265 [2263D - Culling Game](/contest/2263/problem/D "Codeforces Round 1120 (Div. 2)") / [2262B - Culling Game](/contest/2262/problem/B "Codeforces Round 1120 (Div. 1)") 266 267 Author: [kondasujay2](/profile/kondasujay2 "International Master kondasujay2") 268 269 **Tutorial** 270 271 Tutorial is loading... 272 273 **Solution** 274 275 ``` 276 #include <bits/stdc++.h> 277 using namespace std; 278 279 using ll = long long; 280 281 struct BIT { 282 vector<ll> tr; 283 BIT(int n) : tr(n + 1) {} 284 void add(int k, ll x) { 285 while(k < tr.size()) { 286 tr[k] += x; 287 k += k&-k; 288 } 289 } 290 ll sum(int k) { 291 ll res = 0; 292 while(k > 0) { 293 res += tr[k]; 294 k -= k&-k; 295 } 296 return res; 297 } 298 }; 299 300 void tc() { 301 int n; cin >> n; 302 vector<int> a(n), p(n); 303 for(int i = 0; i < n; i++) { 304 cin >> a[i]; 305 } 306 for(int i = 0; i < n; i++) { 307 cin >> p[i]; p[i]--; 308 } 309 reverse(p.begin(), p.end()); 310 BIT bit(n); 311 set<int> imp; 312 vector<int> ans(n); 313 for(int i = 0; i < n; i++) { 314 int k = p[i]; 315 auto it = imp.upper_bound(k); 316 int pimp; 317 if(it == imp.begin() || bit.sum(k) - bit.sum(*prev(it)) < a[k]) { 318 imp.insert(k); 319 pimp = k; 320 } else { 321 pimp = *prev(it); 322 } 323 bit.add(k + 1, a[k]); 324 while(imp.upper_bound(k) != imp.end()) { 325 int j = *imp.upper_bound(k); 326 if(bit.sum(j) - bit.sum(pimp) >= a[j]) { 327 imp.erase(j); 328 } else { 329 break; 330 } 331 } 332 ans[i] = imp.size() - 1; 333 } 334 reverse(ans.begin(), ans.end()); 335 for(int i : ans) cout << i << " "; 336 cout << endl; 337 } 338 339 int main() { 340 ios::sync_with_stdio(false), cin.tie(nullptr); 341 int t; cin >> t; 342 while(t--) tc(); 343 } 344 ``` 345 346 **Rate the problem** 347 348 * Amazing: 349 * Good: 350 * Ok: 351 * Bad: 352 * Terrible: 353 354 [2263E - Traveling the World](/contest/2263/problem/E "Codeforces Round 1120 (Div. 2)") / [2262C - Traveling the World](/contest/2262/problem/C "Codeforces Round 1120 (Div. 1)") 355 356 Author: [kondasujay2](/profile/kondasujay2 "International Master kondasujay2") 357 358 **Tutorial** 359 360 Tutorial is loading... 361 362 **Solution** 363 364 ``` 365 #include <bits/stdc++.h> 366 using namespace std; 367 368 using ll = long long; 369 370 const int MOD = 1e9 + 7; 371 372 void tc() { 373 int n; cin >> n; 374 vector<ll> a(n); 375 for(int i = 0; i < n; i++) cin >> a[i]; 376 int k = n / 2; 377 378 int val = 1; 379 for(int i = 1; i <= k; i++) { 380 val = (ll)i * val % MOD; 381 } 382 for(int i = 1; i <= k - (n % 2 == 0 ? 2 : 1); i++) { 383 val = (ll)i * val % MOD; 384 } 385 386 set<ll> xposs; 387 xposs.insert(a[n - 1] - a[n - 2]); 388 xposs.insert(a[n - 1] - a[n - 3]); 389 390 int ans = 0; 391 for(ll x : xposs) { 392 vector<ll> b; 393 for(int i = 0; i < k; i++) { 394 b.push_back(i * x); 395 } 396 for(int i = 0; i < n - k; i++) { 397 b.push_back(a[n - 1] - i * x); 398 } 399 sort(b.begin(), b.end()); 400 if(a == b) { 401 ans += val; 402 if(ans >= MOD) ans -= MOD; 403 } 404 } 405 cout << ans << endl; 406 } 407 408 int main() { 409 ios::sync_with_stdio(false), cin.tie(nullptr); 410 int t; cin >> t; 411 while(t--) tc(); 412 } 413 ``` 414 415 **Rate the problem** 416 417 * Amazing: 418 * Good: 419 * Ok: 420 * Bad: 421 * Terrible: 422 423 [2263F - PLUSworld](/contest/2263/problem/F "Codeforces Round 1120 (Div. 2)") / [2262D - PLUSworld](/contest/2262/problem/D "Codeforces Round 1120 (Div. 1)") 424 425 Authors: [sukon](/profile/sukon "Candidate Master sukon") & [kondasujay2](/profile/kondasujay2 "International Master kondasujay2") 426 427 **Tutorial** 428 429 Tutorial is loading... 430 431 **Solution** 432 433 ``` 434 #include <bits/stdc++.h> 435 using namespace std; 436 437 void tc() { 438 int n; cin >> n; 439 440 vector<int> a(n), b(n); 441 for(int i = 0; i < n; i++) cin >> a[i], a[i]--; 442 for(int i = 0; i < n; i++) cin >> b[i], b[i]--; 443 444 int badcnt = 0; 445 for(int i = 0; i < n; i++) { 446 badcnt += a[i] != b[i]; 447 } 448 if(badcnt == 0) { 449 cout << "0 1\n"; 450 return; 451 } 452 453 // mark everything which will ever be reached 454 vector<bool> useful(n); 455 for(int i = 0; i < n; i++) { 456 if(a[i] == b[i]) continue; 457 int x = i; 458 while(!useful[x]) { 459 useful[x] = true; 460 x = b[x]; 461 } 462 } 463 464 // anything with b[i] == i once we reach we can't reach anything else, 465 // at most one of them can exit 466 vector<int> ends; 467 for(int i = 0; i < n; i++) { 468 if(useful[i] && b[i] == i) ends.push_back(i); 469 } 470 471 if(ends.size() > 1) { 472 cout << "-1\n"; 473 return; 474 } 475 476 vector<vector<int>> adj(n), radj(n); 477 for(int i = 0; i < n; i++) { 478 if(a[i] > b[i]) { 479 cout << "-1\n"; 480 return; 481 } 482 for(int j = a[i]; j <= b[i]; j++) { 483 adj[i].push_back(j); 484 radj[j].push_back(i); 485 } 486 } 487 488 // tarjan algorithm, from cp-algorithms 489 vector<int> st; // - stack holding the unclaimed vertices 490 vector<int> roots(n, -1); // - keeps track of the SCC roots of the vertices 491 int timer = 0; // - dfs timestamp counter 492 vector<int> t_in(n, -1); // - keeps track of the dfs timestamp of the vertices 493 vector<int> t_low(n, -1); // - keeps track of the lowest t_in of unclaimed vertices 494 // reachable in the subtree 495 496 // implements the tarjan algorithm for strongly connected components 497 auto dfs = [&](auto&& self, int s) -> void { 498 t_low[s] = t_in[s] = timer++; 499 st.push_back(s); 500 501 for (auto u : adj[s]) { 502 if (t_in[u] == -1) { // tree-edge 503 self(self, u); 504 t_low[s] = min(t_low[s], t_low[u]); 505 } else if (roots[u] == -1) { // back-edge, cross-edge or forward-edge to an unclaimed vertex 506 t_low[s] = min(t_low[s], t_in[u]); 507 } 508 } 509 510 if (t_low[s] == t_in[s]) { // vertex is a root 511 while (true) { 512 int u = st.back(); 513 st.pop_back(); 514 roots[u] = s; // claims the vertex 515 if (u == s) 516 break; 517 } 518 } 519 }; 520 521 // applies the tarjan algorithm to all the vertices 522 for (int v = 0; v < n; v++) { 523 if (t_in[v] == -1) { 524 dfs(dfs, v); 525 } 526 } 527 vector<vector<int>> comps(n); 528 for(int v = 0; v < n; v++) { 529 comps[roots[v]].push_back(v); 530 } 531 532 vector<int> p(n, -1); 533 vector<int> sz(n); 534 for(int i = 0; i < n; i++) { 535 if(a[i] != b[i]) { 536 sz[roots[i]]++; 537 } 538 if(useful[i] && roots[i] != roots[b[i]]) { 539 if(p[roots[b[i]]] != -1) { 540 cout << "-1\n"; 541 return; 542 } 543 p[roots[b[i]]] = roots[i]; 544 } 545 } 546 vector<int> chain; 547 int x = roots[ends[0]]; 548 int csz = 0; 549 while(x != -1) { 550 chain.push_back(x); 551 csz += sz[x]; 552 x = p[x]; 553 } 554 if(csz != badcnt) { 555 cout << "-1\n"; 556 return; 557 } 558 reverse(chain.begin(), chain.end()); 559 560 { 561 x = comps[chain[0]][0]; 562 vector<int> ops; 563 auto op1 = [&] () { 564 ops.push_back(1); 565 a[x]++; 566 }; 567 auto op2 = [&] () { 568 ops.push_back(2); 569 x = a[x]; 570 }; 571 auto solve_scc = [&] () { 572 int rt = roots[x]; 573 vector<int> comp = comps[rt]; 574 575 vector<int> p2(n, -1); 576 // only one thing in comp case 577 auto rdfs = [&] (auto&& self, int s) -> void { 578 for(int u : radj[s]) { 579 if(roots[u] != rt) continue; 580 if(p2[u] == -1) { 581 p2[u] = s; 582 self(self, u); 583 } 584 } 585 }; 586 587 // root a tree 588 rdfs(rdfs, comp[0]); 589 590 for(int i = 0; i < comp.size(); i++) { 591 while(x != comp[i]) { 592 while(a[x] < max(p2[x], comp[i])) op1(); 593 op2(); 594 } 595 while(a[x] < b[x]) op1(); 596 op2(); 597 } 598 }; 599 for(int i = 0; i < chain.size(); i++) solve_scc(); 600 601 cout << ops.size() << " " << comps[chain[0]][0] + 1 << endl; 602 for(int i : ops) cout << i << " "; 603 cout << endl; 604 605 for(int i = 0; i < n; i++) assert(a[i] == b[i]); 606 } 607 } 608 609 int main() { 610 ios::sync_with_stdio(false), cin.tie(nullptr); 611 int t; cin >> t; 612 while(t--) tc(); 613 } 614 ``` 615 616 **Magic** 617 618 With this, you can prove a significantly simpler solution. We will add this proof later. 619 620 **Magic Solution** 621 622 ``` 623 // Note: AI generated solution 624 #include <bits/stdc++.h> 625 using namespace std; 626 627 int main() { 628 ios::sync_with_stdio(false); 629 cin.tie(nullptr); 630 631 int t; 632 cin >> t; 633 634 while (t--) { 635 int n; 636 cin >> n; 637 638 vector<int> a(n + 1), b(n + 1); 639 for (int i = 1; i <= n; i++) { 640 cin >> a[i]; 641 } 642 for (int i = 1; i <= n; i++) { 643 cin >> b[i]; 644 } 645 646 int start = 1, remaining = 0; 647 bool possible = true; 648 649 for (int i = 1; i <= n; i++) { 650 if (a[i] > b[i]) { 651 possible = false; 652 } 653 if (a[i] < b[i]) { 654 if (remaining == 0) { 655 start = i; 656 } 657 remaining++; 658 } 659 } 660 661 if (!possible) { 662 cout << -1 << '\n'; 663 continue; 664 } 665 666 vector<int> operations; 667 int position = start; 668 669 while (remaining > 0) { 670 if (a[position] < b[position]) { 671 while (a[position] < b[position] && 672 (a[position] >= position || 673 a[a[position]] == b[a[position]])) { 674 a[position]++; 675 operations.push_back(1); 676 } 677 678 if (a[position] == b[position]) { 679 remaining--; 680 } 681 } 682 683 if (remaining == 0 || a[position] == position) { 684 break; 685 } 686 687 operations.push_back(2); 688 position = a[position]; 689 } 690 691 if (remaining > 0) { 692 cout << -1 << '\n'; 693 continue; 694 } 695 696 cout << operations.size() << ' ' << start << '\n'; 697 for (int operation : operations) { 698 cout << operation << ' '; 699 } 700 cout << '\n'; 701 } 702 } 703 ``` 704 705 **Rate the problem** 706 707 * Amazing: 708 * Good: 709 * Ok: 710 * Bad: 711 * Terrible: 712 713 [2262E - Paired Bracket Sequences](/contest/2262/problem/E "Codeforces Round 1120 (Div. 1)") 714 715 Author: [kondasujay2](/profile/kondasujay2 "International Master kondasujay2") 716 717 **Tutorial** 718 719 Tutorial is loading... 720 721 **Solution** 722 723 ``` 724 #include <bits/stdc++.h> 725 using namespace std; 726 727 int MOD; 728 729 void madd(int& a, int b) { 730 a += b; 731 if(a >= MOD) a -= MOD; 732 } 733 734 void msub(int& a, int b) { 735 a -= b; 736 if(a < 0) a += MOD; 737 } 738 739 int mmul(int a, int b) { 740 return 1LL * a * b % MOD; 741 } 742 743 int bpow(int x, int y) { 744 return y == 0 ? 1 : mmul((y % 2) ? x : 1, bpow(mmul(x, x), y / 2)); 745 } 746 747 void tc() { 748 int n; cin >> n >> MOD; 749 vector<int> f(2 * n + 1), invf(2 * n + 1); 750 f[0] = 1; 751 for(int i = 1; i <= 2 * n; i++) { 752 f[i] = mmul(f[i - 1], i); 753 } 754 invf[2 * n] = bpow(f[2 * n], MOD - 2); 755 for(int i = 2 * n; i >= 1; i--) { 756 invf[i - 1] = mmul(invf[i], i); 757 } 758 auto F = [&] (int n, int k) -> int { 759 return mmul(f[n], mmul(invf[k + 1], invf[n - k])); 760 }; 761 auto choose = [&] (int n, int k) -> int { 762 return mmul(f[n], mmul(invf[k], invf[n - k])); 763 }; 764 vector<vector<int>> p(n + 1, vector<int>(n + 1)); 765 for(int i = 0; i <= n; i++) { 766 p[0][i] = mmul(F(2 * i, i), F(2 * i, i)); 767 } 768 for(int i = 1; i <= n; i++) { 769 for(int j = 0; j <= n; j++) { 770 for(int k = 0; j + k <= n; k++) { 771 madd(p[i][j + k], mmul(p[i - 1][j], p[0][k])); 772 } 773 } 774 } 775 vector<int> ans(n + 1); 776 for(int i = 0; i <= n; i++) { 777 ans[i] = mmul(F(2 * n, i), p[i][n - i]); 778 } 779 for(int i = n - 1; i >= 0; i--) { 780 for(int j = i + 1; j <= n; j++) { 781 msub(ans[i], mmul(ans[j], choose(j, i))); 782 } 783 } 784 for(int i = 0; i <= n; i++) { 785 cout << ans[i] << " "; 786 } 787 cout << endl; 788 } 789 790 int main() { 791 ios::sync_with_stdio(false), cin.tie(nullptr); 792 int t; cin >> t; 793 while(t--) tc(); 794 } 795 ``` 796 797 **Rate the problem** 798 799 * Amazing: 800 * Good: 801 * Ok: 802 * Bad: 803 * Terrible: 804 805 [2262F - Rank Removal](/contest/2262/problem/F "Codeforces Round 1120 (Div. 1)") 806 807 Authors: [sukon](/profile/sukon "Candidate Master sukon") & [kondasujay2](/profile/kondasujay2 "International Master kondasujay2") 808 809 **Tutorial** 810 811 Tutorial is loading... 812 813 **Solution** 814 815 ``` 816 #include <bits/stdc++.h> 817 using namespace std; 818 819 const int MXN = 400; 820 821 template<size_t SZ> int compute_inv(const vector<bitset<SZ>>& mat, vector<bitset<SZ>>& inv) { 822 int n = mat.size(); 823 vector<bool> empty(n, true); 824 vector<bitset<SZ>> basis(n); 825 826 for(int i = 0; i < n; i++) { 827 bitset<SZ> cur = mat[i]; 828 bitset<SZ> curinv; 829 curinv[i] = 1; 830 for(int j = 0; j < n; j++) { 831 if(cur[j]) { 832 if(empty[j]) { 833 basis[j] = cur; 834 inv[j] = curinv; 835 empty[j] = false; 836 break; 837 } else { 838 cur ^= basis[j]; 839 curinv ^= inv[j]; 840 } 841 } 842 } 843 } 844 for(int i = 0; i < n; i++) { 845 if(empty[i]) return 0; 846 } 847 848 for(int i = n - 1; i >= 1; i--) { 849 for(int j = 0; j < i; j++) { 850 if(basis[j][i]) { 851 basis[j] ^= basis[i]; 852 inv[j] ^= inv[i]; 853 } 854 } 855 } 856 return 1; 857 } 858 859 bool try_removal(vector<pair<int, int>> cells, vector<bitset<MXN>>& mat, vector<bitset<MXN>>& inv, vector<int>& row_cnt) { 860 int n = mat.size(), k = cells.size(); 861 for(auto [x, y] : cells) { 862 if(mat[x][y] == 0) { 863 return false; 864 } 865 } 866 assert(k < 4); 867 vector<bitset<3>> K(k); 868 for(int i = 0; i < k; i++) { 869 for(int j = 0; j < k; j++) { 870 K[i][j] = (i == j) ^ inv[cells[i].second][cells[j].first]; 871 } 872 } 873 vector<bitset<3>> invK(cells.size()); 874 if(!compute_inv(K, invK)) { 875 return false; 876 } 877 for(auto [x, y] : cells) { 878 mat[x][y] = 0; 879 row_cnt[x]--; 880 } 881 882 auto old = inv; 883 for(int i = 0; i < n; i++) { 884 bitset<3> coef; 885 for(int alpha = 0; alpha < k; alpha++) { 886 int r = cells[alpha].first; 887 888 if(old[i][r]) { 889 coef ^= invK[alpha]; 890 } 891 } 892 893 // delta = coef * (V^T * old) 894 for(int beta = 0; beta < k; beta++) { 895 if(coef[beta]) { 896 int c = cells[beta].second; 897 inv[i] ^= old[c]; 898 } 899 } 900 } 901 return true; 902 } 903 904 vector<int> compute_matching(const vector<bitset<MXN>>& mat) { 905 int n = mat.size(); 906 vector<vector<int>> adj(n); 907 for(int i = 0; i < n; i++) { 908 for(int j = 0; j < n; j++) { 909 if(mat[i][j]) adj[i].push_back(j); 910 } 911 } 912 913 vector<int> match(n, -1); 914 vector<bool> done(n); 915 916 function<bool(int)> dfs = [&] (int s) { 917 for(int u : adj[s]) { 918 if(!done[u]) { 919 done[u] = true; 920 921 if(match[u] == -1 || dfs(match[u])) { 922 match[u] = s; 923 return true; 924 } 925 } 926 } 927 return false; 928 }; 929 930 for(int i = 0; i < n; i++) { 931 fill(done.begin(), done.end(), false); 932 dfs(i); 933 } 934 935 for(int i = 0; i < n; i++) { 936 assert(match[i] != -1); 937 } 938 return match; 939 } 940 941 void tc() { 942 int n, m; cin >> n >> m; 943 944 vector<bitset<MXN>> mat(n); 945 vector<int> row_cnt(n); 946 for(int i = 0; i < m; i++) { 947 int x, y; cin >> x >> y; 948 x--, y--; 949 mat[x][y] = 1; 950 row_cnt[x]++; 951 } 952 953 vector<bitset<MXN>> inv(n); 954 compute_inv(mat, inv); 955 956 int sm = m; 957 int left = (sm + n - 1) / n; 958 cout << left << '\n'; 959 960 while(sm > 0) { 961 vector<bitset<MXN>> omat = mat; 962 if(sm <= n) { 963 for(int i = 0; i < n; i++) { 964 for(int j = 0; j < n; j++) { 965 mat[i][j] = 0; 966 } 967 } 968 row_cnt.assign(n, 0); 969 } else if(sm <= 2 * n) { 970 vector<int> matching = compute_matching(mat); 971 for(int i = 0; i < n; i++) { 972 for(int j = 0; j < n; j++) { 973 mat[i][j] = 0; 974 } 975 } 976 row_cnt.assign(n, 0); 977 for(int i = 0; i < sm - n; i++) { 978 mat[matching[i]][i] = 1; 979 row_cnt[matching[i]]++; 980 } 981 } else if(sm <= 3 * n) { 982 vector<int> matching = compute_matching(mat); 983 int above = 0; 984 for(int i = 0; i < n; i++) { 985 for(int j = matching[i] + 1; j < n; j++) { 986 above += mat[j][i]; 987 } 988 } 989 990 vector<bitset<MXN>> nmat(n); 991 vector<int> nrow_cnt(n); 992 int ones_left = sm - n; 993 for(int i = 0; i < n; i++) { 994 nmat[matching[i]][i] = 1; 995 nrow_cnt[matching[i]]++; 996 ones_left--; 997 } 998 // make matrix either upper or lower triangular, whichever one 999 // removes a sufficient number of ones 1000 if(above >= ones_left) { 1001 for(int i = 0; i < n; i++) { 1002 for(int j = matching[i] + 1; j < n; j++) { 1003 if(mat[j][i]) { 1004 ones_left--; 1005 nmat[j][i] = 1; 1006 nrow_cnt[j]++; 1007 if(ones_left == 0) break; 1008 } 1009 } 1010 if(ones_left == 0) break; 1011 } 1012 } else { 1013 for(int i = 0; i < n; i++) { 1014 for(int j = 0; j < matching[i]; j++) { 1015 if(mat[j][i]) { 1016 ones_left--; 1017 nmat[j][i] = 1; 1018 nrow_cnt[j]++; 1019 if(ones_left == 0) break; 1020 } 1021 } 1022 if(ones_left == 0) break; 1023 } 1024 } 1025 mat = nmat; 1026 row_cnt = nrow_cnt; 1027 } else { 1028 int csm = sm; 1029 if(n % 2) { 1030 // odd case (remove either 1 or 3) 1031 int dup_row = -1; 1032 for(int i = 0; i < n; i++) { 1033 if(row_cnt[i] >= 2) { 1034 dup_row = i; 1035 break; 1036 } 1037 } 1038 assert(dup_row != -1); 1039 1040 vector<int> cols; 1041 for(int i = 0; i < n; i++) { 1042 if(mat[dup_row][i]) cols.push_back(i); 1043 } 1044 1045 assert(cols.size() >= 2); 1046 1047 for(int i = 0; i < n; i++) { 1048 if(try_removal({{i, cols[0]}}, mat, inv, row_cnt)) { 1049 csm--; 1050 break; 1051 } 1052 if(try_removal({{i, cols[1]}}, mat, inv, row_cnt)) { 1053 csm--; 1054 break; 1055 } 1056 } 1057 1058 if(csm == sm) { 1059 for(int i = 0; i < n; i++) { 1060 if(i != dup_row) { 1061 // remove L shape 1062 if(try_removal( 1063 {{i, cols[0]}, 1064 {dup_row, cols[0]}, 1065 {dup_row, cols[1]}}, 1066 mat, inv, row_cnt)) { 1067 csm -= 3; 1068 break; 1069 } 1070 } 1071 } 1072 assert(sm != csm); 1073 } 1074 } 1075 1076 while(csm > sm - n) { 1077 // remove 2 at a time 1078 int dup_row = -1; 1079 for(int i = 0; i < n; i++) { 1080 if(row_cnt[i] >= 3) { 1081 dup_row = i; 1082 break; 1083 } 1084 } 1085 1086 vector<int> cols; 1087 for(int i = 0; i < n; i++) { 1088 if(mat[dup_row][i]) cols.push_back(i); 1089 } 1090 1091 assert(cols.size() >= 3); 1092 1093 if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[1]}}, mat, inv, row_cnt)) { 1094 if(!try_removal({{dup_row, cols[1]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) { 1095 if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) { 1096 assert(false); 1097 } 1098 } 1099 } 1100 1101 csm -= 2; 1102 } 1103 assert(csm == sm - n); 1104 } 1105 1106 vector<pair<int, int>> move; 1107 for(int i = 0; i < n; i++) { 1108 for(int j = 0; j < n; j++) { 1109 if(omat[i][j] == 1 && mat[i][j] == 0) { 1110 move.push_back({i, j}); 1111 } 1112 } 1113 } 1114 cout << move.size() << "\n"; 1115 for(auto [x, y] : move) cout << x + 1 << " " << y + 1 << "\n"; 1116 sm -= n; 1117 1118 int csm = 0; 1119 for(int i = 0; i < n; i++) { 1120 csm += row_cnt[i]; 1121 } 1122 assert(csm == max(0, sm)); 1123 } 1124 } 1125 1126 int main() { 1127 int t; cin >> t; 1128 while(t--) tc(); 1129 } 1130 ``` 1131 1132 **Tutorial 2** 1133 1134 Credit to [BurnedChicken](/profile/BurnedChicken "International Grandmaster BurnedChicken") for finding this in testing! 1135 1136 We will first prove that for any row/column of a rank $n$ matrix, we can zero out everything in that row/column except one, and maintain rank $n$. This is because rank $n$ means the determinant is $1$, so there are exactly an odd number of perfect matchings in total (read Solution 1 for more understanding). Therefore at least $1$ of the ones in the row/column must be in an odd number of perfect matchings (since if they were all even then the total number would be even). This means if we delete all other ones but that one, then we would keep rank $n$. 1137 1138 This actually all you need to prove to solve the problem. Note that after we clear out one row except one number, we can clear out that column except that one number (even partially) and the determinant will not change (and the same works when clearing out a column with the leftover row). 1139 1140 For every turn, we want to try to find $n$ things to remove without changing the rank. Therefore, we begin by finding the one in the biggest row/column we can keep while removing everything else. Then we remove everything in the column/row of that one, and the everything in the row/column into the queue. If the queue + the current removals is big enough to reach $n$ removals, then we can just remove the ones in the queue. If the queue is too small, then we repeat one the next biggest row/column. Because the queue contains the row/column with the most ones, when the current removals will never exceed $n$ if the the queue + current removals is less than $n$. Once we run out of row/columns to clear, we can start removing the ones we excluded removing, since we have to reduce the rank at this point. 1141 1142 To find the one we must keep, you have to utilize the inverse, since we can clear out the row/column on $M_{i, j}$ if $M^{-1}_{j, i} = 1$ (proof is by Cramer's Rule). We can keep track of the inverse after this clear out operation in $O(n^2 / w)$ if done properly (using something similar to Woodbury Matrix Identity, look at Solution 1 for details). If implemented properly, this results in a $O(n^3 / w)$ solution. 1143 1144 **Solution 2** 1145 1146 ``` 1147 #include <bits/stdc++.h> 1148 using namespace std; 1149 1150 const int SZ = 400; 1151 1152 1153 template<size_t SZ> int compute_inv(const vector<bitset<SZ>>& mat, vector<bitset<SZ>>& inv) { 1154 int n = mat.size(); 1155 vector<bool> empty(n, true); 1156 vector<bitset<SZ>> basis(n); 1157 1158 for(int i = 0; i < n; i++) { 1159 bitset<SZ> cur = mat[i]; 1160 bitset<SZ> curinv; 1161 curinv[i] = 1; 1162 for(int j = 0; j < n; j++) { 1163 if(cur[j]) { 1164 if(empty[j]) { 1165 basis[j] = cur; 1166 inv[j] = curinv; 1167 empty[j] = false; 1168 break; 1169 } else { 1170 cur ^= basis[j]; 1171 curinv ^= inv[j]; 1172 } 1173 } 1174 } 1175 } 1176 for(int i = 0; i < n; i++) { 1177 if(empty[i]) return 0; 1178 } 1179 1180 for(int i = n - 1; i >= 1; i--) { 1181 for(int j = 0; j < i; j++) { 1182 if(basis[j][i]) { 1183 basis[j] ^= basis[i]; 1184 inv[j] ^= inv[i]; 1185 } 1186 } 1187 } 1188 return 1; 1189 } 1190 1191 void tc() { 1192 int n, m; cin >> n >> m; 1193 vector<bitset<SZ>> mat(n); 1194 for(int i = 0; i < m; i++) { 1195 int x, y; cin >> x >> y; 1196 x--, y--; 1197 mat[x][y] = 1; 1198 } 1199 1200 vector<bitset<SZ>> inv(n); 1201 compute_inv(mat, inv); 1202 vector<int> cnts(2 * n); 1203 for(int i = 0; i < n; i++) { 1204 for(int j = 0; j < n; j++) { 1205 cnts[i] += mat[i][j]; 1206 cnts[n + j] += mat[i][j]; 1207 } 1208 } 1209 queue<pair<int, int>> mustq, freeq; 1210 vector<pair<int, int>> centers; 1211 vector<vector<pair<int, int>>> moves; 1212 while(true) { 1213 while(mustq.size() + freeq.size() < n) { 1214 int best_rc = 0; 1215 for(int rc = 0; rc < 2 * n; rc++) { 1216 if(cnts[rc] >= cnts[best_rc]) best_rc = rc; 1217 } 1218 if(cnts[best_rc] == 0) { 1219 break; 1220 } 1221 1222 int x = -1, y = -1; 1223 if(best_rc < n) { 1224 x = best_rc; 1225 for(int j = 0; j < n; j++) { 1226 if(mat[x][j] && inv[j][x]) { 1227 y = j; 1228 break; 1229 } 1230 } 1231 } else { 1232 y = best_rc - n; 1233 for(int j = 0; j < n; j++) { 1234 if(mat[j][y] && inv[y][j]) { 1235 x = j; 1236 break; 1237 } 1238 } 1239 } 1240 assert(x != -1 && y != -1); 1241 1242 centers.push_back({x, y}); 1243 vector<pair<int, int>> must, free; 1244 auto erase = [&] (int a, int b) { 1245 mat[a][b] = 0; 1246 cnts[a]--; 1247 cnts[b + n]--; 1248 }; 1249 for(int j = 0; j < n; j++) { 1250 if(mat[x][j] && j != y) { 1251 must.push_back({x, j}); 1252 erase(x, j); 1253 } 1254 } 1255 for(int j = 0; j < n; j++) { 1256 if(mat[j][y] && j != x) { 1257 free.push_back({j, y}); 1258 erase(j, y); 1259 } 1260 } 1261 erase(x, y); 1262 assert(cnts[x] == 0 && cnts[n + y] == 0); 1263 1264 if(best_rc < n) swap(must, free); 1265 for(auto u : must) mustq.push(u); 1266 for(auto u : free) freeq.push(u); 1267 1268 bitset<SZ> row = inv[y]; 1269 for(int j = 0; j < n; j++) { 1270 if(cnts[j + n] > 0 && inv[j][x]) { 1271 inv[j] ^= row; 1272 } 1273 } 1274 } 1275 int left = n; 1276 vector<pair<int, int>> move; 1277 while(left > 0 && mustq.size() > 0) { 1278 left--; 1279 move.push_back(mustq.front()); 1280 mustq.pop(); 1281 } 1282 while(left > 0 && freeq.size() > 0) { 1283 left--; 1284 move.push_back(freeq.front()); 1285 freeq.pop(); 1286 } 1287 while(left > 0 && centers.size() > 0) { 1288 left--; 1289 move.push_back(centers.back()); 1290 centers.pop_back(); 1291 } 1292 moves.push_back(move); 1293 if(centers.size() == 0) break; 1294 } 1295 cout << moves.size() << "\n"; 1296 for(auto move : moves) { 1297 cout << move.size() << "\n"; 1298 for(auto [u, v] : move) cout << u + 1 << " " << v + 1 << "\n"; 1299 } 1300 } 1301 1302 int main() { 1303 ios::sync_with_stdio(false), cin.tie(nullptr); 1304 int t; cin >> t; 1305 while(t--) tc(); 1306 } 1307 ``` 1308 1309 **Rate the problem** 1310 1311 * Amazing: 1312 * Good: 1313 * Ok: 1314 * Bad: 1315 * Terrible: