Thanks everybody for participating in the round!↵
↵
### [Div2A. Blocked](https://codeforces.me/contest/2220/problem/A)↵
Author: [user:misteg168,2025-12-20] Preparation: [user:misteg168,2025-12-20]↵
↵
<spoiler summary="Hint1">↵
What happens when there are two equal elements?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2220A]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
for (auto &x : a)↵
cin >> x;↵
↵
sort(a.rbegin(), a.rend());↵
↵
for (int i = 0; i < n-1; i++)↵
if (a[i] == a[i+1]) {↵
cout << "-1\n";↵
return;↵
}↵
↵
for (auto x : a)↵
cout << x << " ";↵
cout << "\n";↵
}↵
↵
int main() {↵
int T;↵
cin >> T;↵
while (T--)↵
solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
### [Div2B. OIE excursion](https://codeforces.me/contest/2220/problem/B)↵
Author: [user:danx,2025-09-20] Preparation: [user:danx,2025-09-20]↵
↵
<spoiler summary="Solution">↵
[tutorial:2220B]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#pragma GCC optimize ("O3")↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int t, n, m;↵
↵
int main() {↵
↵
int t; cin >> t;↵
while(t--) {↵
int n, m; cin >> n >> m;↵
↵
int c, cnt, mx = 1;↵
↵
for(int i = 0; i < n; i++) {↵
int a; cin >> a;↵
↵
if (!i) {↵
c = a;↵
cnt = 1;↵
}↵
else if (a != c) {↵
c = a;↵
mx = max(mx, cnt);↵
cnt = 1;↵
}↵
else {↵
cnt++;↵
}↵
}↵
↵
mx = max(mx, cnt);↵
↵
if(mx < m) cout << "YES" << "\n";↵
else cout << "NO" << "\n";↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
### [Div1A Grid-L](https://codeforces.me/contest/2219/problem/A)↵
Author: [user:rlidon2006,2025-09-20] Preparation: [user:misteg168,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
We want an easy to check condition on $m$, $n$, $p$, $q$ that is equivalent to being able to fill the grid.↵
</spoiler>↵
↵
<spoiler summary="Hint2 (strong spoiler)">↵
You can fill the $m\times n$ grid if and only if $p+2q = m(n+1)+n(m+1)$ and $p\ge \vert m-n\vert$. (See tutorial for proof)↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
$p+2q = m(n+1) + n(m+1)$ is quadratic on $m$ and $n$. If you assume $m\ge n$, can you say anything on the size of $n$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2219A]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:370969986]↵
</spoiler>↵
↵
### [Div1B Unique values](https://codeforces.me/contest/2219/problem/B1)↵
Author: [user:misteg168,2025-12-20] Preparation: [user:misteg168,2025-12-20]↵
↵
↵
<spoiler summary="Solution B1">↵
[tutorial:2219B1]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission:371019251]↵
</spoiler>↵
↵
<spoiler summary="Solution B2">↵
[tutorial:2219B2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:371035963]↵
</spoiler>↵
↵
### [Div1C](https://codeforces.me/contest/2219/problem/C)↵
Author: [user:misteg168,2025-09-20] Preparation: [user:misteg168,2025-09-20]↵
↵
↵
<spoiler summary="Hint1">↵
Think of some kind of subtree DP.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2219C]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:370987541]↵
</spoiler>↵
↵
### [Div1D. MEX Replacement on Tree](https://codeforces.me/contest/2219/problem/D)↵
Author: [user:Misuki,2025-09-20] Preparation: [user:Misuki,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Having a good visual image of the problem in mind may help. That is, for each vertex, thinking there is an array of infinite slot, and some of them are occupied by token, and the operation correspond to moving certain token to the first hole.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
Draw some small cases! What would these infinite arrays change when doing operation on root?↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Doing operation on vertex with $p_v < f(v)$ is useless. Consider the rest situations.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
when doing operation on $v$, how would $f(x)$ change if $x$ is in subtree of $v$?↵
</spoiler>↵
↵
<spoiler summary="Hint5">↵
There are two cases, $f(x) = f(v)$ and $f(x) > f(v)$.↵
</spoiler>↵
↵
<spoiler summary="Hint6">↵
Solve https://judge.yosupo.jp/problem/vertex_add_subtree_sum↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2219D]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:371007707]↵
</spoiler>↵
↵
### [DivE. Weird Chessboard](https://codeforces.me/contest/2219/problem/E)↵
Author: [user:rlidon2006,2025-09-20] Preparation: [user:misteg168,2025-09-20], [user:rlidon2006,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Can you rewrite the condition on the board to something simpler?↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
Label the board $v_{i,j}$ where $v_{0,0}$ is the top left cell. We work mod $2$. A board $v_{i,j}$ is valid if and only if $v_{i,j}+v_{i+1,j}+v_{i,j+1}=0$ and all entries above the secondary diagonal are zero.↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Warm up: try to get a construction of density $1/4$.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
The next few hints get quite spoilery. If you don't want to see them yet but are stuck, consider coding some kind of heuristic (say, simulated annealing or A*) and running it on small values of $n$ to see what the result looks like.↵
</spoiler>↵
↵
<spoiler summary="Hint5">↵
Prove that the density is at most $1/3$.↵
</spoiler>↵
↵
<spoiler summary="Hint6">↵
Consider the grid $w_{i,j}$ with $w_{i,j}=1$ when $i+j\ge n-1$ and $i\not\equiv j\pmod 3$, and $w_{i,j}=0$ otherwise.↵
</spoiler>↵
↵
<spoiler summary="Hint7">↵
This grid is almost valid: $v_{i,j}+v_{i+1,j}+v_{i,j+1}=1$ only for very few concrete positions $(i,j)$. Try to fix the issues at those positions in a way that does not disturb much of the grid. ↵
</spoiler>↵
↵
<spoiler summary="Hint8">↵
For each position $(i_0, j_0)$ on the diagonal where $w_{i_0,j_0} = 0$, we want to add a pattern to the grid that fixes the issues there.↵
</spoiler>↵
↵
<spoiler summary="Hint9">↵
For each such $(i_0,j_0)$, flip $w_{i_0,j_0}$ and add a Pascal triangle mod $2$ to the grid.↵
</spoiler>↵
↵
<spoiler summary="Hint10">↵
To implement this in $O(n^2)$, instead of adding each pascal independently, try to compute the sum of all of the pascals directly.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2219E]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:371015865]↵
</spoiler>↵
↵
↵
↵
### [Div2A. Blocked](https://codeforces.me/contest/2220/problem/A)↵
Author: [user:misteg168,2025-12-20] Preparation: [user:misteg168,2025-12-20]↵
↵
<spoiler summary="Hint1">↵
What happens when there are two equal elements?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2220A]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
for (auto &x : a)↵
cin >> x;↵
↵
sort(a.rbegin(), a.rend());↵
↵
for (int i = 0; i < n-1; i++)↵
if (a[i] == a[i+1]) {↵
cout << "-1\n";↵
return;↵
}↵
↵
for (auto x : a)↵
cout << x << " ";↵
cout << "\n";↵
}↵
↵
int main() {↵
int T;↵
cin >> T;↵
while (T--)↵
solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
### [Div2B. OIE excursion](https://codeforces.me/contest/2220/problem/B)↵
Author: [user:danx,2025-09-20] Preparation: [user:danx,2025-09-20]↵
↵
<spoiler summary="Solution">↵
[tutorial:2220B]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#pragma GCC optimize ("O3")↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int t, n, m;↵
↵
int main() {↵
↵
int t; cin >> t;↵
while(t--) {↵
int n, m; cin >> n >> m;↵
↵
int c, cnt, mx = 1;↵
↵
for(int i = 0; i < n; i++) {↵
int a; cin >> a;↵
↵
if (!i) {↵
c = a;↵
cnt = 1;↵
}↵
else if (a != c) {↵
c = a;↵
mx = max(mx, cnt);↵
cnt = 1;↵
}↵
else {↵
cnt++;↵
}↵
}↵
↵
mx = max(mx, cnt);↵
↵
if(mx < m) cout << "YES" << "\n";↵
else cout << "NO" << "\n";↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
### [Div1A Grid-L](https://codeforces.me/contest/2219/problem/A)↵
Author: [user:rlidon2006,2025-09-20] Preparation: [user:misteg168,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
We want an easy to check condition on $m$, $n$, $p$, $q$ that is equivalent to being able to fill the grid.↵
</spoiler>↵
↵
<spoiler summary="Hint2 (strong spoiler)">↵
You can fill the $m\times n$ grid if and only if $p+2q = m(n+1)+n(m+1)$ and $p\ge \vert m-n\vert$. (See tutorial for proof)↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
$p+2q = m(n+1) + n(m+1)$ is quadratic on $m$ and $n$. If you assume $m\ge n$, can you say anything on the size of $n$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2219A]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:370969986]↵
</spoiler>↵
↵
### [Div1B Unique values](https://codeforces.me/contest/2219/problem/B1)↵
Author: [user:misteg168,2025-12-20] Preparation: [user:misteg168,2025-12-20]↵
↵
↵
<spoiler summary="Solution B1">↵
[tutorial:2219B1]↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission:371019251]↵
</spoiler>↵
↵
<spoiler summary="Solution B2">↵
[tutorial:2219B2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:371035963]↵
</spoiler>↵
↵
### [Div1C](https://codeforces.me/contest/2219/problem/C)↵
Author: [user:misteg168,2025-09-20] Preparation: [user:misteg168,2025-09-20]↵
↵
↵
<spoiler summary="Hint1">↵
Think of some kind of subtree DP.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2219C]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:370987541]↵
</spoiler>↵
↵
### [Div1D. MEX Replacement on Tree](https://codeforces.me/contest/2219/problem/D)↵
Author: [user:Misuki,2025-09-20] Preparation: [user:Misuki,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Having a good visual image of the problem in mind may help. That is, for each vertex, thinking there is an array of infinite slot, and some of them are occupied by token, and the operation correspond to moving certain token to the first hole.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
Draw some small cases! What would these infinite arrays change when doing operation on root?↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Doing operation on vertex with $p_v < f(v)$ is useless. Consider the rest situations.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
when doing operation on $v$, how would $f(x)$ change if $x$ is in subtree of $v$?↵
</spoiler>↵
↵
<spoiler summary="Hint5">↵
There are two cases, $f(x) = f(v)$ and $f(x) > f(v)$.↵
</spoiler>↵
↵
<spoiler summary="Hint6">↵
Solve https://judge.yosupo.jp/problem/vertex_add_subtree_sum↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2219D]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:371007707]↵
</spoiler>↵
↵
### [DivE. Weird Chessboard](https://codeforces.me/contest/2219/problem/E)↵
Author: [user:rlidon2006,2025-09-20] Preparation: [user:misteg168,2025-09-20], [user:rlidon2006,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Can you rewrite the condition on the board to something simpler?↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
Label the board $v_{i,j}$ where $v_{0,0}$ is the top left cell. We work mod $2$. A board $v_{i,j}$ is valid if and only if $v_{i,j}+v_{i+1,j}+v_{i,j+1}=0$ and all entries above the secondary diagonal are zero.↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Warm up: try to get a construction of density $1/4$.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
The next few hints get quite spoilery. If you don't want to see them yet but are stuck, consider coding some kind of heuristic (say, simulated annealing or A*) and running it on small values of $n$ to see what the result looks like.↵
</spoiler>↵
↵
<spoiler summary="Hint5">↵
Prove that the density is at most $1/3$.↵
</spoiler>↵
↵
<spoiler summary="Hint6">↵
Consider the grid $w_{i,j}$ with $w_{i,j}=1$ when $i+j\ge n-1$ and $i\not\equiv j\pmod 3$, and $w_{i,j}=0$ otherwise.↵
</spoiler>↵
↵
<spoiler summary="Hint7">↵
This grid is almost valid: $v_{i,j}+v_{i+1,j}+v_{i,j+1}=1$ only for very few concrete positions $(i,j)$. Try to fix the issues at those positions in a way that does not disturb much of the grid. ↵
</spoiler>↵
↵
<spoiler summary="Hint8">↵
For each position $(i_0, j_0)$ on the diagonal where $w_{i_0,j_0} = 0$, we want to add a pattern to the grid that fixes the issues there.↵
</spoiler>↵
↵
<spoiler summary="Hint9">↵
For each such $(i_0,j_0)$, flip $w_{i_0,j_0}$ and add a Pascal triangle mod $2$ to the grid.↵
</spoiler>↵
↵
<spoiler summary="Hint10">↵
To implement this in $O(n^2)$, instead of adding each pascal independently, try to compute the sum of all of the pascals directly.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2219E]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:371015865]↵
</spoiler>↵
↵
↵
