Thank you to everyone who participated!

We are sorry for the poor testcases on C1, along with C1 and C2's solutions being so similar to the recent Div3 E.

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

void tc() {
    int n; cin >> n;
    int cnt = 0;
    vector<int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        cnt += a[i];
    }
    if(cnt >= n - cnt) {
        cout << "Bessie\n";
    } else {
        cout << "Elsie\n";
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

Rate the problem

2263B - Min Matrices

Author: sukon

Tutorial

Solution

#include<bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, k; cin >> n >> k;
    int x = k-n+1;
    if(!(1 <= x && x <= n)) { cout << -1; return; }
    vector<vector<int>> ans(n, vector<int>(n));
    ans[0][0] = 1;
    int on = 2;
    for(int i = 1; i < x; i++) {
        ans[0][i] = on; on++;
        ans[i][0] = on; on++;
    }
    for(int i = x; i < n; i++) {
        ans[i][i] = on; on++;
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(!ans[i][j]) {
                ans[i][j] = on; on++;
            }
        }
    }

    for(int j = 0; j < n; j++) {
        if(j) cout << "\n";
        for(auto &i : ans[j]) cout << i << " ";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) {
        solve();
        if(t)   cout << "\n";
    }
}

Rate the problem

2263C1 - Floor of MEX (Easy Version) / 2262A1 - Floor of MEX (Easy Version)

Author: CutSandstone

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

