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.
Author: kondasujay2
Tutorial
Tutorial is loading...
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();
}
Author: sukon
Tutorial
Tutorial is loading...
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";
}
}
2263C1 - Floor of MEX (Easy Version) / 2262A1 - Floor of MEX (Easy Version)
Author: CutSandstone
Tutorial
Tutorial is loading...
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();
}
2263C2 - Floor of MEX (Hard Version) / 2262A2 - Floor of MEX (Hard Version)
Author: kondasujay2
Tutorial
Tutorial is loading...
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();
}
2263D - Culling Game / 2262B - Culling Game
Author: kondasujay2
Tutorial
Tutorial is loading...
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();
}
2263E - Traveling the World / 2262C - Traveling the World
Author: kondasujay2
Tutorial
Tutorial is loading...
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();
}
2263F - PLUSworld / 2262D - PLUSworld
Authors: sukon & kondasujay2
Tutorial
Tutorial is loading...
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
With this, you can prove a significantly simpler solution. We will add this proof later.
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';
}
}
2262E - Paired Bracket Sequences
Author: kondasujay2
Tutorial
Tutorial is loading...
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();
}
Authors: sukon & kondasujay2
Tutorial
Tutorial is loading...
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();
}
Tester Solution
Will be added later; credit to BurnedChicken for finding this in testing! This method results in a much simpler solution!
Spoiler
#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();
}
Auto comment: topic has been updated by kondasujay2 (previous revision, new revision, compare).
Auto comment: topic has been updated by sukon (previous revision, new revision, compare).
Nice Contest
Div1A2/Div2C2 can be solved in $$$O(n\log n)$$$ via counting sort if you store the smallest interval for each right endpoint.
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].
"Rate the problem" appears to have all the problems sharing the same rating votes
wow im stupid i will fix