As of Feb 26, 2026. I am not aware of an editorial on this section. So I decided to write it here.↵
If you see any mistake or have an alternative solution, I'd be glad if you tell me in the comments.↵
↵
Notes (2026-02-26):↵
↵
1. The codes given are my AC codes on CSES. They are written at very different times. Therefore, you might expect some jumps in coding style among the solutions.↵
↵
2. I am not good at implementing. Sometimes I make solutions harder to understand in exchange for them being easier to implement. If you can't understand the solution, feel free to ask.↵
↵
3. I haven't been able to AC Grid Path Construction yet. I do have a solution in mind though. (Therefore the solution is not checked by AC, if you find any mistake please tell me).↵
↵
[Inverse Inversions](https://cses.fi/problemset/task/2214/)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
How do you construct an array with one inversions? How about three? How about six?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
You can only scramble the order of the small numbers and keep the large ones ordered. Try the sample test case.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
In the sample, you can construct `3 2 4 1 5`. Where 1, 2, 3 are in reverse order and 4 adds an inversion by being before 1. Try to generalize this.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
We start with $a_i=i$ with $0$ inversions.↵
First, find the largest $m$ such that $\frac{m(m-1)}{2}\leq k$. Reverse the first $m$ numbers to get $\frac{m(m-1)}{2}$ inversions. $m$ can be found by brute force.↵
↵
And then let $k'=k-\frac{m(m-1)}{2}$, this is how many inversion you needed left. Swap the number $m+1$ just $k'$ spots to the left and we're done.↵
↵
(You can use a stack or vector to reverse as well, as shown in the code).↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
int a[1000005];↵
↵
int main(){↵
vector <int> pre;↵
int n, id;↵
ll tg;↵
cin>>n>>tg;↵
id=0;↵
while(tg-id>0){↵
pre.pb(id+1);↵
tg-=id;↵
id++;↵
}↵
for(int i=1; i<=n; i++) a[i]=i;↵
reverse(a+1, a+id+1);↵
int k=tg;↵
id++;↵
while(k>0){↵
swap(a[id], a[id-1]);↵
id--;↵
k--;↵
}↵
for(int i=1; i<=n; i++) cout<<a[i]<<" ";↵
}↵
~~~~~↵
</spoiler>↵
↵
[Monotone Subsequences](https://cses.fi/problemset/task/2215)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
Solve the problem for $n=9$ and $k=3$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Put numbers in $\mod k$ order would be good. For example you have `3 6 9 1 4 7 2 5 8` for $n=9, k=3$. However, sometimes it won't work.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
If $k<\sqrt{n}$ it becomes impossible. For proof, search for the Erdős–Szekeres Theorem.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
See hint 3 for impossible cases.↵
↵
For the possible cases. Put all numbers that are $0 \mod k$ in increasing order, then all numbers that are $1\mod k$ in increasing order, then put $2 \mod k$ ones, and so on.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
int main(){↵
int t;↵
cin>>t;↵
while(t--){↵
vector <int> v;↵
int n,k;↵
cin>>n>>k;↵
if(k*k<n){↵
cout<<"IMPOSSIBLE\n";↵
continue;↵
}↵
for(int i=0; i<k; i++){↵
for(int j=1; j<=k; j++){↵
v.pb(j*k-i);↵
}↵
}↵
for(int i: v){↵
if(i<=n) cout<<i<<" ";↵
}↵
cout<<'\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[Third Permutation](https://cses.fi/problemset/task/3422/)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
For $a=[1,2,3,4], b=[4,3,1,2]$. Note that $[2,1,4,3]$ is a solution.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Build a graph with edges from $a_i$ to $b_i$ for every $i$, how do you construct a solution for the test case in hint 1? When does it not work?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Build a graph from $a_i$ to $b_i$ for every $i$. And then if there isn't any $2$-cycles in the graph, just make $c_i$ the index of the vertex where you walk $2$ steps from $a_i$. ↵
↵
If there is a $2$ cycle then $c_i=a_i$ for those two vertices. Store those pairs into a queue or vector, and then merge two pairs to make a new $4$-cycle any way you want. One pair might be left, then you need to merge the last pair into an existing cycle as well. $n=2$ is impossible.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
#define pii pair<int, int>↵
↵
const int MAXN=200005;↵
int a[MAXN], b[MAXN], pos[MAXN], g[MAXN], ans[MAXN], bad[MAXN];↵
queue <pii> qu;↵
↵
int main(){↵
int n;↵
cin>>n;↵
for(int i=1; i<=n; i++) cin>>a[i];↵
for(int i=1; i<=n; i++){↵
cin>>b[i];↵
pos[b[i]]=i;↵
g[a[i]]=b[i];↵
}↵
for(int i=1; i<=n; i++){↵
ans[i]=g[g[a[i]]];↵
if(ans[i]==a[i]){↵
if(!bad[i]) qu.push({i, pos[a[i]]});↵
bad[pos[a[i]]]=1;↵
bad[i]=1;↵
}↵
}↵
pii temp1, temp2;↵
while(qu.size()>1){↵
temp1=qu.front();↵
qu.pop();↵
temp2=qu.front();↵
qu.pop();↵
swap(ans[temp1.first], ans[temp2.first]);↵
swap(ans[temp2.second], ans[temp1.second]);↵
bad[temp1.first]=bad[temp2.first]=bad[temp1.second]=bad[temp2.second]=0;↵
}↵
if(!qu.empty()){↵
int x1=0, x2=0;↵
if(n==2){↵
cout<<"IMPOSSIBLE";↵
return 0;↵
}↵
temp1=qu.front();↵
qu.pop();↵
for(int i=1; i<=n; i++){↵
if(x1 && x2) break;↵
if(!bad[i]){↵
if(x1) x2=i;↵
else x1=i;↵
}↵
}↵
swap(ans[temp1.first], ans[x1]);↵
swap(ans[temp1.second], ans[x2]);↵
}↵
for(int i=1; i<=n; i++) cout<<ans[i]<<" ";↵
}↵
~~~~~↵
</spoiler>↵
↵
[Permutation Prime Sums](https://cses.fi/problemset/task/3423)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
Solve when $n=p-1$ where $p$ is a prime.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
A recursive solution is possible. How do you deal with the last few terms first?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Use any sieve method to find all primes below $10^6$.↵
↵
If $n+1$ is a prime then you solve directly by letting the first permutation be identity permutation and the second one be reversed.↵
↵
Otherwise, put the second one and the first both as identity first. Find an $i<n$ such that $n+i$ is prime, reverse the subarray from the $i$th term to the $n$th term and solve it for $n=i-1$ (recursively doing so until $n+1$ is prime where you hit the base case).↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
const int MAXN=200005;↵
bool prime[MAXN];↵
int ans[MAXN];↵
↵
void solve(int n){↵
if(prime[n+1]){↵
for(int i=1; i<=n; i++) ans[i]=n-i+1;↵
return;↵
}↵
for(int i=2; i<=n; i++){↵
if(prime[n+i]){↵
reverse(ans+i, ans+n+1);↵
solve(i-1);↵
break;↵
}↵
}↵
}↵
↵
int main(){↵
for(int i=2; i<MAXN; i++) prime[i]=1;↵
for(int i=2; i*i<MAXN; i++){↵
if(prime[i]){↵
for(int j=i*i; j<MAXN; j+=i) prime[j]=0;↵
}↵
}↵
ll n;↵
cin>>n;↵
for(int i=1; i<=n; i++) ans[i]=i;↵
solve(n);↵
for(int i=1; i<=n; i++) cout<<i<<" ";↵
cout<<'\n';↵
for(int i=1; i<=n; i++) cout<<ans[i]<<" ";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Proof">↵
As you might question in the solution: why does there always an $1\leq i<n$ such that $n+i$ is prime?↵
[Bertrand's Postulate](https://en.wikipedia.org/wiki/Bertrand%27s_postulate) tell us there is a prime $p$ such that $n<p<2n$ for all $n>1$. I don't know how to prove the theorem though so don't ask me.↵
</spoiler>↵
↵
[Chess Tournament](https://cses.fi/problemset/task/1697/)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
We first disregard the limit that each pair of player can play only one game. Develop a greedy solution (with the fact that the sum of $x_i$ is not too large.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Set the limit back. We know that the player who want to play the most matches matters, so we need to deal with them first. Can you deal with them greedily?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
What if a player want to play a lot of games and there are not enough opponents left during your greedy?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
From now on, if a player still wants to play $k$ games I said they have $k$ "remnant games".↵
↵
Use a priority queue to store how many remnants game are left for each player. Take out the one with the most remnant games and pair opponents with them (pair the opponents in decreasing order of remnant games). If at any moment the player with the most remnant games can't find enough opponents, then halt and output `IMPOSSIBLE`↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
#define pii pair<int, int>↵
↵
int tot;↵
int oddcnt;↵
priority_queue <pii> pq;↵
vector <pii> ans;↵
vector <pii> temp;↵
↵
int main(){↵
int n;↵
cin>>n;↵
int num;↵
bool possible=true;↵
for(int i=1; i<=n; i++){↵
cin>>num;↵
if(num>0) pq.push({num, i});↵
}↵
pii cur, nxt;↵
while(!pq.empty()){↵
cur=pq.top();↵
pq.pop();↵
if(cur.first>pq.size()){↵
possible=false;↵
break;↵
}↵
else{↵
for(int i=0; i<cur.first; i++){↵
nxt=pq.top();↵
pq.pop();↵
ans.pb({cur.second, nxt.second});↵
if(nxt.first>1) temp.pb({nxt.first-1, nxt.second});↵
}↵
while(temp.size()>0){↵
pq.push(temp.back());↵
temp.pop_back();↵
}↵
}↵
}↵
if(possible){↵
cout<<ans.size()<<'\n';↵
for(pii x: ans){↵
cout<<x.first<<" "<<x.second<<'\n';↵
}↵
}↵
else cout<<"IMPOSSIBLE";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
[Distinct Sums Grid](https://cses.fi/problemset/task/3424)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
Start with a wrong board. Try applying swaps to it. Which swaps would you want to perform?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
You'd only like the ones that increases the number of distinct row/column sums. But we don't know how to find them at all, so what do we do?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
$n<4$ can be checked to be impossible.↵
↵
Start with a board where every cell on the $i$th row is filled in with number $i$. This board would be incorrect but it's okay. We repeatedly randomly choose two cells to swap. If swapping them increase the number of distinct row/column sums then we swap them, otherwise we don't swap them. $50000$ random tries passes as my code do get AC.↵
↵
A bit on implementation, though. Carefully store the row/column sums and the number of distinct sum values. When you test performing a swap make sure to do it in $O(1)$ by these store values.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
const int MAXN=1005;↵
int g[MAXN][MAXN];↵
int r[MAXN], c[MAXN], r1, r2, c1, c2;↵
int cnt=0, ori;↵
int ex[1000005];↵
↵
void rem(int x){↵
ex[x]--;↵
if(ex[x]==0) cnt--;↵
}↵
↵
void add(int x){↵
ex[x]++;↵
if(ex[x]==1) cnt++;↵
}↵
↵
int res;↵
void change(int x1, int y1, int x2, int y2){↵
rem(r[x1]); rem(r[x2]); rem(c[y1]); rem(c[y2]);↵
r[x1]+=(g[x2][y2]-g[x1][y1]);↵
c[y1]+=(g[x2][y2]-g[x1][y1]);↵
r[x2]-=(g[x2][y2]-g[x1][y1]);↵
c[y2]-=(g[x2][y2]-g[x1][y1]);↵
add(r[x1]); add(r[x2]); add(c[y1]); add(c[y2]);↵
swap(g[x1][y1], g[x2][y2]);↵
}↵
↵
int main(){↵
int n;↵
cin>>n;↵
if(n<=3){↵
cout<<"IMPOSSIBLE";↵
return 0;↵
}↵
for(int i=1; i<=n; i++){↵
for(int j=1; j<=n; j++){↵
g[i][j]=i;↵
r[i]+=g[i][j];↵
c[j]+=g[i][j];↵
}↵
}↵
for(int i=1; i<=n; i++){↵
add(r[i]);↵
add(c[i]);↵
}↵
int sp=0;↵
while(cnt<2*n && sp<50000){↵
r1=rand()%n+1;↵
c1=rand()%n+1;↵
r2=rand()%n+1;↵
c2=rand()%n+1;↵
ori=cnt;↵
change(r1, c1, r2, c2);↵
if(cnt<ori) change(r1, c1, r2, c2);↵
sp++;↵
}↵
if(cnt<2*n){↵
cout<<"IMPOSSIBLE";↵
return 0;↵
}↵
for(int i=1; i<=n; i++){↵
for(int j=1; j<=n; j++){↵
cout<<g[i][j]<<" ";↵
}↵
cout<<'\n';↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[Filling Trominos](https://cses.fi/problemset/task/2423/)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
Try to find as many cases with no solutions first. The trivial requirements are that $3|mn$ and $\min(m, n)>1$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
When one of $m, n$ is $3$, and the other one is odd. This is impossible. Other cases that meet all the aforementioned requirements seems to not be disprovable.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
You can definitely construct a $2\times 3$ rectangle. What else can you construct?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
You can construct a $5\times 9$ rectangle!↵
↵
~~~~~↵
114414411↵
124112431↵
223552233↵
133451311↵
114411331↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
Try to do casework and decompose the board into $2\times 3$, $3\times 2$ and $5\times 9$ (or $9\times 5$) rectangles.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Please read all the hints first. From now on, I'd assume you had read them. We work on an $n\times m$ board ($n$ rows, $m$ columns).↵
↵
If $m=1$ or $n=1$ or $3\nmid mn$, then there's no solution.↵
↵
If one of $m, n$ is $3$ and the other one is odd, then there's no solution. That's it for the case with no solutions. From now on we would assume we are not on these cases.↵
↵
If $n=2$ then fill it with $2\times 3$ block.↵
↵
If $n>2$ but $n$ is even then still fill it with $2\times 3$ blocks, beware of adjacent letters.↵
↵
If $n$ is odd but $m$ is even. Fill the first $3 times m$ with $3\times 2$ blocks. Then it reduces to the last case.↵
↵
If they both are odd, then fill the top left $5\times 9$ first, and then fill the remaining $(n-5)\times 9$ on the left, and then the remaining board at last. You can do this recursively, just beware of adjacent letters.↵
↵
(My solution code might involve a transformation, though)↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
int g[100][100];↵
int aa[2][3]={{1,1,2},{1,2,2}};↵
int bb[3][2]={{1,1},{1,2},{2,2}};↵
int cc[5][9]={{1,1,4,4,1,4,4,1,1},{1,2,4,1,1,2,4,3,1},{2,2,3,5,5,2,2,3,3},{1,3,3,4,5,1,3,1,1},{1,1,4,4,1,1,3,3,1}};↵
string s="ABCDEFGHIJKLMNOPQRSTUVWXYZ";↵
↵
void put(int a, int b, int type, int t){↵
if(type==1){↵
for(int i=0; i<2; i++){↵
for(int j=0; j<3; j++){↵
g[a+i][b+j]=aa[i][j]+t;↵
}↵
}↵
}↵
else if(type==2){↵
for(int i=0; i<3; i++){↵
for(int j=0; j<3; j++){↵
g[a+i][b+j]=bb[i][j]+t;↵
}↵
}↵
}↵
else{↵
for(int i=0; i<5; i++){↵
for(int j=0; j<9; j++){↵
g[a+i][b+j]=cc[i][j]+t;↵
}↵
}↵
}↵
}↵
↵
void fill(int a, int b, int x, int y, int delta){↵
//delta is for not repeating letter for adjacent piece↵
if(x==2){//2*y board↵
for(int i=0; i<y; i+=3){↵
put(a, b+i, 1, delta);↵
}↵
return;↵
}↵
if(x%2==0){//2k*y board↵
int temp1=delta;↵
for(int i=0; i<x; i+=2){↵
if(i%4==0) fill(a+i, b, 2, y, temp1);↵
else fill(a+i, b, 2, y, temp1+2);↵
}↵
return;↵
}↵
else if(y%2==0){//x*2k board↵
int temp2=delta;↵
for(int i=0; i<y; i+=2){↵
if(i%4) put(a, b+i, 2, temp2+4);↵
else put(a, b+i, 2, temp2+6);↵
}↵
fill(a+3, b, x-3, y, temp2);↵
}↵
else{↵
//for other board, decompose them into↵
//one 5*9, one (x-5)*9, and one remaining chunk.↵
int temp3=delta;↵
put(a, b, 3, temp3+16);↵
fill(a+5, b, x-5, 9, temp3+12);↵
fill(a, b+9, x, y-9, temp3);↵
}↵
}↵
↵
void say(int x, int y, bool trans){↵
if(trans){↵
for(int i=0; i<y; i++){↵
for(int j=0; j<x; j++){↵
cout<<s[g[j][i]-1];↵
}↵
cout<<'\n';↵
}↵
}↵
else{↵
for(int i=0; i<x; i++){↵
for(int j=0; j<y; j++){↵
cout<<s[g[i][j]-1];↵
}↵
cout<<'\n';↵
}↵
}↵
}↵
↵
int main(){↵
int qq;↵
cin>>qq;↵
int m, n;↵
for(int i=1; i<=qq; i++){↵
cin>>m>>n;↵
if(m%3&&n%3){↵
cout<<"NO\n";↵
}↵
else if(m%2&&n%2&&(m==3||n==3)){↵
cout<<"NO\n";↵
}↵
else if(m==1||n==1){↵
cout<<"NO\n";↵
}↵
else if(n%3==0){↵
cout<<"YES\n";↵
fill(0,0,m,n,0);↵
say(m,n,false);↵
}↵
else{↵
cout<<"YES\n";↵
fill(0,0,n,m,0);↵
say(n,m,true);↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
[Grid Path Construction](https://cses.fi/problemset/task/2418)↵
------------------↵
↵
<spoiler summary="If you want the solution now, read this">↵
There is a [research paper](https://www.researchgate.net/publication/220616693_Hamilton_Paths_in_Grid_Graphs) you can view that contains a whole solution (but not implementation).↵
</spoiler>↵
↵
↵
<spoiler summary="TBD">↵
I come up with a slightly different solution. Haven't been able to implement it yet though.↵
But this tutorial is written at 2am-4am local time. I would try to update it when I can. At least I would put my solution here in a few days, I hope.↵
</spoiler>↵
↵
That's it for now. Tell me in the comment if there's anything you want to point out. I would update later.
If you see any mistake or have an alternative solution, I'd be glad if you tell me in the comments.↵
↵
Notes (2026-02-26):↵
↵
1. The codes given are my AC codes on CSES. They are written at very different times. Therefore, you might expect some jumps in coding style among the solutions.↵
↵
2. I am not good at implementing. Sometimes I make solutions harder to understand in exchange for them being easier to implement. If you can't understand the solution, feel free to ask.↵
↵
3. I haven't been able to AC Grid Path Construction yet. I do have a solution in mind though. (Therefore the solution is not checked by AC, if you find any mistake please tell me).↵
↵
[Inverse Inversions](https://cses.fi/problemset/task/2214/)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
How do you construct an array with one inversions? How about three? How about six?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
You can only scramble the order of the small numbers and keep the large ones ordered. Try the sample test case.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
In the sample, you can construct `3 2 4 1 5`. Where 1, 2, 3 are in reverse order and 4 adds an inversion by being before 1. Try to generalize this.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
We start with $a_i=i$ with $0$ inversions.↵
First, find the largest $m$ such that $\frac{m(m-1)}{2}\leq k$. Reverse the first $m$ numbers to get $\frac{m(m-1)}{2}$ inversions. $m$ can be found by brute force.↵
↵
And then let $k'=k-\frac{m(m-1)}{2}$, this is how many inversion you needed left. Swap the number $m+1$ just $k'$ spots to the left and we're done.↵
↵
(You can use a stack or vector to reverse as well, as shown in the code).↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
int a[1000005];↵
↵
int main(){↵
vector <int> pre;↵
int n, id;↵
ll tg;↵
cin>>n>>tg;↵
id=0;↵
while(tg-id>0){↵
pre.pb(id+1);↵
tg-=id;↵
id++;↵
}↵
for(int i=1; i<=n; i++) a[i]=i;↵
reverse(a+1, a+id+1);↵
int k=tg;↵
id++;↵
while(k>0){↵
swap(a[id], a[id-1]);↵
id--;↵
k--;↵
}↵
for(int i=1; i<=n; i++) cout<<a[i]<<" ";↵
}↵
~~~~~↵
</spoiler>↵
↵
[Monotone Subsequences](https://cses.fi/problemset/task/2215)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
Solve the problem for $n=9$ and $k=3$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Put numbers in $\mod k$ order would be good. For example you have `3 6 9 1 4 7 2 5 8` for $n=9, k=3$. However, sometimes it won't work.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
If $k<\sqrt{n}$ it becomes impossible. For proof, search for the Erdős–Szekeres Theorem.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
See hint 3 for impossible cases.↵
↵
For the possible cases. Put all numbers that are $0 \mod k$ in increasing order, then all numbers that are $1\mod k$ in increasing order, then put $2 \mod k$ ones, and so on.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
int main(){↵
int t;↵
cin>>t;↵
while(t--){↵
vector <int> v;↵
int n,k;↵
cin>>n>>k;↵
if(k*k<n){↵
cout<<"IMPOSSIBLE\n";↵
continue;↵
}↵
for(int i=0; i<k; i++){↵
for(int j=1; j<=k; j++){↵
v.pb(j*k-i);↵
}↵
}↵
for(int i: v){↵
if(i<=n) cout<<i<<" ";↵
}↵
cout<<'\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[Third Permutation](https://cses.fi/problemset/task/3422/)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
For $a=[1,2,3,4], b=[4,3,1,2]$. Note that $[2,1,4,3]$ is a solution.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Build a graph with edges from $a_i$ to $b_i$ for every $i$, how do you construct a solution for the test case in hint 1? When does it not work?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Build a graph from $a_i$ to $b_i$ for every $i$. And then if there isn't any $2$-cycles in the graph, just make $c_i$ the index of the vertex where you walk $2$ steps from $a_i$. ↵
↵
If there is a $2$ cycle then $c_i=a_i$ for those two vertices. Store those pairs into a queue or vector, and then merge two pairs to make a new $4$-cycle any way you want. One pair might be left, then you need to merge the last pair into an existing cycle as well. $n=2$ is impossible.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
#define pii pair<int, int>↵
↵
const int MAXN=200005;↵
int a[MAXN], b[MAXN], pos[MAXN], g[MAXN], ans[MAXN], bad[MAXN];↵
queue <pii> qu;↵
↵
int main(){↵
int n;↵
cin>>n;↵
for(int i=1; i<=n; i++) cin>>a[i];↵
for(int i=1; i<=n; i++){↵
cin>>b[i];↵
pos[b[i]]=i;↵
g[a[i]]=b[i];↵
}↵
for(int i=1; i<=n; i++){↵
ans[i]=g[g[a[i]]];↵
if(ans[i]==a[i]){↵
if(!bad[i]) qu.push({i, pos[a[i]]});↵
bad[pos[a[i]]]=1;↵
bad[i]=1;↵
}↵
}↵
pii temp1, temp2;↵
while(qu.size()>1){↵
temp1=qu.front();↵
qu.pop();↵
temp2=qu.front();↵
qu.pop();↵
swap(ans[temp1.first], ans[temp2.first]);↵
swap(ans[temp2.second], ans[temp1.second]);↵
bad[temp1.first]=bad[temp2.first]=bad[temp1.second]=bad[temp2.second]=0;↵
}↵
if(!qu.empty()){↵
int x1=0, x2=0;↵
if(n==2){↵
cout<<"IMPOSSIBLE";↵
return 0;↵
}↵
temp1=qu.front();↵
qu.pop();↵
for(int i=1; i<=n; i++){↵
if(x1 && x2) break;↵
if(!bad[i]){↵
if(x1) x2=i;↵
else x1=i;↵
}↵
}↵
swap(ans[temp1.first], ans[x1]);↵
swap(ans[temp1.second], ans[x2]);↵
}↵
for(int i=1; i<=n; i++) cout<<ans[i]<<" ";↵
}↵
~~~~~↵
</spoiler>↵
↵
[Permutation Prime Sums](https://cses.fi/problemset/task/3423)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
Solve when $n=p-1$ where $p$ is a prime.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
A recursive solution is possible. How do you deal with the last few terms first?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Use any sieve method to find all primes below $10^6$.↵
↵
If $n+1$ is a prime then you solve directly by letting the first permutation be identity permutation and the second one be reversed.↵
↵
Otherwise, put the second one and the first both as identity first. Find an $i<n$ such that $n+i$ is prime, reverse the subarray from the $i$th term to the $n$th term and solve it for $n=i-1$ (recursively doing so until $n+1$ is prime where you hit the base case).↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
const int MAXN=200005;↵
bool prime[MAXN];↵
int ans[MAXN];↵
↵
void solve(int n){↵
if(prime[n+1]){↵
for(int i=1; i<=n; i++) ans[i]=n-i+1;↵
return;↵
}↵
for(int i=2; i<=n; i++){↵
if(prime[n+i]){↵
reverse(ans+i, ans+n+1);↵
solve(i-1);↵
break;↵
}↵
}↵
}↵
↵
int main(){↵
for(int i=2; i<MAXN; i++) prime[i]=1;↵
for(int i=2; i*i<MAXN; i++){↵
if(prime[i]){↵
for(int j=i*i; j<MAXN; j+=i) prime[j]=0;↵
}↵
}↵
ll n;↵
cin>>n;↵
for(int i=1; i<=n; i++) ans[i]=i;↵
solve(n);↵
for(int i=1; i<=n; i++) cout<<i<<" ";↵
cout<<'\n';↵
for(int i=1; i<=n; i++) cout<<ans[i]<<" ";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Proof">↵
As you might question in the solution: why does there always an $1\leq i<n$ such that $n+i$ is prime?↵
[Bertrand's Postulate](https://en.wikipedia.org/wiki/Bertrand%27s_postulate) tell us there is a prime $p$ such that $n<p<2n$ for all $n>1$. I don't know how to prove the theorem though so don't ask me.↵
</spoiler>↵
↵
[Chess Tournament](https://cses.fi/problemset/task/1697/)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
We first disregard the limit that each pair of player can play only one game. Develop a greedy solution (with the fact that the sum of $x_i$ is not too large.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Set the limit back. We know that the player who want to play the most matches matters, so we need to deal with them first. Can you deal with them greedily?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
What if a player want to play a lot of games and there are not enough opponents left during your greedy?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
From now on, if a player still wants to play $k$ games I said they have $k$ "remnant games".↵
↵
Use a priority queue to store how many remnants game are left for each player. Take out the one with the most remnant games and pair opponents with them (pair the opponents in decreasing order of remnant games). If at any moment the player with the most remnant games can't find enough opponents, then halt and output `IMPOSSIBLE`↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
#define pii pair<int, int>↵
↵
int tot;↵
int oddcnt;↵
priority_queue <pii> pq;↵
vector <pii> ans;↵
vector <pii> temp;↵
↵
int main(){↵
int n;↵
cin>>n;↵
int num;↵
bool possible=true;↵
for(int i=1; i<=n; i++){↵
cin>>num;↵
if(num>0) pq.push({num, i});↵
}↵
pii cur, nxt;↵
while(!pq.empty()){↵
cur=pq.top();↵
pq.pop();↵
if(cur.first>pq.size()){↵
possible=false;↵
break;↵
}↵
else{↵
for(int i=0; i<cur.first; i++){↵
nxt=pq.top();↵
pq.pop();↵
ans.pb({cur.second, nxt.second});↵
if(nxt.first>1) temp.pb({nxt.first-1, nxt.second});↵
}↵
while(temp.size()>0){↵
pq.push(temp.back());↵
temp.pop_back();↵
}↵
}↵
}↵
if(possible){↵
cout<<ans.size()<<'\n';↵
for(pii x: ans){↵
cout<<x.first<<" "<<x.second<<'\n';↵
}↵
}↵
else cout<<"IMPOSSIBLE";↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
[Distinct Sums Grid](https://cses.fi/problemset/task/3424)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
Start with a wrong board. Try applying swaps to it. Which swaps would you want to perform?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
You'd only like the ones that increases the number of distinct row/column sums. But we don't know how to find them at all, so what do we do?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
$n<4$ can be checked to be impossible.↵
↵
Start with a board where every cell on the $i$th row is filled in with number $i$. This board would be incorrect but it's okay. We repeatedly randomly choose two cells to swap. If swapping them increase the number of distinct row/column sums then we swap them, otherwise we don't swap them. $50000$ random tries passes as my code do get AC.↵
↵
A bit on implementation, though. Carefully store the row/column sums and the number of distinct sum values. When you test performing a swap make sure to do it in $O(1)$ by these store values.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
const int MAXN=1005;↵
int g[MAXN][MAXN];↵
int r[MAXN], c[MAXN], r1, r2, c1, c2;↵
int cnt=0, ori;↵
int ex[1000005];↵
↵
void rem(int x){↵
ex[x]--;↵
if(ex[x]==0) cnt--;↵
}↵
↵
void add(int x){↵
ex[x]++;↵
if(ex[x]==1) cnt++;↵
}↵
↵
int res;↵
void change(int x1, int y1, int x2, int y2){↵
rem(r[x1]); rem(r[x2]); rem(c[y1]); rem(c[y2]);↵
r[x1]+=(g[x2][y2]-g[x1][y1]);↵
c[y1]+=(g[x2][y2]-g[x1][y1]);↵
r[x2]-=(g[x2][y2]-g[x1][y1]);↵
c[y2]-=(g[x2][y2]-g[x1][y1]);↵
add(r[x1]); add(r[x2]); add(c[y1]); add(c[y2]);↵
swap(g[x1][y1], g[x2][y2]);↵
}↵
↵
int main(){↵
int n;↵
cin>>n;↵
if(n<=3){↵
cout<<"IMPOSSIBLE";↵
return 0;↵
}↵
for(int i=1; i<=n; i++){↵
for(int j=1; j<=n; j++){↵
g[i][j]=i;↵
r[i]+=g[i][j];↵
c[j]+=g[i][j];↵
}↵
}↵
for(int i=1; i<=n; i++){↵
add(r[i]);↵
add(c[i]);↵
}↵
int sp=0;↵
while(cnt<2*n && sp<50000){↵
r1=rand()%n+1;↵
c1=rand()%n+1;↵
r2=rand()%n+1;↵
c2=rand()%n+1;↵
ori=cnt;↵
change(r1, c1, r2, c2);↵
if(cnt<ori) change(r1, c1, r2, c2);↵
sp++;↵
}↵
if(cnt<2*n){↵
cout<<"IMPOSSIBLE";↵
return 0;↵
}↵
for(int i=1; i<=n; i++){↵
for(int j=1; j<=n; j++){↵
cout<<g[i][j]<<" ";↵
}↵
cout<<'\n';↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[Filling Trominos](https://cses.fi/problemset/task/2423/)↵
------------------↵
↵
<spoiler summary="Hint 1">↵
Try to find as many cases with no solutions first. The trivial requirements are that $3|mn$ and $\min(m, n)>1$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
When one of $m, n$ is $3$, and the other one is odd. This is impossible. Other cases that meet all the aforementioned requirements seems to not be disprovable.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
You can definitely construct a $2\times 3$ rectangle. What else can you construct?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
You can construct a $5\times 9$ rectangle!↵
↵
~~~~~↵
114414411↵
124112431↵
223552233↵
133451311↵
114411331↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
Try to do casework and decompose the board into $2\times 3$, $3\times 2$ and $5\times 9$ (or $9\times 5$) rectangles.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Please read all the hints first. From now on, I'd assume you had read them. We work on an $n\times m$ board ($n$ rows, $m$ columns).↵
↵
If $m=1$ or $n=1$ or $3\nmid mn$, then there's no solution.↵
↵
If one of $m, n$ is $3$ and the other one is odd, then there's no solution. That's it for the case with no solutions. From now on we would assume we are not on these cases.↵
↵
If $n=2$ then fill it with $2\times 3$ block.↵
↵
If $n>2$ but $n$ is even then still fill it with $2\times 3$ blocks, beware of adjacent letters.↵
↵
If $n$ is odd but $m$ is even. Fill the first $3 times m$ with $3\times 2$ blocks. Then it reduces to the last case.↵
↵
If they both are odd, then fill the top left $5\times 9$ first, and then fill the remaining $(n-5)\times 9$ on the left, and then the remaining board at last. You can do this recursively, just beware of adjacent letters.↵
↵
(My solution code might involve a transformation, though)↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll long long↵
#define pb push_back↵
↵
int g[100][100];↵
int aa[2][3]={{1,1,2},{1,2,2}};↵
int bb[3][2]={{1,1},{1,2},{2,2}};↵
int cc[5][9]={{1,1,4,4,1,4,4,1,1},{1,2,4,1,1,2,4,3,1},{2,2,3,5,5,2,2,3,3},{1,3,3,4,5,1,3,1,1},{1,1,4,4,1,1,3,3,1}};↵
string s="ABCDEFGHIJKLMNOPQRSTUVWXYZ";↵
↵
void put(int a, int b, int type, int t){↵
if(type==1){↵
for(int i=0; i<2; i++){↵
for(int j=0; j<3; j++){↵
g[a+i][b+j]=aa[i][j]+t;↵
}↵
}↵
}↵
else if(type==2){↵
for(int i=0; i<3; i++){↵
for(int j=0; j<3; j++){↵
g[a+i][b+j]=bb[i][j]+t;↵
}↵
}↵
}↵
else{↵
for(int i=0; i<5; i++){↵
for(int j=0; j<9; j++){↵
g[a+i][b+j]=cc[i][j]+t;↵
}↵
}↵
}↵
}↵
↵
void fill(int a, int b, int x, int y, int delta){↵
//delta is for not repeating letter for adjacent piece↵
if(x==2){//2*y board↵
for(int i=0; i<y; i+=3){↵
put(a, b+i, 1, delta);↵
}↵
return;↵
}↵
if(x%2==0){//2k*y board↵
int temp1=delta;↵
for(int i=0; i<x; i+=2){↵
if(i%4==0) fill(a+i, b, 2, y, temp1);↵
else fill(a+i, b, 2, y, temp1+2);↵
}↵
return;↵
}↵
else if(y%2==0){//x*2k board↵
int temp2=delta;↵
for(int i=0; i<y; i+=2){↵
if(i%4) put(a, b+i, 2, temp2+4);↵
else put(a, b+i, 2, temp2+6);↵
}↵
fill(a+3, b, x-3, y, temp2);↵
}↵
else{↵
//for other board, decompose them into↵
//one 5*9, one (x-5)*9, and one remaining chunk.↵
int temp3=delta;↵
put(a, b, 3, temp3+16);↵
fill(a+5, b, x-5, 9, temp3+12);↵
fill(a, b+9, x, y-9, temp3);↵
}↵
}↵
↵
void say(int x, int y, bool trans){↵
if(trans){↵
for(int i=0; i<y; i++){↵
for(int j=0; j<x; j++){↵
cout<<s[g[j][i]-1];↵
}↵
cout<<'\n';↵
}↵
}↵
else{↵
for(int i=0; i<x; i++){↵
for(int j=0; j<y; j++){↵
cout<<s[g[i][j]-1];↵
}↵
cout<<'\n';↵
}↵
}↵
}↵
↵
int main(){↵
int qq;↵
cin>>qq;↵
int m, n;↵
for(int i=1; i<=qq; i++){↵
cin>>m>>n;↵
if(m%3&&n%3){↵
cout<<"NO\n";↵
}↵
else if(m%2&&n%2&&(m==3||n==3)){↵
cout<<"NO\n";↵
}↵
else if(m==1||n==1){↵
cout<<"NO\n";↵
}↵
else if(n%3==0){↵
cout<<"YES\n";↵
fill(0,0,m,n,0);↵
say(m,n,false);↵
}↵
else{↵
cout<<"YES\n";↵
fill(0,0,n,m,0);↵
say(n,m,true);↵
}↵
}↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
[Grid Path Construction](https://cses.fi/problemset/task/2418)↵
------------------↵
↵
<spoiler summary="If you want the solution now, read this">↵
There is a [research paper](https://www.researchgate.net/publication/220616693_Hamilton_Paths_in_Grid_Graphs) you can view that contains a whole solution (but not implementation).↵
</spoiler>↵
↵
↵
<spoiler summary="TBD">↵
I come up with a slightly different solution. Haven't been able to implement it yet though.↵
But this tutorial is written at 2am-4am local time. I would try to update it when I can. At least I would put my solution here in a few days, I hope.↵
</spoiler>↵
↵
That's it for now. Tell me in the comment if there's anything you want to point out. I would update later.