void tc() {
    int n; cin >> n;
    vector<int> b(n + 1);
    for(int i = 1; i <= n; i++) cin >> b[i];
    vector<pair<int, int>> goodivs;
    vector<pair<int, int>> badivs;
    for(int i = 1; i <= n; i++) {
        badivs.push_back({b[i] * i, (b[i] + 1) * i - 1});
        for(int j = 0; j < b[i]; j++) {
            goodivs.push_back({j * i, (j + 1) * i - 1});
        }
    }
    vector<int> d(n + 1);
    for(auto [l, r] : badivs) {
        d[min(n, l)]++;
        d[min(n, r + 1)]--;
    }
    int csm = 0;
    vector<int> gnums;
    for(int i = 0; i < n; i++) {
        csm += d[i];
        if(csm == 0) {
            gnums.push_back(i);
        }
    }
    cout << gnums.size() << endl;
    for(int i : gnums) cout << i << " ";
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

Rate the problem

2263C2 - Floor of MEX (Hard Version) / 2262A2 - Floor of MEX (Hard Version)

Author: kondasujay2

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

void tc() {
    int n; cin >> n;
    vector<int> b(n + 1);
    for(int i = 1; i <= n; i++) cin >> b[i];
    vector<pair<int, int>> goodivs;
    vector<pair<int, int>> badivs;
    for(int i = 1; i <= n; i++) {
        if(b[i] > (n - 1) / i + 1) {
            cout << 0 << endl;
            return;
        }
        badivs.push_back({b[i] * i, (b[i] + 1) * i - 1});
        for(int j = 0; j < b[i]; j++) {
            goodivs.push_back({j * i, (j + 1) * i - 1});
        }
    }
    vector<int> d(n + 1);
    for(auto [l, r] : badivs) {
        d[min(n, l)]++;
        d[min(n, r + 1)]--;
    }
    int csm = 0;
    vector<int> gnums;
    for(int i = 0; i < n; i++) {
        csm += d[i];
        if(csm == 0) {
            gnums.push_back(i);
        }
    }
    set<pair<int, int>> st;
    sort(goodivs.begin(), goodivs.end(), [&] (pair<int, int> iv, pair<int, int> iv2) {
        return iv.second - iv.first < iv2.second - iv2.first;
    });
    for(auto [l, r] : goodivs) {
        auto it = st.lower_bound({l, 0});
        if(it != st.end() && it->second <= r) {
            continue;
        }
        st.insert({l, r});
    }

    vector<pair<int, int>> impivs(st.begin(), st.end());
    int l = 0, r = 0;
    vector<int> dp(impivs.size() + 1);
    dp[0] = 1;
    int poss = 1;
    for(int i : gnums) {
        while(l < impivs.size() && impivs[l].second < i) {
            poss += MOD - dp[l];
            poss %= MOD;
            l++;
        }
        while(r < impivs.size() && impivs[r].first <= i) r++;
        dp[r] += poss;
        dp[r] %= MOD;
        poss += poss;
        poss %= MOD;
    }
    cout << dp[impivs.size()] << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

Rate the problem

2263D - Culling Game / 2262B - Culling Game

Author: kondasujay2

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct BIT {
    vector<ll> tr;
    BIT(int n) : tr(n + 1) {}
    void add(int k, ll x) {
        while(k < tr.size()) {
            tr[k] += x;
            k += k&-k;
        }
    }
    ll sum(int k) {
        ll res = 0;
        while(k > 0) {
            res += tr[k];
            k -= k&-k;
        }
        return res;
    }
};

void tc() {
    int n; cin >> n;
    vector<int> a(n), p(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> p[i]; p[i]--;
    }
    reverse(p.begin(), p.end());
    BIT bit(n);
    set<int> imp; 
    vector<int> ans(n);
    for(int i = 0; i < n; i++) {
        int k = p[i];
        auto it = imp.upper_bound(k);
        int pimp;
        if(it == imp.begin() || bit.sum(k) - bit.sum(*prev(it)) < a[k]) {
            imp.insert(k);
            pimp = k;
        } else {
            pimp = *prev(it);
        }
        bit.add(k + 1, a[k]);
        while(imp.upper_bound(k) != imp.end()) {
            int j = *imp.upper_bound(k);
            if(bit.sum(j) - bit.sum(pimp) >= a[j]) {
                imp.erase(j);
            } else {
                break;
            }
        }
        ans[i] = imp.size() - 1;
    }
    reverse(ans.begin(), ans.end());
    for(int i : ans) cout << i << " ";
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

Rate the problem

2263E - Traveling the World / 2262C - Traveling the World

Author: kondasujay2

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MOD = 1e9 + 7;

void tc() {
    int n; cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    int k = n / 2;

    int val = 1;
    for(int i = 1; i <= k; i++) {
        val = (ll)i * val % MOD;
    }
    for(int i = 1; i <= k - (n % 2 == 0 ? 2 : 1); i++) {
        val = (ll)i * val % MOD;
    }

    set<ll> xposs;
    xposs.insert(a[n - 1] - a[n - 2]);
    xposs.insert(a[n - 1] - a[n - 3]);

    int ans = 0;
    for(ll x : xposs) {
        vector<ll> b;
        for(int i = 0; i < k; i++) {
            b.push_back(i * x);
        }
        for(int i = 0; i < n - k; i++) {
            b.push_back(a[n - 1] - i * x);
        }
        sort(b.begin(), b.end());
        if(a == b) {
            ans += val;
            if(ans >= MOD) ans -= MOD;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

Rate the problem

2263F - PLUSworld / 2262D - PLUSworld

Authors: sukon & kondasujay2

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

void tc() {
    int n; cin >> n;

    vector<int> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i], a[i]--;
    for(int i = 0; i < n; i++) cin >> b[i], b[i]--;

    int badcnt = 0;
    for(int i = 0; i < n; i++) {
        badcnt += a[i] != b[i];
    }
    if(badcnt == 0) {
        cout << "0 1\n";
        return;
    }

    // mark everything which will ever be reached
    vector<bool> useful(n);
    for(int i = 0; i < n; i++) {
        if(a[i] == b[i]) continue;
        int x = i;
        while(!useful[x]) {
            useful[x] = true;
            x = b[x];
        }
    }

    // anything with b[i] == i once we reach we can't reach anything else, 
    // at most one of them can exit
    vector<int> ends;
    for(int i = 0; i < n; i++) {
        if(useful[i] && b[i] == i) ends.push_back(i);
    }

    if(ends.size() > 1) {
        cout << "-1\n";
        return;
    }

    vector<vector<int>> adj(n), radj(n);
    for(int i = 0; i < n; i++) {
        if(a[i] > b[i]) {
            cout << "-1\n";
            return;
        }
        for(int j = a[i]; j <= b[i]; j++) {
            adj[i].push_back(j);
            radj[j].push_back(i);
        }
    }

    // tarjan algorithm, from cp-algorithms
    vector<int> st;    // - stack holding the unclaimed vertices
    vector<int> roots(n, -1); // - keeps track of the SCC roots of the vertices
    int timer = 0;         // - dfs timestamp counter
    vector<int> t_in(n, -1);  // - keeps track of the dfs timestamp of the vertices
    vector<int> t_low(n, -1); // - keeps track of the lowest t_in of unclaimed vertices
    // reachable in the subtree

    // implements the tarjan algorithm for strongly connected components
    auto dfs = [&](auto&& self, int s) -> void {
        t_low[s] = t_in[s] = timer++;
        st.push_back(s);

        for (auto u : adj[s]) {
            if (t_in[u] == -1) { // tree-edge
                self(self, u);
                t_low[s] = min(t_low[s], t_low[u]);
            } else if (roots[u] == -1) { // back-edge, cross-edge or forward-edge to an unclaimed vertex
                t_low[s] = min(t_low[s], t_in[u]);
            }
        }

        if (t_low[s] == t_in[s]) { // vertex is a root
            while (true) {
                int u = st.back();
                st.pop_back();
                roots[u] = s; // claims the vertex
                if (u == s)
                    break;
            }
        }
    };

    // applies the tarjan algorithm to all the vertices
    for (int v = 0; v < n; v++) {
        if (t_in[v] == -1) {
            dfs(dfs, v);
        }
    }
    vector<vector<int>> comps(n);
    for(int v = 0; v < n; v++) {
        comps[roots[v]].push_back(v);
    }

    vector<int> p(n, -1);
    vector<int> sz(n);
    for(int i = 0; i < n; i++) {
        if(a[i] != b[i]) {
            sz[roots[i]]++;
        }
        if(useful[i] && roots[i] != roots[b[i]]) {
            if(p[roots[b[i]]] != -1) {
                cout << "-1\n";
                return;
            }
            p[roots[b[i]]] = roots[i];
        }
    }
    vector<int> chain;
    int x = roots[ends[0]];
    int csz = 0;
    while(x != -1) {
        chain.push_back(x);
        csz += sz[x];
        x = p[x];
    }
    if(csz != badcnt) {
        cout << "-1\n";
        return;
    }
    reverse(chain.begin(), chain.end());

    {
        x = comps[chain[0]][0];
        vector<int> ops;
        auto op1 = [&] () {
            ops.push_back(1);
            a[x]++;
        };
        auto op2 = [&] () {
            ops.push_back(2);
            x = a[x];
        };
        auto solve_scc = [&] () {
            int rt = roots[x];
            vector<int> comp = comps[rt];

            vector<int> p2(n, -1);
            // only one thing in comp case
            auto rdfs = [&] (auto&& self, int s) -> void {
                for(int u : radj[s]) {
                    if(roots[u] != rt) continue;
                    if(p2[u] == -1) {
                        p2[u] = s;
                        self(self, u);
                    }
                }
            };

            // root a tree
            rdfs(rdfs, comp[0]);

            for(int i = 0; i < comp.size(); i++) {
                while(x != comp[i]) {
                    while(a[x] < max(p2[x], comp[i])) op1();
                    op2();
                }
                while(a[x] < b[x]) op1();
                op2();
            }
        };
        for(int i = 0; i < chain.size(); i++) solve_scc();

        cout << ops.size() << " " << comps[chain[0]][0] + 1 << endl;
        for(int i : ops) cout << i << " ";
        cout << endl;

        for(int i = 0; i < n; i++) assert(a[i] == b[i]);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

Magic

Magic Solution

// Note: AI generated solution
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n + 1), b(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; i++) {
            cin >> b[i];
        }

        int start = 1, remaining = 0;
        bool possible = true;

        for (int i = 1; i <= n; i++) {
            if (a[i] > b[i]) {
                possible = false;
            }
            if (a[i] < b[i]) {
                if (remaining == 0) {
                    start = i;
                }
                remaining++;
            }
        }

        if (!possible) {
            cout << -1 << '\n';
            continue;
        }

        vector<int> operations;
        int position = start;

        while (remaining > 0) {
            if (a[position] < b[position]) {
                while (a[position] < b[position] &&
                       (a[position] >= position ||
                        a[a[position]] == b[a[position]])) {
                    a[position]++;
                    operations.push_back(1);
                }

                if (a[position] == b[position]) {
                    remaining--;
                }
            }

            if (remaining == 0 || a[position] == position) {
                break;
            }

            operations.push_back(2);
            position = a[position];
        }

        if (remaining > 0) {
            cout << -1 << '\n';
            continue;
        }

        cout << operations.size() << ' ' << start << '\n';
        for (int operation : operations) {
            cout << operation << ' ';
        }
        cout << '\n';
    }
}

Rate the problem

2262E - Paired Bracket Sequences

Author: kondasujay2

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

int MOD;

void madd(int& a, int b) {
    a += b;
    if(a >= MOD) a -= MOD;
}

void msub(int& a, int b) {
    a -= b;
    if(a < 0) a += MOD;
}

int mmul(int a, int b) {
    return 1LL * a * b % MOD;
}

int bpow(int x, int y) {
    return y == 0 ? 1 : mmul((y % 2) ? x : 1, bpow(mmul(x, x), y / 2));
}

void tc() {
    int n; cin >> n >> MOD;
    vector<int> f(2 * n + 1), invf(2 * n + 1);
    f[0] = 1;
    for(int i = 1; i <= 2 * n; i++) {
        f[i] = mmul(f[i - 1], i);
    }
    invf[2 * n] = bpow(f[2 * n], MOD - 2);
    for(int i = 2 * n; i >= 1; i--) {
        invf[i - 1] = mmul(invf[i], i);
    }
    auto F = [&] (int n, int k) -> int {
        return mmul(f[n], mmul(invf[k + 1], invf[n - k]));
    };
    auto choose = [&] (int n, int k) -> int {
        return mmul(f[n], mmul(invf[k], invf[n - k]));
    };
    vector<vector<int>> p(n + 1, vector<int>(n + 1));
    for(int i = 0; i <= n; i++) {
        p[0][i] = mmul(F(2 * i, i), F(2 * i, i));
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            for(int k = 0; j + k <= n; k++) {
                madd(p[i][j + k], mmul(p[i - 1][j], p[0][k]));
            }
        }
    }
    vector<int> ans(n + 1);
    for(int i = 0; i <= n; i++) {
        ans[i] = mmul(F(2 * n, i), p[i][n - i]);
    }
    for(int i = n - 1; i >= 0; i--) {
        for(int j = i + 1; j <= n; j++) {
            msub(ans[i], mmul(ans[j], choose(j, i)));
        }
    }
    for(int i = 0; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t; 
    while(t--) tc();
}

Rate the problem

2262F - Rank Removal

Authors: sukon & kondasujay2

Tutorial

Solution

#include <bits/stdc++.h>
using namespace std;

const int MXN = 400;

template<size_t SZ> int compute_inv(const vector<bitset<SZ>>& mat, vector<bitset<SZ>>& inv) {
    int n = mat.size();
    vector<bool> empty(n, true);
    vector<bitset<SZ>> basis(n);

    for(int i = 0; i < n; i++) {
        bitset<SZ> cur = mat[i];
        bitset<SZ> curinv;
        curinv[i] = 1;
        for(int j = 0; j < n; j++) {
            if(cur[j]) {
                if(empty[j]) {
                    basis[j] = cur;
                    inv[j] = curinv;
                    empty[j] = false;
                    break;
                } else {
                    cur ^= basis[j];
                    curinv ^= inv[j];
                }
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(empty[i]) return 0;
    }

    for(int i = n - 1; i >= 1; i--) {
        for(int j = 0; j < i; j++) {
            if(basis[j][i]) {
                basis[j] ^= basis[i];
                inv[j] ^= inv[i];
            }
        }
    }
    return 1;
}

bool try_removal(vector<pair<int, int>> cells, vector<bitset<MXN>>& mat, vector<bitset<MXN>>& inv, vector<int>& row_cnt) {
    int n = mat.size(), k = cells.size();
    for(auto [x, y] : cells) {
        if(mat[x][y] == 0) {
            return false;
        }
    }
    assert(k < 4);
    vector<bitset<3>> K(k); 
    for(int i = 0; i < k; i++) {
        for(int j = 0; j < k; j++) {
            K[i][j] = (i == j) ^ inv[cells[i].second][cells[j].first];
        }
    }
    vector<bitset<3>> invK(cells.size());
    if(!compute_inv(K, invK)) {
        return false;
    }
    for(auto [x, y] : cells) {
        mat[x][y] = 0;
        row_cnt[x]--;
    }

    auto old = inv;
    for(int i = 0; i < n; i++) {
        bitset<3> coef;
        for(int alpha = 0; alpha < k; alpha++) {
            int r = cells[alpha].first;

            if(old[i][r]) {
                coef ^= invK[alpha];
            }
        }

        // delta = coef * (V^T * old)
        for(int beta = 0; beta < k; beta++) {
            if(coef[beta]) {
                int c = cells[beta].second;
                inv[i] ^= old[c];
            }
        }
    }
    return true;
}

vector<int> compute_matching(const vector<bitset<MXN>>& mat) {
    int n = mat.size();
    vector<vector<int>> adj(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(mat[i][j]) adj[i].push_back(j);
        }
    }

    vector<int> match(n, -1);
    vector<bool> done(n);

    function<bool(int)> dfs = [&] (int s) {
        for(int u : adj[s]) {
            if(!done[u]) {
                done[u] = true;

                if(match[u] == -1 || dfs(match[u])) {
                    match[u] = s;
                    return true;
                }
            }
        }
        return false;
    };

    for(int i = 0; i < n; i++) {
        fill(done.begin(), done.end(), false);
        dfs(i);
    }

    for(int i = 0; i < n; i++) {
        assert(match[i] != -1);
    }
    return match;
}

void tc() {
    int n, m; cin >> n >> m;

    vector<bitset<MXN>> mat(n);
    vector<int> row_cnt(n);
    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        x--, y--;
        mat[x][y] = 1;
        row_cnt[x]++;
    }

    vector<bitset<MXN>> inv(n);
    compute_inv(mat, inv);

    int sm = m;
    int left = (sm + n - 1) / n;
    cout << left << '\n';

    while(sm > 0) {
        vector<bitset<MXN>> omat = mat;
        if(sm <= n) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    mat[i][j] = 0;
                }
            }
            row_cnt.assign(n, 0);
        } else if(sm <= 2 * n) {
            vector<int> matching = compute_matching(mat);
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    mat[i][j] = 0;
                }
            }
            row_cnt.assign(n, 0);
            for(int i = 0; i < sm - n; i++) {
                mat[matching[i]][i] = 1;
                row_cnt[matching[i]]++;
            }
        } else if(sm <= 3 * n) {
            vector<int> matching = compute_matching(mat);
            int above = 0;
            for(int i = 0; i < n; i++) {
                for(int j = matching[i] + 1; j < n; j++) {
                    above += mat[j][i];
                }
            }

            vector<bitset<MXN>> nmat(n);
            vector<int> nrow_cnt(n);
            int ones_left = sm - n;
            for(int i = 0; i < n; i++) {
                nmat[matching[i]][i] = 1;
                nrow_cnt[matching[i]]++;
                ones_left--;
            }
            // make matrix either upper or lower triangular, whichever one
            // removes a sufficient number of ones
            if(above >= ones_left) {
                for(int i = 0; i < n; i++) {
                    for(int j = matching[i] + 1; j < n; j++) {
                        if(mat[j][i]) {
                            ones_left--;
                            nmat[j][i] = 1;
                            nrow_cnt[j]++;
                            if(ones_left == 0) break;
                        }
                    }
                    if(ones_left == 0) break;
                }
            } else {
                for(int i = 0; i < n; i++) {
                    for(int j = 0; j < matching[i]; j++) {
                        if(mat[j][i]) {
                            ones_left--;
                            nmat[j][i] = 1;
                            nrow_cnt[j]++;
                            if(ones_left == 0) break;
                        }
                    }
                    if(ones_left == 0) break;
                }
            }
            mat = nmat;
            row_cnt = nrow_cnt;
        } else {
            int csm = sm;
            if(n % 2) {
                // odd case (remove either 1 or 3)
                int dup_row = -1;
                for(int i = 0; i < n; i++) {
                    if(row_cnt[i] >= 2) {
                        dup_row = i;
                        break;
                    }
                }
                assert(dup_row != -1);

                vector<int> cols;
                for(int i = 0; i < n; i++) {
                    if(mat[dup_row][i]) cols.push_back(i);
                }

                assert(cols.size() >= 2);

                for(int i = 0; i < n; i++) {
                    if(try_removal({{i, cols[0]}}, mat, inv, row_cnt)) {
                        csm--;
                        break;
                    }
                    if(try_removal({{i, cols[1]}}, mat, inv, row_cnt)) {
                        csm--;
                        break;
                    }
                }

                if(csm == sm) {
                    for(int i = 0; i < n; i++) {
                        if(i != dup_row) {
                            // remove L shape
                            if(try_removal(
                                    {{i, cols[0]}, 
                                     {dup_row, cols[0]}, 
                                     {dup_row, cols[1]}},
                                mat, inv, row_cnt)) {
                                csm -= 3;
                                break;
                            }
                        }
                    }
                    assert(sm != csm);
                }
            }

            while(csm > sm - n) {
                // remove 2 at a time
                int dup_row = -1;
                for(int i = 0; i < n; i++) {
                    if(row_cnt[i] >= 3) {
                        dup_row = i;
                        break;
                    }
                }

                vector<int> cols;
                for(int i = 0; i < n; i++) {
                    if(mat[dup_row][i]) cols.push_back(i);
                }

                assert(cols.size() >= 3);

                if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[1]}}, mat, inv, row_cnt)) {
                    if(!try_removal({{dup_row, cols[1]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) {
                        if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) {
                            assert(false);
                        }
                    }
                }

                csm -= 2;
            }
            assert(csm == sm - n);
        }

        vector<pair<int, int>> move;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(omat[i][j] == 1 && mat[i][j] == 0) {
                    move.push_back({i, j});
                }
            }
        }
        cout << move.size() << "\n";
        for(auto [x, y] : move) cout << x + 1 << " " << y + 1 << "\n";
        sm -= n;

        int csm = 0;
        for(int i = 0; i < n; i++) {
            csm += row_cnt[i];
        }
        assert(csm == max(0, sm));
    }
}

int main() {
    int t; cin >> t;
    while(t--) tc();
}

Tutorial 2

Credit to BurnedChicken for finding this in testing!

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$$$.

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).

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.

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.

Solution 2

#include <bits/stdc++.h>
using namespace std;
 
const int SZ = 400;
 
 
template<size_t SZ> int compute_inv(const vector<bitset<SZ>>& mat, vector<bitset<SZ>>& inv) {
    int n = mat.size();
    vector<bool> empty(n, true);
    vector<bitset<SZ>> basis(n);
 
    for(int i = 0; i < n; i++) {
        bitset<SZ> cur = mat[i];
        bitset<SZ> curinv;
        curinv[i] = 1;
        for(int j = 0; j < n; j++) {
            if(cur[j]) {
                if(empty[j]) {
                    basis[j] = cur;
                    inv[j] = curinv;
                    empty[j] = false;
                    break;
                } else {
                    cur ^= basis[j];
                    curinv ^= inv[j];
                }
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(empty[i]) return 0;
    }
 
    for(int i = n - 1; i >= 1; i--) {
        for(int j = 0; j < i; j++) {
            if(basis[j][i]) {
                basis[j] ^= basis[i];
                inv[j] ^= inv[i];
            }
        }
    }
    return 1;
}
 
void tc() {
    int n, m; cin >> n >> m;
    vector<bitset<SZ>> mat(n);
    for(int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        x--, y--;
        mat[x][y] = 1;
    }
 
    vector<bitset<SZ>> inv(n);
    compute_inv(mat, inv);
    vector<int> cnts(2 * n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cnts[i] += mat[i][j];
            cnts[n + j] += mat[i][j];
        }
    }
    queue<pair<int, int>> mustq, freeq;
    vector<pair<int, int>> centers;
    vector<vector<pair<int, int>>> moves;
    while(true) {
        while(mustq.size() + freeq.size() < n) {
            int best_rc = 0;
            for(int rc = 0; rc < 2 * n; rc++) {
                if(cnts[rc] >= cnts[best_rc]) best_rc = rc;
            }
            if(cnts[best_rc] == 0) {
                break;
            }
 
            int x = -1, y = -1;
            if(best_rc < n) {
                x = best_rc;
                for(int j = 0; j < n; j++) {
                    if(mat[x][j] && inv[j][x]) {
                        y = j;
                        break;
                    }
                }
            } else {
                y = best_rc - n;
                for(int j = 0; j < n; j++) {
                    if(mat[j][y] && inv[y][j]) {
                        x = j;
                        break;
                    }
                }
            }
            assert(x != -1 && y != -1);
 
            centers.push_back({x, y});
            vector<pair<int, int>> must, free;
            auto erase = [&] (int a, int b) {
                mat[a][b] = 0;
                cnts[a]--;
                cnts[b + n]--;
            };
            for(int j = 0; j < n; j++) {
                if(mat[x][j] && j != y) {
                    must.push_back({x, j});
                    erase(x, j);
                }
            }
            for(int j = 0; j < n; j++) {
                if(mat[j][y] && j != x) {
                    free.push_back({j, y});
                    erase(j, y);
                }
            }
            erase(x, y);
            assert(cnts[x] == 0 && cnts[n + y] == 0);
 
            if(best_rc < n) swap(must, free);
            for(auto u : must) mustq.push(u);
            for(auto u : free) freeq.push(u);
 
            bitset<SZ> row = inv[y];
            for(int j = 0; j < n; j++) {
                if(cnts[j + n] > 0 && inv[j][x]) {
                    inv[j] ^= row;
                }
            }
        }
        int left = n;
        vector<pair<int, int>> move;
        while(left > 0 && mustq.size() > 0) {
            left--;
            move.push_back(mustq.front());
            mustq.pop();
        }
        while(left > 0 && freeq.size() > 0) {
            left--;
            move.push_back(freeq.front());
            freeq.pop();
        }
        while(left > 0 && centers.size() > 0) {
            left--;
            move.push_back(centers.back());
            centers.pop_back();
        }
        moves.push_back(move);
        if(centers.size() == 0) break;
    }
    cout << moves.size() << "\n";
    for(auto move : moves) {
        cout << move.size() << "\n";
        for(auto [u, v] : move) cout << u + 1 << " " << v + 1 << "\n";
    }
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t; cin >> t;
    while(t--) tc();
}

Rate the problem

define ll long long

int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin>>t; while(t--) { int n,k; cin>>n>>k; int d=1; int re=2*n-k; int c=re+1; int count=1; int a[n][n]; if(k<n|| k>=2*n)cout<<-1<<endl; else { for( int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i==j && count<=re) { a[i][j]=d; d++; count++;

} else { a[i][j]=c; c++; } cout<<a[i][j]<<" "; } cout<<endl; } } } return 0;

} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I felt B can done this way also.

Комментарии (61)

Написать комментарий?

kondasujay2

2 месяца назад, скрыть # |

Auto comment: topic has been updated by kondasujay2 (previous revision, new revision, compare).

→ Ответить

Askew_breadcrumb6

7 недель назад, скрыть # ^ |

In Problem C2's official solution,

for(int i = 1; i <= n; i++) {
       badivs.push_back({b[i] * i, (b[i] + 1) * i - 1});
    for(int j = 0; j < b[i]; j++) {
       goodivs.push_back({j * i, (j + 1) * i - 1});
    }
}

How do you know this will not give a TLE? In the sense that the worst case time complexity of this loop is n^2 right?

chen_weilian

← Rev. 3 →

The problem states that a solution must exist, which implies that a[i] <= (n-1) / i + 1 because numbers are at most n-1. Summing it up give a O(n*log n) complexity

Oh that's right! Thank you!!

sukon

Auto comment: topic has been updated by sukon (previous revision, new revision, compare).

bakaasta

Nice Contest

AksLolCoding

← Rev. 2 →

+16

Div1A2/Div2C2 can be solved in $$$O(n\log n)$$$ via counting sort if you store the smallest interval for each right endpoint.

tfg

2 месяца назад, скрыть # ^ |

Remove intervals that have smaller intervals that are completely inside it and there remains O(N) intervals. I solved the DP part in O(N) using prefix sums and the only part is O(NlogN) to iterate through the initial intervals to find out for each L the smallest R of an interval starting at that L.

mnnit.prakharg

+20

For C2, my submission: 390474676. It works in O(nlogn) time comp. and O(n) space comp.

My DP: I have processed till i (0 <= i < n), and I want to find how many good sets exist with the largest element being i. Note till now, we are not considering intervals whose right endpoint is bigger that i.

For transition, I will be summing up the dp[j] such that j < i, j represents what is the second largest element of the set, and there is no interval completely inside [j + 1, i — 1]. j will form a contiguous range, so we can use prefix sum on dp values.

Thus, dp calc. part is O(n), but preprocessing intervals take O(nlogn) time.

Final answer: let pos represents the maximum left endpoint of any interval in which at least one number should lie. ans = dp[pos] + dp[pos + 1] + ... + dp[n — 1].

fakeapple

I also solved it similarily :D

https://codeforces.me/contest/2262/submission/390455393

dooglius

"Rate the problem" appears to have all the problems sharing the same rating votes

wow im stupid i will fix

PiggyPump

Not a bad contest, but it was indeed tough, thx for the rating boost, but I mean it was like:

A: 800 — 900 B: 1000 — 1100 C1: 1300, maybe 1400, because I had to use Seg Tree to quickly tell me which ranges of values needed to be excluded (but it wasn't necessary because you didn't have to do updates between queries)

C2: 1700+, I read it and it seemed kinda cooked, like I don't know how to wrap my head around all the conditions that had to be satisifed -- and how to count the number of ways to satisfy all constraints.

D: 2000+, read it and realized that your favorite pupil had never seen this kind of bullshit before.

E, F: ???

mrinmoy66sadhukhan

"never seen this kind of bullshit.." Lmao.

Geek_GamBit

Goated feedback LOL

Sean222299

C1 is hard for me :<

misytnikita

B tricky math and realization, C1 really mathy

Krish-006-19

i found out, in min k all diagonal things, and as k decreases we move minimum non diagonal elements to the diagonal and we keep on doing till k==n, and the max k happens when it goes, n=3, 1 2 3 4 5 6 7 8 9 here k is the max, whereas 1 5 9 4 2 6 7 8 3 here k=3

hence it is bit observation, not that much math, the only thing u gotta do is to swap mat[i][i] & mat[0][i] and you gonna get ans

i have the same idea, but i get one RE with realization

potatoArmy

in C1 and C2, i think its difference array, not prefix sum right?

xiaolanjing

Use a difference array to mark the intervals that are not allowed

ik, but editorial says prefix sum, i think it should be difference array

After marking the forbidden intervals with a difference array, take prefix sums to determine which positions are covered.That's probably what the editorial meant^_^

well then maybe they should mention difference array too

yes,i think so

c2 is so hard >_<

invoker._

c2 idea seemed so oblivious , but was too much implementation that i though i was over complicating and did not try :( .

dhane_4651

Can you explain the thought process for C2 and any similar question if available

Exactly same as the editorial

Pre- requisite idea in combinatorics:

I have to choose a number of in the range [x,y] .

This condition will always be satisfied if choose a value in range [x1,y1] . given x1 >= x && Y1 <= Y

Now for each I , you mark some range as invalid . On other valid ranges you need at-least one element to satisfy MEX condition.

The above statement is pretty oblivious if you solve C1.

Now using the idea from combinatorics you can remove the larger interval , if a smaller one exists

Now for each value , it will either be in a interval , or invalid , or present in no interval. (if present in no interval , you multiply the result by 2) this can be solved using DP .

This was basically what i came up with , but looked like too much implementation which i suck at.

trashaccountasf

-8

Exactly there is no way these many people solved C2 in Div2 without cheating. Even if you know the solution the implementation is insanely hard. Not to mention I still don't know how to make the Dp state correctly. Question D is 2x easier than this question.

HuynhGiangNhatKhang

Am I the only one to solve div 1B with sqrt decomposition?

vaibhav_prakash2005

Div2 C1 has weak test cases leading to many quadratic solutions including mine getting accepted. There should be a test case where n = 10^5 and a_i = 1, 1 <= i <= n

sumeet2007

-9

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

include <bits/stdc++.h>

using namespace std;

ipig

Great contest! Unfortunately, I ran out of time on E.

In the solution for c2 ,isn't the time complexity for getting the goodivs O(n*n) as we are already running the loop for O(n) times and while getting all the ranges of size k we are again iterating from 0 -> b[i] where 0 <= b[i] <= n.

Harmonic progression :

n + (n/2) + (n/3) + ... --> upper bound n log(n)

I get it I did the same thing, but thought that inner loop is running for O(nlog(n)) times but outer is running for O(n) so overall time complexity is O(n*nlog(n)) but I was wrong. As inner loop is not running for O(nlog(n)) times for every i , instead for overall all i the the condition inside the inner loop is running for O(nlog(n))

Unchained_Fate

Can anyone tell why this latest code gets passed ?? 390532511

for n=100000 and a[i]=0 for every i, it should TLE right

Tsukasa_Tsukuyomi

Then there doesn't exist a set B that satisfies the constraints, as $$$a_n = 0$$$ implies that every number from $$$0$$$ to $$$n - 1$$$ must be excluded from B.

read carefully, B can be empty

the submission runs in 46ms, but when i custom test it with your test, its 1765ms, so the tests are weak. it should techincally TLE, maybe c++ is fast. And CutSandstone, next time you should make n to 2e5 bro, n^2 solution can pass

how is it passing when you custom test it? wont it be in the order of n^2?

its n^2, but since n = 1e5 (not 2e5) and also c++ is VERY fast (pragma even faster sometimes)

Arbuzik342

Я:

Пишу задачу 2263E за O(N!*N^2)

Решение получает TLE на втором тесте

Не, а что я не так делаю?

seicode

nice contest, learn a lot

aalp75

can anyone suggest good ressources to learn more about the div2 C2 DP trick to count subset with interval conditions or other similar problems please? Thanks!

dinhhuubaonam123

I love this B!

I believe i have a simpler solution (implementation-wise) for D1A2: https://codeforces.me/contest/2262/submission/390455393 The idea is that you mark bad elements with difference arrays and only work with a "continuous" range of free elements (elements that can be used). In my opinion it makes calculating dp[] a bit easier

Wax

the last part of the editorial of Div2D is preety much planless in describing the solution....the two cases if the previous champions win or not win is not described as much to understand properly....Same also for C2....Editorial should have easily understandable for all range of coders!

cosmic_void

I don't know where I am going wrong in C1.. https://codeforces.me/contest/2263/submission/390687639 this is my last updated solution..

← Rev. 7 →

I just discovered a perhaps easier alternate way to look at problem E

The problem is actually equivalent to the following:

Build the graph similarly to the editorial for E. Call indices i where a[i] < b[i] be bad indices. Let bad[i] be the ith bad index. Then, check for all i < bad.size()-1, whether it is possible to reach bad[i+1] from b[bad[i]].

This can be derived from the editorial. If bad[i] and bad[i+1] are in the same SCC, bad[i] cannot be the largest index in the SCC, and hence b[i] must also be in the SCC. We can obviously reach bad[i+1] from b[bad[i]].

If bad[i] and bad[i+1] are not in the same SCC, we can claim that the SCC that contains bad[i] is before the SCC that contains bad[i+1] in the chain (see proof below). Since bad[i+1] is in a later SCC, we must be able to visit it afterwards. Hence, the remaining walk gives a path from b[bad[i]] to bad[i+1].

Exact proof of claim: Suppose the SCC containing bad[i+1] comes first instead. Since the maximum index increases along the SCC chain(because b[i] >= i), the SCC containing bad[i] has some index larger than bad[i+1]. A path from that index down to bad[i] must cross bad[i+1], and because each node’s possible destinations form an interval with b[u] >= u, we can redirect the crossing edge to bad[i+1]. This means the later SCC can reach the earlier SCC, a contradiction.

Implementation: 390720502

PS: I wonder what is the magic solution

LNight121

7 недель назад, скрыть # |

Has anyone else directly solved the single-point modification version of D Culling Game? It probably isn't much harder than the editorial's approach. This problem is just a special case of the single-point modification version (where the single point is modified to 0).

Solved using a segment tree, with time complexity O(n log² n) and space complexity O(n).

RiverFlow

In div1-C, we can actually test the b[n] value from a[2]->a[n-1].

Say m1=a[N], m2=a[i] (we let b[n]=m2)

The order should be 0 | m1 | m2 value on the left has the form k*(m1-m2), value on the right has the form k*(m2-m1) + m2.

we see that value that matches the left a[j]=k*(m1-m2) ==> a[j] can only match at most its number of divisors for m2 (so ~1000 for a[j]<=10^9). similarly for the right side ~1000 m2 that can match.

so when testing any value m2:

we can run and try to match each value, once an a[j] cannot match either left or right, we break. each value can only let at most 1k value m2 to pass it. So at most 1k * N pass can be made which make the complexity be 1k*N.

my sub: https://codeforces.me/contest/2262/submission/391009596

Sora213

+28

Div1D/Div2F Simpler Solution

I tried the question post contest and was able to solve it quite easily compared to what a 2800 would require so went to editorial to verify whether this was intended or what to find out it is probably the magic solution so here is the proof:

Note: I didn't read the editorial properly since the method was completely different and much more complex so I might mention things already mentioned in the editorial.

We are given two arrays, a and b and needs to make a equal to b with two types of operation -> Operation 1 for incrementing the array by 1 and Operation 2 for traversal, and we require to start from some random node and with these two operations achieve the array equality if possible.

Claim 1: Since we only increase the element and b[i] >= i, it is always better to select the smallest index where a[i] != b[i].

Claim 2: If we are at index i and wishes to go to index j > i, we shall only go there if b[i] == j.

Case 1: It doesn't make sense to go back to i from j.

Since j > i, we can only come back to i as long as current value of a[j] <= i and it doesn't make sense to come back since a[j] < b[j] as b[j] >= j && i < j leaving a[j] unfixed and we have to go to j again from some other node to fix it and could have achieved these steps of increasing a[j] to i that time as well making the operation not profitable.

Case 2: It doesn't make sense to go back to i from k < j. Same reason as above, still a[j] < b[j] as b[j] >= j && k < j and still have to fix j as well as k from some other node.

Case 3: It doesn't make sense to go back to i from k > j.

Assuming Claim-2 holds, k = b[j], in this case, we can only go back to i if a[k] <= i, it that case firstly k is not done and must be reachable from some other node to fix it, secondly if a[k] <= i then a[k] < j, this node could have been used to fix up j and didn't require j to be fixed by going there from i and if k can only be reached from j, then atleast either i or k must be left unfixed making the ans not possible.

Since we covered all 3 cases, the claim must hold.

Claim 3: If some j < i is unfixed and we can reach j from i, we shall go there to fix it.

Reason: From claim-2, if we go to j, we must fix it completely before going to any k > j. If doing so leaves i as unfixed, not going to j would have left j as unfixed as if we can go to j from some other node v, we could also reach i and v > i since we reached v by not going to any node less than i from it, we could have fixed j from i itself and used v to go back to i. Incase visiting v is not possible if we go to j, then going to j from v to fix it will leave v unfixed and again not solve anything.

Claim 4: When b[i] == i, the traversal ends.

It can be proved that for a valid solution to exist the four claims will also give a valid solution though i might not have articulated the claim 3 well but basically proving that going to j < i from i to fix j would not lead to ans if ans exist would lead to contradiction.

From these four claims, we can simulate the enitre way Bessie should traverse to make the two arrays equal. It shall be noted the claims at no point states anything regarding if it is possible to actually make the two arrays equal, it only states a valid path if the solution exists. So if on traversing based on these claims, at the end leads to a != b, then the no traversal shall lead to a == b and ans doesn't exist.

The proof for no traversal to exist is not explicitly written but on finding one would lead to solution when the claims failed to do so would again lead to contradiction. The first claim tells the start point, fourth claim the end point while second denotes forward traversal and third denotes back traversal.

We can direstly simulate this code and update a accordingly and when the traversal ends check if a == b to find out if it is possible or not.

Start node chosen by Claim 1. Lets say current node is cur initally equal to start node.

If a[cur] > b[cur] -> It is not possible to make then equal.
If a[cur] == b[cur]
a. If a[cur] == cur -> Claim 4 states traversal ends
b. Else Claim 2 -> cur = a[cur] with Operation-2
a. If a[cur] is not fixed -> Claim 3 -> cur = a[cur] with Operation-2

b. Since a[cur] is fixed, no need to go there so just increase a[i] = a[i]+1 with Operation-1.

Implementation: 391363278

Toradora

6 недель назад, скрыть # |

Authors please share the idea for dp solutions as well instead of just writing a one liner, C2 isn't that straight forward. Also, please write the hints instead of directly giving the tutorial.

Aryan_ism

i have best solution for problem B:

391083236

no memory used, simple to look at and easy to understand

№	Пользователь	Рейтинг
1	Benq	3676
2	Kevin114514	3659
3	jiangly	3640
4	turmax	3450
5	tourist	3382
6	strapple	3360
7	Um_nik	3354
8	squareOf105	3348
9	maroonrk	3312
10	idontwannadothis…e	3191

№	Пользователь	Вклад
1	Qingyu	155
2	nik_exists	151
3	maspy	149
4	AmShZ	145
5	Um_nik	143
6	Errichto	139
7	BledDest	136
8	adamant	134
9	maroonrk	132
10	cry	130

Блог пользователя kondasujay2

include <bits/stdc++.h>

define ll long long