Thanks everybody for participating in the round!↵
↵
### [A. Shortest Increasing Path](https://codeforces.me/contest/2147/problem/A)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:BernatP,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
How big can the answer be?↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
Which coordinates can you reach in $2$ or $3$ moves?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147A]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define endl '\n'↵
using namespace std;↵
#define int long long↵
↵
signed main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
int t;↵
cin>>t;↵
while(t--){↵
int x,y;↵
cin>>x>>y;↵
if(x==y || x==y+1 || y==1)cout<<-1<<endl;↵
else if(x<y)cout<<2<<endl;↵
else cout<<3<<endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
### [B. Multiple Construction](https://codeforces.me/contest/2147/problem/B)↵
Author: [user:danx,2025-09-20] Preparation: [user:danx,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Don't over complicate, there is a simple construction↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
There is a construction where each number $x$ is placed at distance either $x$ or $2 \cdot x$.↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Here is a construction where only the number $n$ is placed at distance $n$. All other numbers are placed at distance $2 \cdot x$.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
There is a construction where the first element of the array is always $n$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147B]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int t, n;↵
↵
signed main() {↵
ios::sync_with_stdio(false); cin.tie(nullptr);↵
↵
cin >> t;↵
while (t--) {↵
cin >> n;↵
for (int i = n; i >= 1; i--) {↵
cout << i << " ";↵
}↵
cout << n;↵
for (int i = 1; i < n; i++) {↵
cout << " " << i;↵
}↵
cout << "\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
### [C. Rabbits](https://codeforces.me/contest/2147/problem/C)↵
Author: [user:misteg168,2025-09-20] Preparation: [user:misteg168,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
If we have two consecutive $1$'s, the rabbits on the left and right of this block are independent. We can divide our problem into multiple subproblems.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
If one of these subproblems mentioned in hint $1$ contains two consecutive 0's, can we solve this subproblem?↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
If we don't have consecutive $0$'s in these subproblems mentioned in hint $1$, the pattern looks like $10101 \dots 10101$, in which of these patterns can we place the rabbits?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147C]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n; cin >> n;↵
string s; cin >> s;↵
bool ok = true;↵
bool curr = (s[0] == '1');↵
int cnt = 0;↵
for (int i = 0; i < n; i++) {↵
if (s[i] == '0')↵
cnt++;↵
if (i == 0)↵
continue;↵
if (s[i] == s[i-1] && s[i] == '0')↵
curr = false;↵
if (s[i] == s[i-1] && s[i] == '1') {↵
if (curr && cnt % 2 == 1)↵
ok = false;↵
curr = true;↵
cnt = 0;↵
}↵
}↵
↵
if (curr && cnt % 2 == 1 && s[n-1] == '1')↵
ok = false;↵
↵
cout << (ok ? "YES" : "NO") << "\n";↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int T; cin >> T;↵
while (T--)↵
solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
### [D. Game on Array](https://codeforces.me/contest/2147/problem/D)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:BernatP,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Solve small cases.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
What happens when every value is even?↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
How can we add exactly one odd number to the solution of hint 2?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147D]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339613659]↵
</spoiler>↵
↵
### [E. Maximum OR Popcount](https://codeforces.me/contest/2147/problem/E)↵
Author: [user:Pablo-No,2025-09-20] Preparation: [user:Pablo-No,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
The answer is bounded by $31$.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
We will precalculate the minimum operations for each answer.↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
How will the bitwise or look like if we want to increase the popcount↵
from the original by increasing the number of $1$'s.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
We can show that it is better to fill the least significant $0$'s first.↵
</spoiler>↵
↵
<spoiler summary="Hint5">↵
What is the best way to fill a certain bit.↵
</spoiler>↵
↵
<spoiler summary="Hint6">↵
The solution is a greedy algorithm.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147E]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339612536]↵
</spoiler>↵
↵
### [F. Exchange Queries](https://codeforces.me/contest/2147/problem/F)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:misteg168,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Try to understand what are the SCCs.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
They are a line. Given the sizes of the SCC, find a closed formula for the answer.↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Think how to maintain the formula using data structures.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147F]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339608901]↵
</spoiler>↵
↵
### [G. Modular Tetration](https://codeforces.me/contest/2147/problem/G)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:BernatP,2025-09-20]↵
↵
<spoiler summary="About cheaters">↵
There was a lot of cheating on this problem, which is why there were many in-contest solves. Cheaters will be banned. We’re sorry if the high solve count during the contest misled anyone, but please understand that this isn’t something the authors, coordinators, or codeforces can control.↵
</spoiler>↵
↵
<spoiler summary="Hint1">↵
What happens when $n$ is big?↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
$b_n$ is $a^{a^N}$ for some big $N$.↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Given $a$ and $m$ find a condition for $a$ to be $m$-tetrative.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
The condition is $\forall p|ord_m(a), p|a$.↵
</spoiler>↵
↵
<spoiler summary="Hint5">↵
Fix the number of values of $a$ such that $ord_m(a) = k$ and get a formula.↵
</spoiler>↵
↵
<spoiler summary="Hint6">↵
If $m$ is an odd prime power, the number above for $k|\varphi(m)$ is $\varphi(k)$.↵
</spoiler>↵
↵
<spoiler summary="Hint7">↵
Manipulate the formula until it only depends on the prime divisors of $\varphi(m)$ that are not in $m$.↵
</spoiler>↵
↵
<spoiler summary="Hint8">↵
Factor it to calculate it in $O(\log m)$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147G]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339609655]↵
</spoiler>↵
↵
### [H. Maxflow GCD Coloring](https://codeforces.me/contest/2147/problem/H)↵
Author: [user:FelixMP,2025-09-20] Preparation: [user:FelixMP,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Think of min-cut instead of max-flow.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
Can you think of a sufficient condition so that all the min-cuts between any pair of vertices are divisible by the same number?↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
In fact, the expected sufficient condition implies that all cuts of the graph (not just min-cuts) are divisible by the same number.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
The minimum number of colors is always $1$ or $2$. You can check if the answer is $1$ by brute force. ↵
</spoiler>↵
↵
<spoiler summary="Hint5">↵
It is possible to make all cuts even in each induced subgraph using just $2$ colors. ↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147H]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339609874]↵
</spoiler>↵
↵
### [I1. Longest Increasing Path (Easy Version)](https://codeforces.me/contest/2147/problem/I1)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:BernatP,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
The expected is $n = mlogm - O(m)$ steps using harmonic sum.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
Think of a solution in 2D (not needed but good intuition).↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Put points as an almost regular polygon and keep doing circles around it jumping with step $1$, then $2$, then $3$...↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
Think how to project this solution to 1D↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147I1]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339610927]↵
</spoiler>↵
↵
↵
### [I2. Longest Increasing Path (Hard Version)](https://codeforces.me/contest/2147/problem/I2)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:BernatP,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
There is a $n = 2m-3$ solution that will be useful: given two groups of points in arithmetic progression far enough apart you can add two pivots in the middle to keep jumping from the left to the right group: ..... .. .....↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
The goal is to recursively construct a solution using smaller ones.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147I2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339611036]↵
</spoiler>↵
↵
↵
### [A. Shortest Increasing Path](https://codeforces.me/contest/2147/problem/A)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:BernatP,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
How big can the answer be?↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
Which coordinates can you reach in $2$ or $3$ moves?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147A]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define endl '\n'↵
using namespace std;↵
#define int long long↵
↵
signed main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
int t;↵
cin>>t;↵
while(t--){↵
int x,y;↵
cin>>x>>y;↵
if(x==y || x==y+1 || y==1)cout<<-1<<endl;↵
else if(x<y)cout<<2<<endl;↵
else cout<<3<<endl;↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
### [B. Multiple Construction](https://codeforces.me/contest/2147/problem/B)↵
Author: [user:danx,2025-09-20] Preparation: [user:danx,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Don't over complicate, there is a simple construction↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
There is a construction where each number $x$ is placed at distance either $x$ or $2 \cdot x$.↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Here is a construction where only the number $n$ is placed at distance $n$. All other numbers are placed at distance $2 \cdot x$.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
There is a construction where the first element of the array is always $n$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147B]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int t, n;↵
↵
signed main() {↵
ios::sync_with_stdio(false); cin.tie(nullptr);↵
↵
cin >> t;↵
while (t--) {↵
cin >> n;↵
for (int i = n; i >= 1; i--) {↵
cout << i << " ";↵
}↵
cout << n;↵
for (int i = 1; i < n; i++) {↵
cout << " " << i;↵
}↵
cout << "\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
### [C. Rabbits](https://codeforces.me/contest/2147/problem/C)↵
Author: [user:misteg168,2025-09-20] Preparation: [user:misteg168,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
If we have two consecutive $1$'s, the rabbits on the left and right of this block are independent. We can divide our problem into multiple subproblems.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
If one of these subproblems mentioned in hint $1$ contains two consecutive 0's, can we solve this subproblem?↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
If we don't have consecutive $0$'s in these subproblems mentioned in hint $1$, the pattern looks like $10101 \dots 10101$, in which of these patterns can we place the rabbits?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147C]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n; cin >> n;↵
string s; cin >> s;↵
bool ok = true;↵
bool curr = (s[0] == '1');↵
int cnt = 0;↵
for (int i = 0; i < n; i++) {↵
if (s[i] == '0')↵
cnt++;↵
if (i == 0)↵
continue;↵
if (s[i] == s[i-1] && s[i] == '0')↵
curr = false;↵
if (s[i] == s[i-1] && s[i] == '1') {↵
if (curr && cnt % 2 == 1)↵
ok = false;↵
curr = true;↵
cnt = 0;↵
}↵
}↵
↵
if (curr && cnt % 2 == 1 && s[n-1] == '1')↵
ok = false;↵
↵
cout << (ok ? "YES" : "NO") << "\n";↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int T; cin >> T;↵
while (T--)↵
solve();↵
}↵
~~~~~↵
</spoiler>↵
↵
### [D. Game on Array](https://codeforces.me/contest/2147/problem/D)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:BernatP,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Solve small cases.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
What happens when every value is even?↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
How can we add exactly one odd number to the solution of hint 2?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147D]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339613659]↵
</spoiler>↵
↵
### [E. Maximum OR Popcount](https://codeforces.me/contest/2147/problem/E)↵
Author: [user:Pablo-No,2025-09-20] Preparation: [user:Pablo-No,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
The answer is bounded by $31$.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
We will precalculate the minimum operations for each answer.↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
How will the bitwise or look like if we want to increase the popcount↵
from the original by increasing the number of $1$'s.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
We can show that it is better to fill the least significant $0$'s first.↵
</spoiler>↵
↵
<spoiler summary="Hint5">↵
What is the best way to fill a certain bit.↵
</spoiler>↵
↵
<spoiler summary="Hint6">↵
The solution is a greedy algorithm.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147E]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339612536]↵
</spoiler>↵
↵
### [F. Exchange Queries](https://codeforces.me/contest/2147/problem/F)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:misteg168,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Try to understand what are the SCCs.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
They are a line. Given the sizes of the SCC, find a closed formula for the answer.↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Think how to maintain the formula using data structures.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147F]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339608901]↵
</spoiler>↵
↵
### [G. Modular Tetration](https://codeforces.me/contest/2147/problem/G)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:BernatP,2025-09-20]↵
↵
<spoiler summary="About cheaters">↵
There was a lot of cheating on this problem, which is why there were many in-contest solves. Cheaters will be banned. We’re sorry if the high solve count during the contest misled anyone, but please understand that this isn’t something the authors, coordinators, or codeforces can control.↵
</spoiler>↵
↵
<spoiler summary="Hint1">↵
What happens when $n$ is big?↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
$b_n$ is $a^{a^N}$ for some big $N$.↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Given $a$ and $m$ find a condition for $a$ to be $m$-tetrative.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
The condition is $\forall p|ord_m(a), p|a$.↵
</spoiler>↵
↵
<spoiler summary="Hint5">↵
Fix the number of values of $a$ such that $ord_m(a) = k$ and get a formula.↵
</spoiler>↵
↵
<spoiler summary="Hint6">↵
If $m$ is an odd prime power, the number above for $k|\varphi(m)$ is $\varphi(k)$.↵
</spoiler>↵
↵
<spoiler summary="Hint7">↵
Manipulate the formula until it only depends on the prime divisors of $\varphi(m)$ that are not in $m$.↵
</spoiler>↵
↵
<spoiler summary="Hint8">↵
Factor it to calculate it in $O(\log m)$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147G]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339609655]↵
</spoiler>↵
↵
### [H. Maxflow GCD Coloring](https://codeforces.me/contest/2147/problem/H)↵
Author: [user:FelixMP,2025-09-20] Preparation: [user:FelixMP,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
Think of min-cut instead of max-flow.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
Can you think of a sufficient condition so that all the min-cuts between any pair of vertices are divisible by the same number?↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
In fact, the expected sufficient condition implies that all cuts of the graph (not just min-cuts) are divisible by the same number.↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
The minimum number of colors is always $1$ or $2$. You can check if the answer is $1$ by brute force. ↵
</spoiler>↵
↵
<spoiler summary="Hint5">↵
It is possible to make all cuts even in each induced subgraph using just $2$ colors. ↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147H]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339609874]↵
</spoiler>↵
↵
### [I1. Longest Increasing Path (Easy Version)](https://codeforces.me/contest/2147/problem/I1)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:BernatP,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
The expected is $n = mlogm - O(m)$ steps using harmonic sum.↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
Think of a solution in 2D (not needed but good intuition).↵
</spoiler>↵
↵
<spoiler summary="Hint3">↵
Put points as an almost regular polygon and keep doing circles around it jumping with step $1$, then $2$, then $3$...↵
</spoiler>↵
↵
<spoiler summary="Hint4">↵
Think how to project this solution to 1D↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147I1]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339610927]↵
</spoiler>↵
↵
↵
### [I2. Longest Increasing Path (Hard Version)](https://codeforces.me/contest/2147/problem/I2)↵
Author: [user:BernatP,2025-09-20] Preparation: [user:BernatP,2025-09-20]↵
↵
<spoiler summary="Hint1">↵
There is a $n = 2m-3$ solution that will be useful: given two groups of points in arithmetic progression far enough apart you can add two pivots in the middle to keep jumping from the left to the right group: ..... .. .....↵
</spoiler>↵
↵
<spoiler summary="Hint2">↵
The goal is to recursively construct a solution using smaller ones.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
[tutorial:2147I2]↵
</spoiler>↵
↵
<spoiler summary="Code">↵
[submission:339611036]↵
</spoiler>↵
↵
