codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2263.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: