100010 int x[MAXN],y[MAXN],a[MAXN],degree[MAXN]; int n,m; void work() {
cin>>n>>m; for (int i=1;i, > ~~~~~ #include using namespace std; void work, ]; void work() { cin>>n>>m>>k; for (int i=1;i<=k;i++) cin>>a[i]; bool flag;
long long, inline void File(){ cin.tie(nullptr)->sync_with_stdio(false); #ifdef zxyoi
freopen("my.in","r, template void ckmx(T &A,T B){ A, void Main(){ cin>>n>>m; for(int i=1;i<=n;++i) cin>>a[i]; for(int j=1;j<=m;++j)
cin>>b[j, void work() { ans.clear(); cin>>n; for (int i=1;i<=n;i++) { lv[i]=rv[i]=i; cin, void work() { diff.clear(); key={0,-0x3f3f3f3f3f3f3f3f}; cin>>n>>m; m*=2; for
(int i=1;i, void work() { int n; cin>>n; cout<<<' '; for (int i=1;i
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
Void
Last visit:
15 years ago
Registered:
17 years ago
2.
Codeforces Round #810 Editorial Sorry for the late editorial. May this editorial help you. If you have questions, feel free to ask.
[problem:1711A]
<spoiler summary="hint1.">
The minimal weight is at least $1$ since $1$ divides any integer (so $1$ divides $p_1$).
</spoiler>
<spoiler summary="solution">
Since $k+1$ does not divide $k$, a permutation with weight equal to $1$ is: $[n,1,2,\cdots,n-1]$.
</spoiler>
<spoiler summary="code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void work()
{
int n;
cin>>n;
cout<<n<<' ';
for (int i=1;i<n;i++)
cout<<i<<' ';
cout<<endl;
}
int main()
{
int casenum=1;
cin>>casenum;
for (int testcase=1;testcase<=casenum;testcase++)
work();
return 0;
}
~~~~~
</spoiler>
[problem:1711B]
<spoiler summary="hint1.">
See the party as a graph.
</spoiler>
<spoiler summary="hint2.">
Divide the vertices into two categories according to their degrees' parity.
</spoiler>
<spoiler summary="solution">
Let's consider ...
Tutorial of Codeforces Round 810 (Div. 1)
Tutorial of Codeforces Round 810 (Div. 2)
3.
Don't use rand(): a guide to random number generators in C++ Don't use `rand()`. Why? Let's jump right into some code. What value will the following code print, approximately?
~~~~~
#include <cstdlib>
#include <iostream>
using namespace std;
const int ITERATIONS = 1e7;
int main() {
double sum = 0;
for (int i = 0; i < ITERATIONS; i++)
sum += rand() % 1000000;
cout << "Average value: " << sum / ITERATIONS << '\n';
}
~~~~~
Should be about 500,000, right? Turns out it depends on the compiler, and on Codeforces it prints 16382, which isn't even close. [Try it out yourself](http://codeforces.me/contest/1025/customtest).
### What's happening here?
If you look up [C++ documentation on `rand()`](https://en.cppreference.com/w/cpp/numeric/random/rand), you'll see that it returns "a pseudo-random integral value between `0` and `RAND_MAX`." [Click again on `RAND_MAX`](https://en.cppreference.com/w/cpp/numeric/random/RAND_MAX) and you'll see that "This value is implementation dependent. It's guaranteed that th...
void srand(unsigned int seed) { holdrand = (long) seed; }
4.
C++ Tricks I see lots of programmers write code like this one:
~~~~~
pair<int, int> p;
vector<int> v;
// ...
p = make_pair(3, 4);
v.push_back(4); v.push_back(5);
~~~~~
while you can just do this:
~~~~~
pair<int, int> p;
vector<int> v;
// ...
p = {3, 4};
v = {4, 5};
~~~~~
[cut]
[This](http://codeforces.me/blog/entry/10124) is a great C++11 tutorial for those who want to know more about C++11.
#### 1. Assign value by a pair of {} to a container
I see lots of programmers write code like this one:
~~~~~
pair<int, int> p;
// ...
p = make_pair(3, 4);
~~~~~
while you can just do this:
~~~~~
pair<int, int> p;
// ...
p = {3, 4};
~~~~~
even a more complex `pair`
~~~~~
pair<int, pair<char, long long> > p;
// ...
p = {3, {'a', 8ll}};
~~~~~
What about `vector`, `deque`, `set` and other containers?
~~~~~
vector<int> v;
v = {1, 2, 5, 2};
for (auto i: v)
cout << i << ' ';
cout << '\n';
// prints "1 2 5 2"
deque<vector<pair<in...
void err(istream_iterator it) {} template void err
5.
[Tutorial] Matroid intersection in simple words **[This article is also available in [Russian](https://codeforces.me/blog/entry/69287?locale=ru)]**
Hello, CodeForces.
I think that matroids are beautiful and powerful concept, however, not really well known in competitive programming.
I’ve discovered matroids at 2019 Petrozavodsk Winter Training Camp. There was a problem that clearly cannot be solved using usual techniques I knew, editorial for this problem was just these three words “just matroid intersection”. Back then it took me more than 2 days of upsolving to find all the information and details I need and implement solution that gets Accepted on this. And it took way longer to actually understand why does it work and exactly how does it work. (I still hesitate in some details.)
Of course, it is not hard to google up all the definitions and some related articles, but in my opinion they all are focused more on mathematical part of theory, strict proofs in some not really obvious but short ways, and observing only ke...
void add_vector(Z2Vector new_vector) { vectors.push_back(new_vector); }, void gaussian_elimination() { for (int i = 0; i < size(); i++) { for (int j, void prepare_colorful_oracle() { for (int c = 0; c < color_count; c++) {
color_used[c, void prepare_linear_oracle() { basis.reset();, void reset() { vectors.clear(); }, void solve() { cin >> n; for (int i = 0; i < n; i++) { ground_set.emplace_back
6.
Blowing up unordered_map, and how to stop getting hacked on it C++ has always had the convenient data structures `std::set` and `std::map`, which are tree data structures whose operations take $O(\log n)$ time. With C++11, we finally received a hash set and hash map in `std::unordered_set` and `std::unordered_map`. Unfortunately, I've seen a lot of people on Codeforces get hacked or fail system tests when using these. In this post I'll explain how it's possible to break these data structures and what you can do in order to continue using your favorite hash maps without worrying about being hacked
[cut]
.
So how are they hackable? We always assume hash maps are $O(1)$ per operation (insert, erase, access, etc.). But this depends on a key assumption, which is that each item _only runs into $O(1)$ collisions on average_. If our input data is completely random, this is a reasonable assumption. But this is no longer a safe bet when the input isn't random, especially so if someone is adversarially designing inputs to our code (a.k.a. hacking ph...
void insert_numbers(long long x) { clock_t begin = clock(); unordered_map
7.
You won't believe how this simple trick defeated the unexplained bug destroying every top LGM ### TL;DR
Currently people are discussing a slowdown bug on Codeforces that seems to happen randomly, and can cause code to run 100x slower and get TLE. More details in [user:pajenegod,2024-03-03]'s [blog post](https://codeforces.me/blog/entry/126654).
In this article, I present a mitigation: add the following to your code.
~~~~
#include <windows.h>
void *operator new(size_t size) {
if (void *ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
throw std::bad_alloc{};
}
void operator delete(void *ptr) {
HeapFree(GetProcessHeap(), 0, ptr);
}
~~~~
<spoiler summary="If you use malloc/free in C++ (you shouldn't), also change them.">
~~~~
void *my_malloc(size_t size) {
if (void *ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
throw std::bad_alloc{};
}
void my_free(void *ptr) {
HeapFree(GetProcessHeap(), 0, ptr);
}
~~~~
</spoiler>
<spoiler summary="If you use aligned new/delete in C++, also change the...
~~~~ void, : add the following to your code. ~~~~ #include void *operator new(size_t size, void *alloc(size_t s) { auto c = new char[s]; asm volatile("" ::"r"(c)); return
c; }, void *alloc(size_t s) { auto t = high_resolution_clock::now(); auto p = (void
*)malloc(s, void *operator new(size_t size) { if (void *ptr = HeapAlloc(GetProcessHeap(),
0, size ? size, void dealloc(void *p) { auto t = high_resolution_clock::now(); free(p);
dealloc_time, void operator delete(void *ptr) { HeapFree(GetProcessHeap(), 0, ptr); }, ~~~~ #include void *operator new(size_t size) { if (void *ptr = HeapAlloc
8.
C++ tips and tricks Hello, codeforces.
I would like to tell you about some tricks and constructions I use in C++. They are not hidden or anything, moreover, most of them are from stl or maybe well known among software engineers, but I often see codes where something is done by hand in, say, 5 lines, while in stl there is a function which does the same.
The things below are filtered by my personal sense of non-popularity (so no `__builtin` functions) and usage frequency (so there almost surely are similar things I don't know about) and are not really sorted in any reasonable order. Let's begin. [cut]
<hr>
- ### `all(x)`
This may be an exception to the rule of non-popularity -- this is quite widely used, but some next items will depend on `all(x)`, so I define it here. So, I talk about
```[c++]
#define all(x) (x).begin(), (x).end()
```
Now sorting a vector looks like `sort(all(vec))` instead of `sort(vec.begin(), vec.end())`.
However, it's not all about this define. Imagine you nee...
```[c++] void show_binary(int n) { for (int i = 0; i < 20; ++i) { cout << !!(n
& (1
9.
Codeforces Global Round 5 Editorial Enjoy!
<spoiler summary="A. Balanced Rating Changes">
[tutorial:1237A]
<spoiler summary="Solution by tourist">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int flag = 1;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x % 2 == 0) {
cout << x / 2 << '\n';
} else {
cout << (x + flag) / 2 << '\n';
flag *= -1;
}
}
return 0;
}
~~~~~
</spoiler>
</spoiler>
<spoiler summary="B. Balanced Tunnel">
[tutorial:1237B]
<spoiler summary="Solution by tourist">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
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];
}
vector<int> pos(n);
for (int i = 0; i < n; i++) {
pos[b[i...
inline void addanswer(int x) { if (x <= 0) return; answer.pb(x); }, void doreverse(vector &v, int l) { reverse(v.begin(), v.begin() + l); for (int j, void make(int n){ dp1[0][0] = 1; for (int i = 1; i <= n; i++){ for (int j = 0; j, void perform(int l) { int fn = min(l + k, n); assert(psum[fn] >= 0); ll wassum, void restore(int l) { if (l >= n) return; if (a[l] == 0 && psum[l] == 0
10.
Catching silly mistakes with GCC As you know, the C++ language assumes that the programmer is always correct. Therefore C++ compilers don't add additional checks to the program, such as checks for null pointer dereference or out-of-bounds array access. This is good, because C++ programs run as fast as possible, and this is bad, because sometimes we may spend a long time debugging some silly mistake. We would want that the compiler can find such mistakes automatically. And many compilers can! In this post I will show various GCC options that do this. Previously [user:zakharvoit,2015-01-02] already wrote about this [here](/blog/entry/13875).
All options that will follow should be added to the GCC command line. In various IDEs you can do it in IDE or compiler settings. Many of the options can also be used with Clang (for example, in Xcode). For MSVC++, I think, there is nothing better than Debug mode and `/W4`.
[cut]
GCC warnings
------------------
Of course, the first step to debugging is to enable compi...
~~~~~ int n; void solve() { // Solve the problem } int main() { int n; cin >> n
11.
Complex FFT is not as bad as you think ... Probably.
Hi everyone!
As some of you _might_ already know, I don't like NTT. Primary reasons for this are:
- I don't like modular arithmetic optimizations (Montgomery, etc).
- I don't like NTT mods, and prefer good, old $10^9+7$.
- I do like algebra of complex numbers.
But, to my regret, the overwhelming mainstream in modern competitive programming is NTT. Primary reasons are:
- It's allegedly faster.
- It needs less memory.
- It has no precision issues.
- People don't like algebra of complex numbers.
There is nothing I can do about the last, but today I'll address the first 3. Optimizing complex FFT was on my mind for quite some time, but I didn't really work on it _that much_ until the [blog](https://codeforces.me/blog/entry/142063) by [user:Qwerty1232,2025-04-24] on optimizing NTT has dropped, which motivated me to actually put some serious effort into this.
In this blog, we will primarily focus on optimizations that are specific to complex arithmetic...
) { return base::allocate(n); } n *= sizeof(T); void* raw = mmap(nullptr, n, ```cpp void dot(cvector const& t) { size_t n = this->size(); exec_on_evals<1>(n
/ flen, void deallocate(T* p, std::size_t n) noexcept { if(n * sizeof(T) < 1024 * 1024
12.
Linear Recurrence and Berlekamp-Massey Algorithm **#IjustWantContribution**
It seems there isn't any blog about Berlekamp-Massey Algorithm around here, so I decided to go on a try. :P
Acknowledgement: Hats off to matthew99 for introducing this algorithm.
#### What is 'linear recurrence'?
Assuming there is a (probably infinity) sequence $a_0,a_1...a_{n-1}$, we call this sequence satisfies a linear recurrence relation $p_1,p_2...p_m$, iff $\forall i \geq m,~a_i=\sum_{j=1}^m a_{i-j}p_j$. (Obviously, if $m\geq n$ any $p$ can do :P)
#### How to calculate k-th term of a linear recurrence?
For a polynomial $f(x)=\sum_{i=0}^{t} c_ix^i$, we define $G(f)=\sum_{i=0}^{t} c_ia_i$.
Obviously $G$ satisfies $G(f)\pm G(g) =G(f \pm g)$.
Because $a_i=\sum_{j=1}^m a_{i-j}p_j$, if we let $f(x)=x^m-\sum_{j=1}^m x^{m-j}p_j$, then $G(f)=0$. Also $G(fx),G(fx^2)...=0$. So $G(fg)=0$ (g is any polynomial).
What we want is $G(x^k)$. Because $G(f\lfloor x^k/f\rfloor)=0$, then $G(x^k)=G(x^k \bmod f)$.
[cut]
We can calculate $x^k \b...
: first terms //h: relation ll a[SZ],h[SZ],t_[SZ],s[SZ],t[SZ]; //calculate p*q
mod f inlinevoid, [SZ],s[SZ],t[SZ]; //calculate p*q mod f inline void mull(ll*p,ll*q) { for(int
i=0;i
13.
VK Cup 2017 Round 3 + Codeforces Round #412 -- Tutorial Here is the tutorial of VK Cup 2017 Round 3 and Codeforces Round #412. Enjoy!
<spoiler summary="Is it rated?">
[tutorial:807A]
<spoiler summary="Code">
~~~~~
n = int(input())
results = []
for i in range(n):
results.append(list(map(int, input().split())))
for r in results:
if r[0] != r[1]:
print("rated")
exit()
for i in range(n):
for j in range(i):
if results[i][0] > results[j][0]:
print("unrated")
exit()
print("maybe")
~~~~~
</spoiler>
</spoiler>
<spoiler summary="T-Shirt Hunt">
[tutorial:807B]
<spoiler summary="More efficient code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int p, x, y;
cin >> p >> x >> y;
for (int s = y; ; s++) {
if (s % 50 != x % 50) {
continue;
}
bool me = false;
int i = s / 50 % 475;
for (int j = 0; j < 25; j++) {
i = (i * 96 + 42) % 475;
if (i + 26 == p) {
me = true;
...
- p * t >= y - x; } void solve() { ll x, y, p, q; scanf("%lld%lld%lld%lld",
&x, &y, &p, p, ll q, ll t) { return p * t >= x && q * t - p * t >= y - x; } void solve() {
ll x, y, p, void addans() { for (int i = 1; i <= n; i += 2) answer = (answer + odd[i]) %
mod; }, void build(int x, int l, int r) { add[x] = 0; if (l == r) { mn[x] =
make_pair(a[l].first, void conv(ll *from, comp *to) { for (int i = n + 1; i < st2; i++) tmp[i] = 0;
for (int i, void convback(comp *from, ll *to) { fft(from, st2, invw, tmp); for (int i = 0;
i < st2, void fft(comp *a, int n, comp *w, comp *res) { for (int i = 0; i < n; i++)
res[bitrev(i)] = a, void go(int A) { if (A == 1) { even[0] = 1; odd[0] = 0; odd[1, void modify(int x, int l, int r, int ll, int rr, int v) { if (ll <= l && r <=
rr) { add[x, void preparefft(int n) { for (int i = 0; i < n; i++) { int cur = i, void pull(int x) { mn[x] = min(mn[x + x], mn[x + x + 1]); }, void push(int x) { add[x + x] += add[x]; mn[x + x].first += add[x]; add[x + x +
1] += add, void solve() { ll x, y, p, q; scanf("%lld%lld%lld%lld", &x, &y, &p, &q);
14.
About Problemsetting (for AtCoder and Codeforces) Since the amount of information available about the preparation of a competitive programming contest for AtCoder/Codeforces is very little, I decided to collect here what was my experience.
I will try to both describe my experiences and give some general advice to wannabe problemsetters.
I hope that this will be useful to future problemsetters who are "out of the loop". Moreover, participants might be curious to know what happens behind the scenes (and maybe the platforms may consider this as a form of constructive feedback).
*Acronyms*:
- AGC = Atcoder Grand Contest
- GR = Codeforces Global Round
### Why I know something about problemsetting?
I am in the competitive programming world since ~8 years: I have participated in IOI/ICPC/GCJ and a number of contests on AtCoder/Codeforces (and lately Codechef).
I am not a top participant but, being in this world for so long, I know, more or less, all the standard tricks.
Recently, I was the author of the *flagship conte...
spending the vast majority of that time discarding bad ideas, thinking about
the cosmicvoid, feeling
15.
Editorial for Hello 2024 ### [problem:1919a]
Author: [user:maomao90,2024-01-02]
<spoiler summary="Hint 1">
When does the game end?
</spoiler>
<spoiler summary="Solution">
Depending on whether the player chooses to exchange wallets with their opponent on step $1$, $1$ coins will be removed from either the opponent's wallet or the player's wallet. This means that if either of the players still has remaining coins, the game will not end as at least one of the choices will still be valid.
The only way that the game ends is when both players have $0$ coins. Since each operation decreases the total amount of coins by exactly $1$, the only way for Alice to win the game is if $a + b$ is odd.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int a, b; cin >> a >> b;
if ((a + b) % 2 == 0) {
cout << "Bob\n";
} else {
cout << "Alice\n";
}
}
...
int mn[MAXN * 4], lz[MAXN * 4]; void init(int u = 1, int lo = 1, int hi = n) {
mn[u] = lz[u, ll mx[MAXN * 4], lz[MAXN * 4]; void init(int u = 1, int lo = 1, int hi = n) {
lz[u] = 0, ll st[MAXN * 4][2][2]; void merge(int u, int lo, int hi) { int mid = lo + hi >>
1, lc = u
Tutorial of Hello 2024
16.
Codeforces Round #745 Editorial I'm very sorry about all the inconvenience, and I would like to bear the blame. Much thanks to those who help me prepare this round. It's not their fault. And much thanks to your participation.
[problem:1581A]
------------------
idea: [user:interlude,2021-09-30]
preparation: [user:CQXYM,2021-09-30]
tutorial: [user:CQXYM,2021-09-30]
Assume a permutation $p$, and $\sum_{i=2}^{2n}[p_{i-1}<p_i]=k$. Assume a permutaion $q$, satisfying $\forall 1 \leqslant i \leqslant 2n, q_i=2n-p_i$. We can know that $\forall 2 \leqslant i \leqslant 2n,[p_{i-1}<p_i]+[q_{i-1}<q_i]=1$. Thus,$\sum_{i=2}^{2n}[q_{i-1}<q_i]=2n-1-k$, and either $p$ should be counted or $q$ should be counted. All in all, the half of all the permutaions would be counted in the answer. Thus, the answer is $\frac{1}{2}(2n)!$.
The time complexity is $O(\sum n)$. If you precalulate the factors, then the complexity will be $O(t+n)$.
-----
<spoiler summary="solution">
~~~~~
#include<stdio.h>
int f[100001];
int m...
~~~~~ #include inline void Solve(){ int n,m,k; scanf, ;return ans;} void init(int n){ for(int i=1;i>1:a_[i>>1]>>1; for(int, inline void swap() { int t = f; f = s; s = t; } }minv, val[MAX_N, inline void umax(ll &a, ll b) { a = a < b ? b : a; }, template inline void RI(T &t) { char c = GC; for (t = 0; c < 48 || c > 57; c =
GC, template inline void RI(Ty &t) { char c = GC; for (t = 0; c < 48 || c > 57, void Build(int x, int y, int z) { ecnt ++; e[ecnt].y = y; e[ecnt].len = z; e, void block_modify(int Tm, int k, int v) { int bl = x[k] + y[k], *c = cnt[bl];
int l = (Tm, void dfs(int u) { sz[u] = 1; if (ls[u]) { dfs(ls[u]); for (int i = std, void dp(int sz, int cnt, int dep) { if (f[dep][sz][cnt] != -1) return ;
register int &F, void segment_modify(int &i, int l, int r, int x) { i = i ? i : ++ tot; node[i
Tutorial of Codeforces Round 745 (Div. 1)
Tutorial of Codeforces Round 745 (Div. 2)
17.
Hello 2018 -- Tutorial Here is the tutorial of Hello 2018. Enjoy!
<spoiler summary="Modular Exponentiation">
Problem writer: [user:tourist,2018-01-08]
[tutorial:913A]
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
scanf("%d %d", &n, &m);
printf("%d\n", n >= 31 ? m : m % (1 << n));
return 0;
}
~~~~~
</spoiler>
</spoiler>
<spoiler summary="Christmas Spruce">
Problem writer: [user:BudAlNik,2018-01-08]
[tutorial:913B]
<spoiler summary="C++ solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> p(n), deg(n);
for (int i = 1; i < n; i++) {
cin >> p[i];
p[i]--;
deg[p[i]]++;
}
vector<int> sons_leaves(n);
for (int i = 0; i < n; i++) {
if (deg[i] == 0) {
sons_leaves[p[i]]++;
}
}
for (int i = 0; i < n; i++) {
if (deg[i] > 0 && sons_leaves[i] < 3) {
puts("No");
return 0;
}
}
puts...
inline void add(int &a, int b) { a += b; if (a >= md) a -= md; }, inline void sub(int &a, int b) { a -= b; if (a < 0) a += md; }, void add(int pr, const string& s, int mask) { if (dp[mask][pr].empty() || ls(s,
dp[mask][pr, void sub(poly &a, poly b) { while (a.size() < b.size()) { a.push_back(0); } for
(int, void update(string &a, string &b) { if (a == "" || (b.length() < a.length() ||
(b.length
Tutorial of Hello 2018
18.
[Tutorial] Li Chao Tree Extended Hello everyone! I discovered a new (?) trick on how to apply lazy propagation on the Li Chao Tree and decided to write a blog about it. I've personally never seen it before (outside of myself), nor have I seen a problem that needs the Extended Li Chao Tree specifically, but it *can* overkill some problems. Of course, I might not be looking hard enough...
You can learn about the basics of Li Chao Tree from [cp-algorithms](https://cp-algorithms.com/geometry/convex_hull_trick.html) or [this simple blog](https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html).
The Extended Li Chao Tree can do the following problems (and other variations):
## Problem 1
There is an array $A$ of size $N$. There are $Q$ online operations:
- Range Line Insertion. Given $l$, $r$, $a$, $b$, do $A_i = \max(A_i, a \cdot i + b)$, $\forall i \in [l, r]$ in $O(\log^2 N)$
- Range Line Addition. Given $l$, $r$, $a$, $b$, do $A_i += a \cdot i + b$, $\forall i \in [l, r]$ in $O(\log^2 N)$.
- Po...
void AddLine(Node* &n, data_t tl, data_t tr, data_t l, data_t r, Line x) { if
(tr < l, void AddLine(data_t l, data_t r, Line x) { return AddLine(root, 0, sz - 1, l,
r, x); }, void InsertLine(Node* &n, data_t tl, data_t tr, data_t l, data_t r, Line x) {
if (tr < l, void InsertLine(data_t l, data_t r, Line x) { return InsertLine(root, 0, sz -
1, l, r, x); }, void InsertLineKnowingly(Node* &n, data_t tl, data_t tr, Line x) { if (n ==
nullptr) n, void PushLazy(Node* &n, data_t tl, data_t tr) { if (n == nullptr) return; if
(n->lc, void PushLine(Node* &n, data_t tl, data_t tr) { if (n == nullptr) return;
data_t mid = (tl, void add(Line x) { a += x.a; b += x.b; } };, void apply(data_t l, data_t r, Line v) { line.add(v); lazy.add(v); } };
19.
A simple introduction to "Segment tree beats" Hi, I’d like to introduce a simple trick about segment tree in this blog as I promised in [this comment](http://codeforces.me/blog/entry/54750?#comment-387957). Sorry for the long delay, as a sophomore in Peking University, I've just finished a tired semester and a painful final exam. And now I finally have enough time to do a simple introduction to this interesting algorithm.
It may be a huge project for me since my English is not good. I think I will finish this blog in several steps and I will try to finish it as soon as possible :)
In China, all of the 15 candidates for the Chinese National Team are asked to write a simple research report about algorithms in informatics Olympiad, and the score will be counted in the final selection. There are many interesting ideas and algorithms in these reports. And I find that some of them are quite new for competitors in CF although they are well known in China from the final standings of some recent contests. For example, In the last co...
```c++ void modify(int node, int l, int r, int ll, int rr) { if
(break_condition()) return, ```c++ void modify(int node, int l, int r, int ll, int rr) { if (l > rr || r <
ll) return
20.
Tutorial on Permutation Tree (析合树） So my O level Chinese exam is in 2 days so I decided to learn a data structure that I can only find [resources](https://oi-wiki.org/ds/divide-combine/) for in Chinese. I thought I might as well write a tutorial in English.
This data structure is called 析合树, directly translated is cut join tree, but I think permutation tree is a better name. Honestly, after learning about it, it seems like a very niche data structure with very limited uses, but anyways here is the tutorial on it.
Thanks to [user:dantoh,2020-06-16] and [user:oolimry,2020-06-16] for helping me proofread.
### Motivation
Consider this [problem](https://codeforces.me/contest/526/problem/F). We are given a permutation,$P$ of length $n$. A good range is a contiguous subsequence such that $\max\limits_{l \leq i \leq r} P_i - \min\limits_{l \leq i \leq r} P_i = r-l$. This can be thought of the number of contiguous subsequence such that when we sort the numbers in this subsequence, we get contiguous values. Count the...
void add_edge(int u,int v){ //u is parent of v parent[v]=u;
children[u].push_back(v); }, void build(){ idx=n; memset(parent,-1,sizeof(parent));, void dfs(int i){ for (auto &it:children[i]){ int curr=tkd[it][0]=i; for (int
x=0;curr!=-1;x, void propo(){ if (lazy){ val+=lazy; if (s!=e){ l->lazy+=lazy; r->lazy+=lazy, void update(int i,int j,ll k){ if (s==i && e==j) lazy+=k; else{ if (j<=m)
l->update(i,j,k
21.
Editorial — Codeforces Round #651 [problem:1370A]
<spoiler summary = "Tutorial">
[tutorial : 1370A]
</spoiler>
<spoiler summary="Code">
<pre><code>
#include < bits/stdc++.h >
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 1e5 + 5;
int32_t main()
{
IOS;
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
cout << n / 2 << endl;
}
return 0;
}
</code></pre>
</spoiler>
This problem was prepared by [user:the_hyp0cr1t3,2020-06-20]
[problem:1370B]
<spoiler summary = "Tutorial">
[tutorial : 1370B]
</spoiler>
<spoiler summary="Code">
<pre><code>
#include < bits/stdc++.h >
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N = 2e5 + 5;
int n;
int a[N];
int32_t main()
{
IOS;
int t;
cin >> t;
while(t--)
{
cin >> n;
vector< int > even, odd;
for(int i = 1; i ...
void dfs(int i, int par){ max_depth[i] = depth[i]; for(int j : adj[i]){ if(j ==
par, void find_nodes(int i, int par, int req_depth, vector< int > &nodes){
if(depth[i] == req_depth, void player_1(){ cout << "Ashishgup" << endl; }, void player_2(){ cout << "FastestFinger" << endl; }
Tutorial of Codeforces Round 651 (Div. 2)
22.
Codeforces Round #638 (Div. 2) Editorial [problem:1348A]
<spoiler summary="Tutorial">
[tutorial:1348A]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void solve(){
int N;
cin>>N;
//note: 1<<X means 2^X
//we put largest coin in first pile
int sum1=(1<<N), sum2=0;
//we put n/2-1 smallest coins in first pile
for (int i=1;i<N/2;i++)
sum1+=(1<<i);
//we put remaining n/2 coins in second pile
for (int i=N/2;i<N;i++)
sum2+=(1<<i);
cout<<sum1-sum2<<endl;
}
int main(){
int t; cin>>t;
while (t--)
solve();
}
~~~~~
</spoiler>
[problem:1348B]
<spoiler summary="Tutorial">
[tutorial:1348B]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void solve(){
int N,K;
cin>>N>>K;
set<int>s;
for (int i=0;i<N;i++){
int a;
cin>>a;
s.insert(a);
}
//if more than K distinct numbers, print -1
if (s.size()>K){
cout<<-1<<endl;
return;
...
void dfs(int node){ //activates node vis[node]=1; queuetoRemove; for, void foundAnother(int node, int nextNode){ vectorv; int cur=node; //backtracks
on, void perfectMatch(){ //finds a perfect matching deque,int>>v; for (int i=1, void show(){ for(int i=1;i<=N;i++) cout<<<' '; cout<, void solve(){ int N,K; cin>>N>>K; sets; for (int i=0;i, void solve(){ int N; cin>>N; //note: 1<, void solve(){ int n,k; cin>>n>>k; string s; cin>>s; sort(s.begin(),s.end());
//if, void solve(){ vectorinc; int N; cin>>N; //construct sequence 1, 2, 4, ... while
Tutorial of Codeforces Round 638 (Div. 2)
23.
Algorithm Gym :: Data structures Today I want to introduce you some very very useful data structures.
In this lecture, we are trying to improve your data structures skills, stay with us and click on **read more**.
[cut]
Important data structures :
Trees
-----
Trees are one of the most useful data structures.A tree is a connected-acyclic graph.There are too many types of trees, like : rooted trees, weighted trees, directed trees, tries, etc.
Partial sum
-----------
There are two types of problems solvable by partial sum.
1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries).
Solution of all of this problems are the same. You just need to know how to solve one of them.
Example : You are asked some queries on an array $a_1,a_2,...a,_n$. Each query give you numbers $l$ and $r$ and you should print $a_l + a_{l+1} + ... + a_r$ .
Solution : You need to build another array $s_1, s_2, ..., s_n$ which $s_i = a_1 + a_2 + ... + a_i$ ...
void build(string s){ int i = 0, v = 0; while(i < s.size()){ if(x[v][s[i]] ==
-1) v = x[v, void buildLCP() { for (int i = 0, k = 0; i < N; ++i) if (pos[i] != N - 1) { for
(int j, void buildSA() { N = strlen(S); REP(i, N) sa[i] = i, pos[i] = S[i]; for (gap =
1;; gap, void buildSA() { N = strlen(S); hPow[0] = 1; for (int i = 1; i <= N; ++i) hPow[i, ~~~~~ int fen[MAX_N]; void update(int p,int val){ for(int i = p;i <= n;i += i &
-i) fen[i, ~~~~~ int root(int v){return par[v] < 0 ? v : (par[v] = root(par[v]));} void
merge(int x,int y, ~~~~~ vector s; void split(int x,int y, int id = 1,int l = 0, int r = n){// id
is the index, ~~~~~ void build(int id = 1,int l = 0,int r = n){ if(r - l < 2){ // l + 1 == r
s[id] = a[l, ~~~~~ void build(int id = ir,int l = 0,int r = n){ if(r - l < 2){ s[id] = a[l];
return, ~~~~~ void increase(int x,int y,int v,int id = 1,int l = 0,int r = n){ if(x >=
r or l >= y, ~~~~~ void modify(int p,int x,int id = 1,int l = 0,int r = n){ s[id] += x -
a[p]; if(r - l < 2, ~~~~~ void shift(int id,int l,int r){//pass update information to the children
int mid = (l+r)/2, ~~~~~ void upd(int id,int l,int r,int x){// increase all members in this
interval by x lazy[id
24.
Finding all primes up to half a billion in 83 ms Hi everyone!
I was itching to apply SIMD in another problem, and this time my attention picked the following problem:
---
**[Library Checker — Enumerate Primes](https://judge.yosupo.jp/problem/enumerate_primes)**. You are given $N$, $A$ and $B$. Find $\pi(N)$, and print all $p_{kA + B} \leq N$.
It is guaranteed that $N \leq 5 \cdot 10^8$ and that the total number of primes to print is at most $10^6$.
---
After some tweaking, I managed ([#336744](https://judge.yosupo.jp/submission/336744)) to reduce my time consumption in this problem to **83 ms** and memory consumption to **25 MiB**, which makes it a top-1 submission on the Library Checker. For comparison, the top-2 solution ([#148169](https://judge.yosupo.jp/submission/148169)) takes 172 ms and 15 MiB, meaning that what I describe here is a 2x improvement in terms of the running time.
We can also compare it to what appears to be the state of the art of sieving, the [primesieve](https://github.com/kimwalisch/...
// or via function attributes [[gnu::optimize("O3"), gnu::target("avx2")]] void
func1, ```cpp void apply(vector &sieve, vector &pattern) { size_t N, void deallocate(T* p, std::size_t n) noexcept { if (!p) return; std
25.
CodeTON Round 5 Editorial ### [problem:1842A]
<spoiler summary="Tutorial">
Let's view it as when monsters $x$ and $y$ fight, their health changes into $\max(x-y,0)$ and $\max(y-x,0)$ respectively. So any monster with $0$ health is considered dead. Therefore, a player loses when the health of his monsters are all $0$.
Notice that $\max(x-y,0)=x-\min(x,y)$ and $\max(y-x,0)=y-\min(x,y)$. Therefore, after each step, the sum of the health of monsters decrease by the same amount for both players.
Therefore, we only need to know $\sum a_i$ and $\sum b_i$ to determine who wins. If $\sum a_i > \sum b_i$, Tsondu wins. Else if $\sum a_i < \sum b_i$, Tenzing wins. Else, it is a draw.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m, a[50], b[50];
long long sumA = 0, sumB = 0;
cin >> n >> m;
for (int i = 0; i < n;...
= r * a % P; a = a * a % P, n >>= 1; } return r; } inline void inc(int& a, int
b, ), p = pre[p]; reverse(res.begin(), res.end()); return res; } void divide(int
l, int r, void bfs(int u) { static int q[N], dis[N]; memset(dis, -1, sizeof dis); q[1] = u, void insert(int i, int v) { for (i += M; i; i >>= 1) c[i][0] = v, v = max(v,
c[i ^ 1][0
26.
[Tutorial] Proving the inverse Ackermann complexity of Union-Find #### Introduction
Most of us are familiar with the union-find data structure and the two optimizations one can do on it: _union by rank_ and _path compression_. Most tutorials will introduce these methods and state that if both optimizations are used, the complexity will be $\mathcal{O}((n + m) \alpha(n))$. Here, $n$ and $m$ are the number of vertices and queries respectively. What is $\alpha$? Generally, we are told that $\alpha$ is some mysterious function that grows very slowly: $\alpha(N) < 5$ where $N$ is the number of subsets of particles in the observable universe and whatnot. What it is is usually not clarified very much. And there is typically no proof (or intuition and other such justifications) as to why the complexity is like that: usually we're told that the complexity analysis is quite long and complicated. At the time of writing, both [cp-algorithms](https://cp-algorithms.com/data_structures/disjoint_set_union.html) and [Wikipedia](https://bit.ly/3EvnzrI) are like th...
void merge (int u, int v) { u = find(u); v = find(v); parent[u] = v; } ~~~~~, ~~~~~ // in initialization, rank[w] is set to 0 for every w void merge (int u,
int v) { u
27.
Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2) Editorial Thank you for your participation!
Problem A, B were authored by [user:djm03178,2025-10-03].
Problem C was authored by [user:As_dfsdf,2025-10-03].
Problem D was authored by [user:qwerasdfzxcl,2025-10-03].
Problem E, F, G, H1, H2 were authored by [user:ko_osaga,2025-10-03].
[problem:2152A]
<spoiler summary="Spoiler">
[tutorial:2152A]
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
set<int> s;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
s.insert(x);
}
cout << s.size() * 2 - 1 << '\n';
}
}
~~~~~
</spoiler>
[problem:2152B]
<spoiler summary="Spoiler">
[tutorial:2152B]
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
wh...
void dfs(int x, int p = -1) { din[x] = sz(seq); seq.push_back({a[x], 0}); for
(auto &y : gph, void init(int s, int e, int p, vector &seq) { if (s == e) {
tree[p].M[seq[s][0]] = mtrx, void lazydown(int p) { if (tree[p].lazy) { for (int i = 2 * p; i < 2 * p + 2;
i++) { tree, void solve() { int N, Q; cin >> N >> Q; int i; for (i = 1; i <= N; i++) cin >>
A[i]; for, void solve(){ int n, q; scanf("%d %d", &n, &q);, void update(int s, int e, int ps, int pe, int p) { if (e < ps || pe < s)
return; if (s <= ps
28.
Hybrid Tutorial #-1: Heavy-Light Decomposition **[Here](https://www.youtube.com/watch?v=_G_LMuLWMaI&list=PLDjGkpToBsYDx4GWu2u87sTqt6ICELz-T) is a playlist of all hybrid tutorials I've done.**
# "Intro"
_Timestamp: [00:00](https://youtu.be/_G_LMuLWMaI)_
Hi! Definitely not inspired by [this comment](https://codeforces.me/blog/entry/81086?#comment-675431), I've decided to try something that seems relatively novel — combining a blog and video tutorial into one, in a "hybrid" fashion. Both should be usable independently, but they will have the same "flow" and structure so you can reference both for concepts that are harder to grasp, and the two will supplement each other. The goal of these is to be **complete** — beneficial for both video and blog lovers, as well as full of enough information that anyone without much of an idea of what the concept is should be able to fully understand. There will be code as well, however, I very highly recommend not looking at it, but rather working out the implementation for yours...
~~~~~ void dfs_chains(int v, int p) { if (bigchild[v] != -1) {
chain[bigchild[v]] = chain, ~~~~~ void dfs_labels(long long* arr, int v, int p) { label[v] = label_time, ~~~~~ void dfs_size(int v, int p, int d) { sz[v] = 1; depth[v] = d; par[v] = p;
int
29.
Educational Codeforces Round 87 Editorial [problem:1354A]
Idea: [user:BledDest,2020-05-18]
<spoiler summary="Tutorial">
[tutorial:1354A]
</spoiler>
<spoiler summary="Solution (pikmike)">
~~~~~
t = int(input())
for _ in range(t):
a, b, c, d = map(int, input().split())
if b >= a:
print(b)
continue
if c <= d:
print(-1)
continue
a -= b
dif = c - d
print(b + (a + dif - 1) // dif * c)
~~~~~
</spoiler>
[problem:1354B]
Idea: [user:BledDest,2020-05-18]
<spoiler summary="Tutorial">
[tutorial:1354B]
</spoiler>
<spoiler summary="Solution (BledDest)">
~~~~~
#include<bits/stdc++.h>
using namespace std;
char buf[200043];
int main()
{
int t;
scanf("%d", &t);
for(int i = 0; i < t; i++)
{
scanf("%s", buf);
string s = buf;
int ans = int(1e9);
int n = s.size();
vector<pair<char, int> > c;
for(auto x : s)
{
if(c.empty() || c.back().first != x)
c.push_back(make_pair(x, 1));
else
c.back().second++;
}
int m = c.size();
for...
inline void solve() { //check first position mt19937 rnd(lst ^ (n * 1024 + k));
for(int q = 0, template void output_vector(const vector &v, bool add_one = false, int start =
-1, void add(int x, int y, int c, int cost) { g[x].push_back(e.size());
e.push_back(edge(y, void dbg_out() { cerr << endl; } template void dbg_out(Head H, void dfs(int v){ tot0 += clr[v] == 0; tot1 += clr[v] == 1;
vts[clr[v]].back().pb(v); for, void run_case() { int N, K; cin >> N >> K; vector A(N), B(N);, void solve() { sort(a, a + n, [](const pair &a, const pair &b){ if (a.x.y
30.
[Tutorial] Blossom Algorithm for General Matching in O(n^3) I have decided to write a tutorial on a topic not even [user:Um_nik,2021-06-29] knows! ([source](https://codeforces.me/blog/entry/92248))
In this tutorial, I will talk about the blossom algorithm, which solves the problem of **general matching**. In this problem, you are given an undirected graph and you need to select a subset of edges (called matched edges) so that no two edges share a vertex, and the number of matched edges is maximized. More common in competitive programming is bipartite matching, which is the same problem but when the graph is guaranteed to be bipartite. In competitive programming, general matching seems to get a lot of hate for being very challenging to implement. However, the blossom algorithm is quite beautiful, and important in the history of algorithm research.
It will help if you are already familiar with bipartite matching. I will discuss the high level ideas of the algorithm, but my main focus will be on the tricky implementation details. So you may...
)); } void add_edge(int u, int v) { g[u][v] = u; g[v][u] = v; } void match
31.
PSA on Meta Hacker Cup (must read if its your first time!) Meta Hacker Cup is upon us again. Along with it comes the unique format where we have to run our code on large test cases ourselves. Unfortunately, past experience shows that not everyone knows how to do this reliably. Usually, after the first round, many people lose points as a result of an unreliable workflow. This time, let's try to prevent that from happening. Sorry for the somewhat self-important title, but I really do wish that everyone understood this and that no one will fail the contest because of this.
### Don't EVER copy-paste huge files
A lot of people's workflow to run a solution is the following:
- Click some green button in the IDE
- A box comes up, copy-paste the input into that box
- The output shows up somewhere
This may work well for running your solution on small sample test cases. It is **terrible** for running your solution on the huge test cases in Meta Hacker Cup. In last year's Round 1, the full test case for [problem C](https://www.facebook.com...
void dfs (int u, int d) { depth[u] = d; for (int nxt : ch[u]) dfs(nxt, 1 + d); }
32.
Codeforces Round #723 (Div. 2) Editorial [problem:1526A]
------------------
Setter: [user:antontrygubO_o,2021-05-28]
Preparer: [user:errorgorn,2021-05-28]
<spoiler summary="Hint 1">
Notice that the array size is even length. Usually in such problems, we would split the array into $2$ equal parts. Can you figure out what those $2$ parts are?
</spoiler>
<spoiler summary="Hint 2">
We sort the array and split it into the big half and the small half.
</spoiler>
<spoiler summary="Solution">
The main idea is that we can split the numbers into the two halves, the big half and small half, we can place the bigger half at the odd positions and the smaller half at the even positions.
This works because the smallest big number is larger than the biggest small number. Hence, the mean of any two small numbers is smaller than any big number, and the mean of any two big numbers is bigger than any small number.
</spoiler>
<spoiler summary="Code (C++)">
```c++
//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include <bits/stdc++.h>
#inc...
void apply(long long L){ val += L; lazy += L; } void push(){ if(s == e) return;
l, void solve(){ int n; cin>>n;, void sort(int &a,int &b,int &c){ if (a>b) swap(a,b); if (b>c) swap(b,c); if
(a>b) swap(a,b); }
Tutorial of Codeforces Round 723 (Div. 2)
33.
Caveats of using optimize("Ofast") with target("avx2") Hi everyone!
As you may know, it is often recommended to put these lines in your header:
```cpp
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
```
And they're usually great!<sup>[1]</sup> Well, until they aren't. For last 2-3 days I was riddled with the issue that [CP-Algorithms Library](https://lib.cp-algorithms.com) would perform very well on Library Checker, but whenever I tried to also apply it on Codeforces, it will fail to speed up the code, and sometimes would even make it much slower. As I finally figured out the cause, I'd like to write a blog about it, so that other people don't waste as much time.
Mitigating these issues improved my running time on [problem:1975G] from **1530 ms** in [submission:316602668] to **203 ms** in [submission:352602775].
##### Tl'dr
See the "Takeaway" section at the bottom.
[cut]<br>
##### Example problem
I will reproduce the issue on a simple example:
<hr>
**[problem:911G]**: You are given an...
```cpp #pragma GCC optimize("O3") ... [[gnu::target("avx2")]] void solve() {
.... } ```, ```cpp #pragma GCC optimize("Ofast") ... [[gnu::target("avx2")]] void solve() {
... } ... ```
34.
Codeforces Round #770 (Div. 2) editorial Thank you for participating, we hope you enjoyed the problems! We kindly ask you to rate each of the round's problems in the corresponding spoiler in order to improve the quality of future contests.
You can also check video editorials of problems B and C on [user:ak2006,2022-02-06] [Youtube channel](https://www.youtube.com/channel/UCnZ5rC2_JY0EuYMGMiAbISg).
All problems were prepared by [user:Alexdat2000,2022-02-02] with the help of coauthors.
[Why didn't AI participate](https://codeforces.me/blog/entry/99579?#comment-884764)
[problem:1634A]<br>
Idea: [user:sevlll777,2022-02-02]
<div class="spoiler"> <b class="spoiler-title">Hint 1</b> <div class="spoiler-content" style="display: none;">
What property will the string have after the first operation (regardless of the type of operation)?
</div></div>
<div class="spoiler"> <b class="spoiler-title">Hint 2</b> <div class="spoiler-content" style="display: none;">
What happens if you apply an operation to a palindrome?
...
void dfs(int v) { if (pos[v] == 0) { ans[v] = string(len(g[v]), 'L'); }, void upd(int ind, int delta) { notzero -= (unfib[ind] != 0); unfib[ind] +=
delta; if
Tutorial of Codeforces Round 770 (Div. 2)
35.
A Beautiful Technique for Some XOR Related Problems ## Inspiration
I'm very excited about this blog, as it took me quite a lot of effort and scavenging through the internet to completely grasp the concept of this technique(That's probably because I have almost zero knowledge in Linear Algebra or I'm just plain dumb). So I feel like I genuinely conquered a challenge, and I really want to share it with someone. But there's no way my CP friends circle will believe it, they'll think I'm just trying to show off :P
So here I am, sharing it on CF. I also created a [personal blog](https://drschwad.github.io/), so that if I ever feel like sharing something again(not only about CP), I can write a blog there. I also added this same post [there](https://drschwad.github.io/2019-08-06-z2-space-xor-trick/), you can read it there if you prefer dark theme. I'll be pleased to hear any thoughts on the blog or if I can improve it in some way ^\_^
## Introduction
Since it concerns Linear Algebra, there needs to be a lot of formal stuff going on ...
void insertVector(int mask) { for (int i = 0; i < LOG_A; i++) { if ((mask & 1
<< i) == 0, void insertVector(int mask) { for (int i = 0; i < LOG_PREF; i++) { if ((mask &
1 << i) == 0, void insertVector(int mask) { for (int i = 0; i < d; i++) { if ((mask & 1 << i)
== 0) continue, void insertVector(int mask) { for (int i = LOG_A - 1; i >= 0; i--) { if ((mask
& 1 << i) == 0, void insertVector(int mask) { for (int i = LOG_K - 1; i >= 0; i--) { if ((mask
& 1 << i) == 0
36.
Good Bye 2020 Editorial [problem:1466A]
- Author: [user:Okrut,2020-12-30]
- Developer: [user:Anadi,2020-12-30]
- First solve: [user:Mip182,2020-12-30]
<spoiler summary="Tutorial">
[tutorial:1466A]
</spoiler>
<spoiler summary="Solution 1">
```
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
scanf("%d", &n);
vector <int> in(n);
vector <int> is(N);
for(auto &p: in)
scanf("%d", &p);
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n; ++j)
is[in[j] - in[i]] = true;
int ans = 0;
for(auto &v: is)
ans += v;
printf("%d\n", ans);
}
int main() {
int cases;
scanf("%d", &cases);
while(cases--)
solve();
return 0;
}
```
</spoiler>
<spoiler summary="Solution 2">
```
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
scanf("%d", &n);
vector <int> in(n);
for(auto &p: in)
scanf("%d", &p);
set <int> S;
for(int i = 0; i < n; ++i)
for(int j = i + 1; j < n; ++j)
S.insert(in[j...
void init() { scanf("%d %d", &n, &q); read(s), read(t);, void precalc() { sil[0] = 1; for(int i = 1; i <= n; ++i) sil[i] = 1LL * sil[i -
1] * i % MX;, void prepare_songs() { songs = {s}; for(auto c: t) { if(songs.back().size() >=
MAXLEN, void prepare_sum() { for(int i = 0; i < 26; ++i) { char c = 'a' + i;
sum[i].resize(n + 1, 0);, void read() { scanf("%d", &n); precalc();, void read(string &p) { static char input[MAXLEN]; scanf("%s", input); p =
input; }, void solve() { int n; scanf("%d", &n);, void solve() { scanf("%d", &n); for(int i = 1; i <= n; ++i) { scanf("%d",
&w[i]); deg[i, void solve() { while(q--) { int k; string w;, void solve(){ scanf("%d", &n); for(int i = 0; i < P; ++i) cnt[i] = 0;, void solve(){ scanf("%s", in + 1); n = strlen(in + 1);, void solve(vector cur, string pref){ if(pref.size() == b){ write(0, pref);
return; }, void write(int i, string y){ printf("%d ", i); for(auto p: y) printf("%c", p);
puts
Tutorial of Good Bye 2020
37.
Heuristic algorithm for Hamiltonian path in directed graphs (It's a translated version of my blog at https://peehs-moorhsum.blog.uoj.ac/blog/6384. )
Finding a Hamiltonian path in a directed graph is a well-known NP problem.
However, about a year ago, I came up with the following heuristic algorithm which has GREAT performance on random graphs(by first generating a hamiltonian path, adding random edges, then randomly permuting indices) and many CP problems.
Here is the idea of the algorithm:
We maintain a subset $S$ of edges, ensuring there's no cycle and each vertex has in-degree and out-degree at most 1. Whenever $|S|$ reaches $n-1$, we find a hamiltonian path.
We start with $S$ empty. Each time we pick a random edge $e \notin S$. If we can add $e$ to $S$ without violating any rule, we simply add it to $S$. Otherwise, if $e$ won't create a cycle and violate with exactly one edge e', we replace e' with $e$ with 50% probability. Repeat until $|S|$ reaches $n-1$.
We can use LCT to check cycles. Here's my code, which takes le...
ch; vi fa, rev; void init(int n) { ch.resize(n + 1, ch[a][tp ^ 1] = f, fa[f] = a; } void splay(int a) { push(a
38.
Spectral::Cup 2026 Round 2 (Codeforces Round 1100, Div. 1 + Div. 2) Editorial Thank you for participating in our round! We hope you enjoyed the problems as much as we enjoyed preparing them.
<spoiler summary="Rate the contest!">
<spoiler summary="Quality">
-
Absolute Cinema contest
-
Excellent contest
-
Good contest
-
Average contest
-
Bad contest
-
Horrible contest
</spoiler>
<spoiler summary="Difficulty">
-
Trivial contest
-
Easy contest
-
Average contest
-
Hard contest
-
Impossible contest
</spoiler>
</spoiler>
[problem:2229A]
Idea by: [user:Intellegent,2026-05-23]
Prepared by: [user:Intellegent,2026-05-23]
Editorial by: [user:reirugan,2026-05-23]
<spoiler summary="Hint 1">
Let $y$ denote the final position of all of the slimes. Then it is optimal to choose $x = y$ for every operation.
</spoiler>
<spoiler summary="Hint 2">
Let $\mathrm{mn}$ denote the minimum value in $a$, a...
template void rd(T &x) { cin >> x; }, template void rd(vc &x) { for (auto &d : x) rd(d); }, vector cur; auto dfs2 = [&](auto self, int c, int p) -> void{ s.erase(c, vector mx(n); auto dfs = [&](auto self, int c, int p) -> void{ for (int x : g[c, void print() { cout << '\n'; } template void print(Head &&head, Tail, void read() {} template void read(H &h, T &...t) { rd(h), read(t...); }, void solve() { int n, k; cin >> n >> k; vecin(aa, n); sort(all(aa)); n --; ll, void solve(){ int n; cin >> n;
39.
EPIC Institute of Technology Round Summer 2025 (Codeforces Round 1036, Div. 1 + Div. 2) Editorial Thanks for participation! We hope you loved the contest.
#### [problem:2124A]
Problem Credits: [user:Lilypad,2025-07-01] <br>
<spoiler summary="Hint">
When is there definitely *not* a solution?
</spoiler>
<spoiler summary="Solution">
First, note that since relative order is preserved no matter which elements are deleted, if $a$ is originally sorted in nondecreasing order, the array cannot be a derangement no matter which elements are deleted.
If $a$ is not sorted, we can note that any two elements that form an inversion pair satisfies the requirements. The total runtime is $O(n)$.
</spoiler>
<spoiler summary="Code">
```
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin >> n;
vector<int> arr(n);
for(auto &x : arr) cin >> x;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(arr[i] > arr[j]){
cout << "YES\n2\n";
cout << arr[i] << " " << a...
void Solve() { int n; cin >> n;, void solve() { int n; cin >> n; int k; cin >> k; vecin(aa, n); if (k == 1, void solve(){ int n;
40.
[Tutorial] Theoretically Faster HLD and Centroid Decomposition This blog was going to be translation of $[1]$ (which is in Chinese) but I think I ended up deviating too much from the source material that it would not be appropriate to call this a translation. Anyways, I am honestly amazed by how ahead of its time this paper is. In its abstract, it starts by saying that the state of art for tree path queries is $O(n \log n + q \sqrt n \log n)$, which I honestly can't fathom how one would arrive, then proceeds to claim that it has found an $O((n+q) \log n)$ algorithm. All the more, in 2007.
While I was in the process of writing this blog, [user:smax,2022-07-18] sniped me and posted $[9]$. However, we will focus on static trees **only**.
Thanks to [user:oolimry,2022-07-18], [user:everule,2022-07-18] and [user:timreizin,2022-07-18] for proofreading.
Note to reader: I am expecting the reader to be familiar with what a splay tree and HLD is. You do not really need to know why splay trees are $O(\log n)$ amortised but you should know what the z...
void dfs(int i,int p){ root[i]=new node(p==-1?nullptr:root[p]); for (auto
it:al[i]){ if (it, void dfs_hld(int i,int p){ in[i]=++_TIME;, void dfs_hld(int i,int p){ in[i]=TIME++;, void dfs_hld(int i,int p){ num[hp[i]]++;, void dfs_ss(int i,int p){ if (p!=-1 && i<=n){ for (auto &it:al[i]) if (it==p ||
it==rp[p, void get(int i){ val[i]=max(val[i<<1],val[i<<1|1])+lazy[i]; }, void propo(){ if (lazy==0) return;, void rotate(node *u){ node *par=u->p; bool dir=u->dir();, void splay(node *u){ while (!u->head){ if (u->p->head){ //almost root rotate(u, void splay(node *u){ while (u->p){ if (u->p->p==nullptr){ //almost root rotate(u, void upd(){ mx=max({ val, l==nullptr?0:l->mx+l->lazy,
r==nullptr?0:r->mx+r->lazy }); } };, void upd(int i){ mx[i]=val[i]; rep(z,0,2) if (childs[i][z]!=-1)
mx[i]=max(mx[i],mx[childs[i][z
41.
Codeforces Round #813 (Div. 2) Editorial Thanks for participating in the round, we hope you liked the problems!
<spoiler summary="Solve count predictions (official div. 2)">
Handle | A | B | C | D | E1 | E2 | F
--- | --- | --- | --- | --- | --- | --- | ---
[user:Vladithur,2022-08-13] | 16K | 8K | 3K | 900 | 500 | 50 | 4
[user:_dlbm17,2022-08-13] | 14K | 9K | 5K | 500 | ? | ? | ?
[user:thanhchauns2,2022-08-13] | 14K | 8K | 2K | 1K | 500 | ? | ?
[user:QuangBuiCP,2022-08-13] | 14K | 7K | 2K | 1K | 500 | 24 | 5
[user:welleyth,2022-08-13] | 16K | 10K | 4K | 1.5K | 600 | 130 | 2
[user:Kon567889,2022-08-13] | 14K | 10K | 5K | 2K | ? | ? | 5
</spoiler>
[problem:1712A]
<spoiler summary="Hint">
The smallest possible sum is $1 + 2 + \ldots + k$.
</spoiler>
<spoiler summary="Tutorial">
[tutorial:1712A]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const ch...
void solve() {
Tutorial of Codeforces Round 813 (Div. 2)
42.
Codeforces Global Round 14 Editorial [problem:1515A]
Idea: [user:FieryPhoenix,2021-05-02]
<spoiler summary="Tutorial">
[tutorial:1515A]
</spoiler>
<spoiler summary="Solution">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n,x;
int w[101];
cin>>n>>x;
int sum=0;
for (int i=0;i<n;i++){
cin>>w[i];
sum+=w[i];
}
//if the sum is x, we cannot avoid the explosion
if (sum==x){
cout<<"NO"<<endl;
return;
}
cout<<"YES"<<endl;
//otherwise, the answer always exists
//we will keep adding elements from left to right
//if we can't add element i, we add element i+1 first by swapping the two
for (int i=0;i<n;i++){
if (x==w[i]){
//i+1 will always be less than n because otherwise, the total sum would be x
swap(w[i],w[i+1]);
}
cout<<w[i]<<' ';
x-=w[i];
}
cout<<endl;
return;
}
int main(){
int T; cin>>T;
while (T--)
solve();
return 0;
}
~~~~~
</spoiler>
[problem:1515B]
Ide...
void dfs(int u){ vis[u]=true; for(int e=head[u];e!=-1;e=prev[e]){ int
v=elist[e^1, void dfs_fwd(int x){ vis[x]=1; for(auto e:fwd[x]){ int y=e.first; if(vis[y]!=1, void dfs_rev(int x){ vis[x]=2; for(auto e:rev[x]){ int y=e.first,l=e.second;
if(vis, void query_one(int& L,int k,ll& cap,ll& value){ int
high=query_one_range_search(L,k,cap); //v, void solve(){ cin>>N>>M>>X; cout<<"YES"<>s; //stores pairs of, void solve(){ int n; cin>>n; if (n%2==0 && isSquare(n/2)) cout<<"YES"<
Tutorial of Codeforces Global Round 14
43.
Codeforces Global Round 13 Editorial [problem:1491A]
------------------
Setter: [user:syksykCCC,2021-02-28]
Prepared by: [user:syksykCCC,2021-02-28]
<spoiler summary="Hint 1">
How can we find the largest $k$ such that the $k$-th smallest element of the array is $0$?
</spoiler>
<spoiler summary="Hint 2">
How can we maintain $k$?
</spoiler>
<spoiler summary="Solution">
Let's define $cnt$ to represent the number of 1s in the array.
For the modifications, if $a_i$ is already $1$ now, then we let $cnt \gets cnt - 1$. Otherwise, let $cnt \gets cnt + 1$.
For the querys, just compare $cnt$ with $k$. If $cnt \ge k$, the answer will be $1$. Otherwise, the answer will be $0$.
The complexity : $O(n + q)$.
</spoiler>
<spoiler summary="Code (C++)">
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, q, a[N], cnt;
int main()
{
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; ++i)
{
scanf("%d",a+i);
cnt += a[i];
}
while(q--)
{
int opt, x;
...
struct Block { int f[B],lazy,flag,cnt,L,R; void update() { flag = 1; for (int i
= L; i, vector s; ///strictly increasing stack vector reds; void insert(long long b,
long long, void brute(){ deque q; animal w = arr[0];, void clear() { for (int i = 0; i < v.size(); i++) vis[v[i]] = 0; v.clear(); }, void cswap(int i,int j){ swap(arr[i],arr[j]); arr[i]=-arr[i],arr[j]=-arr[j];
ans.pub(ii(i,j)); }, void read(T &maxx,Args &... args) { read(maxx); read(args...); }, void swap_cyc(int i,int j){ cswap(i,j);, void write(T x) { if (x < 0) putchar('-'),x = -x; if (x < 10) return (void)
putchar(x + '0, void writeln(T maxx,Args ... args) { writes(maxx); writes(args...);
putchar('\n'); }, void writeln(T x) { write(x); putchar('\n'); }, void writes(T x) { write(x); putchar(' '); }
Tutorial of Codeforces Global Round 13
44.
Algorithm Gym :: Everything About Segment Trees In the last lecture of **Algorithm Gym** ([Data Structures](/blog/entry/15729)), I introduced you Segment trees.
In this lecture, I want to tell you more about its usages and we will solve some serious problems together.
[cut]
Segment tree types :
Classic Segment Tree
--------------------
Classic, is the way I call it. This type of segment tree, is the most simple and common type. In this kind of segment trees, for each node, we should keep some simple elements, like integers or boolians or etc.
This kind of problems don't have update queries on intervals.
Example 1 (Online):
Problem [problem:380C] :
For each node (for example $x$), we keep three integers :
1.`t[x]` = Answer for it's interval.
2. `o[x]` = The number of $($s after deleting the brackets who belong to the correct bracket sequence in this interval whit length `t[x]`.
3. `c[x]` = The number of $)$s after deleting the brackets who belong to the correct bracket sequence in this interval whi...
~~~~~ void build(int id = 1,int l = 0,int r = n){ if(r - l < 2){ s[id] = 1;
return, ~~~~~ void build(int id = ir,int l = 0,int r = n){ s[id] = 0; if(r - l < 2)
return ; int, ~~~~~ void shift(int id){ if(lazy[id]) lazy[2 * is] = lazy[2 * id + 1] =
lazy[id]; lazy[id
45.
Efficient and easy segment trees This is my first attempt at writing something useful, so your suggestions are welcome.
Most participants of programming contests are familiar with segment trees to some degree, especially having read this articles http://codeforces.me/blog/entry/15890, http://e-maxx.ru/algo/segment_tree (Russian only). If you're not — don't go there yet. I advise to read them after this article for the sake of examples, and to compare implementations and choose the one you like more (will be kinda obvious).
Segment tree with single element modifications
==================
Let's start with a brief explanation of segment trees. They are used when we have an array, perform some changes and queries on continuous segments. In the first example we'll consider 2 operations:
1. modify one element in the array;
2. find the sum of elements on some segment.
[cut]
.
### Perfect binary tree
I like to visualize a segment tree in the following way: [image link](http://i.imgur.com/GGBmcEP....
void apply(int p, int value, int k) { t[p] = value * k; if (p < n) d[p] =
value; } ~~~~~, void build() { // build the tree for (int i = n - 1; i > 0; --i) t[i] = t[i<<1]
+ t[i<<1|1]; }, void build(int p) { while (p > 1) p >>= 1, t[p] = max(t[p<<1], t[p<<1|1]) +
d[p]; }, void inc(int l, int r, int value) { l += n, r += n; int l0 = l, r0 = r; for (;
l < r; l, void modify(int p, int value) { // set value at position p for (t[p += n] =
value; p > 1; p, void push(int p) { for (int s = h; s > 0; --s) { int i = p >> s; if (d[i] != 0, ~~~~~ void apply(int p, int value) { t[p] += value; if (p < n) d[p] += value; }, ~~~~~ void build(int l, int r) { int k = 2; for (l += n, r += n-1; l > 1; k <<=
1) { l, ~~~~~ void calc(int p, int k) { if (d[p] == 0) t[p] = t[p<<1] + t[p<<1|1]; else
t[p] = d[p, ~~~~~ void modify(int l, int r, int value) { for (l += n, r += n; l < r; l >>=
1, r >>= 1, ~~~~~ void modify(int p, const S& value) { for (t[p += n] = value; p >>= 1; )
t[p] = combine(t, ~~~~~ void push() { for (int i = 1; i < n; ++i) { t[i<<1] += t[i]; t[i<<1|1] +=
t[i
46.
Editorial of Codeforces Round #672 (Div. 2) [problem:1420A]
<spoiler summary="Hint">
Any array can be sorted using no more than $\frac{n(n-1)}2$ operations. Think or guess when we need exactly $\frac{n(n-1)}2$ operations.
</spoiler>
<spoiler summary="Solution">
[tutorial:1420A]
</spoiler>
<spoiler summary="Code in C++ (Wind_Eagle)">
~~~~~
#include<iostream>
using namespace std;
int a[1000000+5];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while (t--)
{
int n;
cin>>n;
for (int i=0; i<n; i++)
{
cin>>a[i];
}
bool can=false;
for (int i=1; i<n; i++)
{
if (a[i]>=a[i-1])
{
can=true;
break;
}
}
if (can) cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
}
~~~~~
</spoiler>
[problem:1420B]
<spoiler summary="Hint">
Think of a simple criteria when `a...
inline void erase(int i) { if (i==0||i==n+1) return; if (a[i-1]a[i+1]) ans, inline void insert(int i) { if (i==0||i==n+1) return; if (a[i-1]a[i+1]) ans, public static void main(String[] args) throws IOException { (new C2_Java()).run, public static void main(String[] args) throws IOException { (new D_Java()).doIt, public void doIt() throws IOException { BufferedReader in = new
BufferedReader(new, public void run() throws IOException { BufferedReader in = new
BufferedReader(new, static void shuffleArray(int[] a) { Random rnd = new Random(); for (int i =
a.length-1; i > 0, template inline void umax(T &a, const T &b) { a = max(a, b); }, template inline void umin(T &a, const T &b) { a = min(a, b); }
Tutorial of Codeforces Round 672 (Div. 2)
47.
Editorial for Codeforces Round #761 (Div. 2) Thanks for participating, hope you enjoyed the problems! Implementations for the problems are chosen randomly among testers, and I made some changes to their codes (for example, deleted meaningless comment lines). Please do not hesitate to provide feedback in the comments, so I can improve in setting problems next time.
**UPD**: Sorry but there is a checker bug in problem E. All submissions of problem E will be rejudged soon.
**UPD2:** Rejudge done, the round remains rated.
<spoiler summary="Statistics">
Number of FST for rated participants:
- Problem A: $29$
- Problem B: $90$
- Problem C: $12$
- Problem D1: $4$
- Problem D2: $0$
- Problem E: $6$
Number of AK: $22$
Number of clarifications: $85$
</spoiler>
[problem:1617A]
<spoiler summary="Hint">
When is the lexicographically smallest permutation of $S$ (i.e. the sorted string) not the answer?
</spoiler>
<spoiler summary="Solution">
If there are no occurrences of `a`, `b` or `c` in $S$, ...
()); void solve(int tc) { int n; cin >> n; while(1) { int k, public static void main(String[] args) { Scanner fs = new Scanner(System.in);
int T, static void sort(int[] a) { ArrayList l=new ArrayList<>(); for (int i:a) l.add(i
Tutorial of Codeforces Round 761 (Div. 2)
48.
Counting primes in $\tilde{{\cal O}}(n^{2/3}\,\,)$ _Some time ago I read [this](https://projecteuler.net/thread=10;page=5#111677) post about calculating prime-counting function in $O(n^{3/4})$ (you have to solve problem 10 to access the post). And in the end author mentioned that there is $O(n^{2/3})$ solution. To my surprise I was not able to find any more or less relevant information on the internet about that. Maybe there is a beautiful blog describing all of this on 10-th page of google, but I decided to collect information I found in this post._
###Prerequisites
- From [distribution of prime numbers](https://en.wikipedia.org/wiki/Prime_number_theorem) $n$-th prime is approximately $n \ln n$, I will use it while proving complexities.
###$\tilde O(n^{3/4})$
Let's start with $O(n^{3/4})$ approach from Project Euler. We will need some definitions:
- $\pi(n)$ — prime counting function, i.e. number of primes which are not greater than $n$.
- $S(n, a)$ — suppose we take all numbers from $1$ to $n$ and sieve them w...
void add(int i, int k) { for (; i < n; i = (i | (i + 1))) tree[i, void phi(ll n, int a, int sign = 1) { if (n == 0) return; if (a == -1
49.
CodeCraft-21 and Codeforces Round #711 (Div. 2) Editorial [problem:1498A]
==================
#### [**Video Editorial**](https://www.youtube.com/watch?v=lV5cb8wh3sE)
**Author and Problemsetting:** [user:ninja_28,2021-03-29]
**Editorialist:** [user:sigma_g,2021-03-29]
<spoiler summary="Hint">
Can you think of the simplest properties that relate a number and its sum of digits?
</spoiler>
<spoiler summary="Hint 2">
Note that if $X$ is a multiple of 3, then **both** $X$ as well as the sum of digits of $X$ are a multiple of 3! Can you put this property to use here?
</spoiler>
<spoiler summary="Hint 3">
If $X$ is a multiple of 3, then $\texttt{gcd-sum}(X) \ge 3$. Therefore, we are guaranteed that at least every third number will satisfy the constraints required by our problem $(\texttt{gcd-sum}(X) > 1)$.
</spoiler>
<spoiler summary="Solution">
Therefore, for the input $n$, we can simply check which one of $n$, $n+1$, and $n+2$ has its gcd-sum $> 1$, and print the lowest of them.
</spoiler>
<spoi...
int main(void) { int t; cin >> t;, void dfs(VVI &adj, int node, int prev) { dp[node][0] = a[node];
Tutorial of CodeCraft-21 and Codeforces Round 711 (Div. 2)
50.
C++17, competitive programming edition C++17 is now [available](http://codeforces.me/blog/entry/57646) on codeforces, community [wants](http://codeforces.me/blog/entry/15643?#comment-413401) new edition of [C++ tricks](http://codeforces.me/blog/entry/15643) by [user:Swift,2018-02-19], so, let's start!
Disclaimer: I have done only few examples of new features, which in my opinion are related to competitive programming. Feel free to comment and provide more real-world examples or ask to elaborate some features with more examples or explanations.
### Fold expressions
* I think that everybody knows, what reduce or fold means, but a c++11 example:
```
vector<int> v = {1, 3, 5, 7};
int res = accumulate(v.begin(), v.end(), 0, [](int a, int b) { return a + b; });
cout << res; // 16
```
* In C++17 there is also folding support for a template parameters list. It has the following syntax:
```
(pack op ...)
(... op pack)
(pack op ... op init)
(init op ... op pack)
```
* For example, implement a template...
// C++14 void func() { auto lambda1 = [self = *this]() { self.f, // C++17 void funcNew() { auto lambda1 = [*this]() { f(); }; auto, ``` //C++17 template void readln(Args&... args) { ((cin >> args), ...); }, template void writeln(Args... args) { ((cout << args << " "), ...); }, void f() const { cout << x << '\n'; }, void g() { x++; }
51.
Implementing Dinitz on bipartite graphs Hi everyone!
if you read about [Dinic algorithm](https://cp-algorithms.com/graph/dinic.html) on CP-Algorithms, especially the [section](https://cp-algorithms.com/graph/dinic.html#unit-networks) about how it works on unit networks, you'll notice that its supposed runtime for bipartite matching is $O(E \sqrt V)$, where $E$ is the total number of edges, and $V$ is the total number of vertices of a bipartite graph. Let's try it out on the following problem:
**[Library Checker — matching on Bipartite Graph](https://judge.yosupo.jp/problem/bipartitematching)**. Given a bipartite graph with $V, E \leq 2 \cdot 10^5$, find the maximum matching.
The implementation of the Dinitz algorithm that I typically use looks as follows:
<spoiler summary="code">
```cpp
struct unit_network {
int n;
vector<int> to, cap;
vector<vector<int>> g;
unit_network(int n): n(n), g(n) {}
void add_edge(int a, int b, int cp) {
g[a].push_back(size(to));
...
void add(int a, int b) { add_edge(a, b, 1); add_edge(b, a, 0); }, void add(int a, int b) { g[a].push_back(b); }, void add_edge(int a, int b, int cp) { g[a].push_back(size(to)); to.push_back(b, void dinic() { while(build_layers()) { ptr.assign(n, 0); while
52.
Efficient linear algebra for dummies Hi everyone!
Some time ago I started developing a linear algebra library for Library Checker, and it turned out to be much fun. I'd like to write this blog to outline how one can implement a linalg library with a very good Library Checker performance, while also avoiding highly technical low-level details that are common in other similar blogs. Instead, we will learn a few high level ideas that will let us write a code that the compiler will then optimize using all these fancy techniques _in our stead_.
Huge thanks to ~ToxicPie9,2024-05-08 and [user:magnus.hegdahl,2024-05-08] for explaining me some of the optimizations used here! You may also look into ~sslotin,2024-05-08's [entry](https://codeforces.me/blog/entry/101655) about how it can be sped up even further with more advanced and low-level techniques.
### Tl'dr.
In this blog, I present my [matrix library](https://cp-algorithms.github.io/cp-algorithms-aux/cp-algo/linalg/matrix.hpp), which maintains a simple and elegant...
```cpp // Subtract a's contribution from b void reduce(int &b, int a) { b =
min(b, b ^ a
53.
Editorial of Codeforces Round 796 [problem:1688A]
Idea: [user:huangzirui,2022-06-03].
Solution: [user:huangzirui,2022-06-03].
Preparation: [user:huangzirui,2022-06-03].
Good problem
Average problem
Bad problem
Did not solve
<spoiler summary="Hint">
Consider $x=2^k$ and $x\ne 2^k$ separately.
</spoiler>
<spoiler summary="Solution">
Let $p_i$ be the $i$-th bit of $x$, $q_i$ be the $i$-th bit of $y$ (both indexed from $0$).
$x\ \texttt{and}\ y > 0\Leftrightarrow \exists i,\ p_i= q_i = 1$.
$x\ \texttt{xor}\ y > 0\Leftrightarrow \exists i,\ p_i\ne q_i$.
To satisfy the first condition, find the minimum integer $k$ satisfying $p_k=1$, and assign $1$ to $q_k$.
If $x\ne 2^k$, the second condition is satisfied now. Otherwise, find the minimum integer $j$ satisfying $p_j=0$, and assign $1$ to $q_j$.
The time complexity is $O(1)$.
</spoiler>
<spoiler summary="Code (C++)">
```cpp
#include<bits/stdC++.h>
...
void DIF(int *a, int l) { int *j, *k, n = 1 << l, len = n >> 1, r, *o;, void DIT(int *a, int l) { int *j, *k, n = 1 << l, len = 1, r, *o;, void add(int& x, int y) { if ((x += y) >= P) x -= P; }, void check(int k) { int nn = n; if (k > nn) { while (k > nn) nn <<= 1, void pre(int n) { N = n; sum.resize(n * 4); prd.resize(n * 4); build(1, 0, n); }, void redeg(int d) { a.resize(d + 1); }, void sub(int& x, int y) { if ((x -= y) < 0) x += P; }
Tutorial of Codeforces Round 796 (Div. 1)
Tutorial of Codeforces Round 796 (Div. 2)
54.
A modulo multiplication method that is 2x faster than compiler implementation > Given $k,m$ and $n$ numbers $a_i$, compute each $a_i\times k\bmod m$
I came up with a method that is almost twice as fast as the compiler implementation (when $m$ is a constant), which can effectively speed up the NTT and some DPs.
First of all
$$
a_i\times k\bmod m=\{a_i\times \frac km\}\times m\tag1
$$
where $\\{x\\}=x-\lfloor x\rfloor$ is the fractional part function. The principle of equation $(1)$ is that $a_i\times k\bmod m$ is only related to the fractional part of $\frac{a_i\times k}m$.
Let $\frac km\approx\frac p{2^{64}}$, $p$ is either equal to $\lfloor\frac km\times2^{64}\rfloor$ or $\lceil\frac km\times2^{64}\rceil$, which one to choose, we will decide later, then
$$
\begin{aligned}
a_i\times k\bmod m&\approx\{a_i\times \frac p{2^{64}}\}\times m\\
&=\frac{a_ip\bmod 2^{64}}{2^{64}}\times m\\
&=\frac{a_ip\bmod 2^{64}\times m}{2^{64}}
\end{aligned}
\tag2
$$
There are two place we need to choose whether round up or down:
- $p=\lfloor\frac km\t...
assert(checkSum1 == checkSum2 && checkSum2 == checkSum3); } void LatencyTest()
{ int, void ThroughputTest() { int checkSum1 = 0, checkSum2 = 0, checkSum3 = 0;
55.
[Tutorial] Voronoi Diagram and Delaunay Triangulation in O(n log n) with Fortune's Algorithm What's a Voronoi Diagram?
------------------
Given a set $S$ of $n$ points in the 2D plane, the Voronoi diagram is a partition of the plane into regions. The region associated with a point $p\in S$ contains precisely the points $q$ such that $q$ is closer to $p$ than any other point in $S$. In other words, a point $q$ belongs to the region of its nearest neighbor.
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/54/Euclidean_Voronoi_diagram.svg/1024px-Euclidean_Voronoi_diagram.svg.png" width="300px" height="auto"/>
The Voronoi diagram can be represented by the planar graph of boundaries between regions. A vertex in this graph is where three or more segments meet (or a point at infinity), and an edge is a segment connecting two of these vertices. The way the regions were defined, we see that a segment contains the points equidistant to two points in $S$, so it is part of their perpendicular bisector. Similarly, a Voronoi vertex is equidistant to three or more v...
edges } // update the remove event for the arc at position it void
upd(beach::iterator it
56.
Tricks Which Will Increase Your Rating! Hello Codeforces! I got some interesting tricks to share with you.
### 1. a_i := (a_i + x)%mod Range Updates, Max Range Queries
Apply usual range addition, but after each update run the following code:
```cpp
void normalize(int l, int r) {
while(getmax(l, r).max >= mod) {
set(getmax(l, r).pos, getmax(l, r).max%mod);
}
}
```
What is the complexity of this code? We all know that each time we %%=mod$ number which is $\geqslant mod$ it halves, that means each number will be updated $O(log)$ times, we will perform $O(n\cdot\log{n}\cdot\log{a})$ operations in total. So each update will be $O(\log{n}\cdot\log{a})$ amortized!
### 2. $O(\log^2{\log{n}})$ Segment Tree
Segment tree queries are queries on path. Instead of doing them in the usual brute force-ish way we can use HLD! Since maximum path length is $2\cdot\log{n}$, thus operations are now operations are $O(\log^2{\log{n}})$, which is better than $O(\log{n})$.
### 3. Faster Dinic's
We know t...
```cpp void normalize(int l, int r) { while(getmax(l, r).max >= mod) {
set(getmax(l
57.
Codeforces Round #616 Editorial Hello everyone, this is the editorial for [contest:1290] and [contest:1291]! Along with the solution to each problem, we will have the theme and easter egg solution as well! I hope you all enjoyed our problems ( ´ ▽ ` )b
[problem:1291A]
Author: [user:265918,2020-02-02]
<spoiler summary="Tutorial">
[tutorial:1291A]
</spoiler>
<spoiler summary="Implementation">
~~~~~
#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;
string s; cin >> s;
int odd = 0;
for (char c : s) if ((c - '0') & 1) odd++;
if (odd <= 1) { cout << "-1\n"; continue; }
int cnt = 0;
for (char c : s) {
if ((c - '0') & 1) { cout << c; cnt++; }
if (cnt == 2) break;
}
cout << '\n';
}
return 0;
}
~~~~~
</spoiler>
[problem:1291B]
Author: [user:hugopm,2020-02-02...
inline void operator+=(node oth) { l = min(INF, l + oth.l); r = min(INF, r, void add(int &x, int y) { x += y; if (x >= MOD) { x -= MOD; } }
Tutorial of Codeforces Round 616 (Div. 1)
Tutorial of Codeforces Round 616 (Div. 2)
58.
I don't think the interactor of CF1557E is smart enough. Hello, codeforces! I don't think the interactor of [CF1557E](https://codeforces.me/contest/1557/problem/E) is smart enough. Many wrong codes can get Accepted.
First, the hack input format in CF1557E is:
```
T
x[1] y[1]
x[2] y[2]
...
x[T] y[T]
```
As you see, we can only input the coordinate of the King, but the King's route is by interactor.
So I have no way to hack it, but to post a blog to say it.
Take my code as an example: https://codeforces.me/contest/1557/submission/125431623 .
It's not correct, and it can be easily hacked.
Here is my `Hand Player` , which you can control the King's route (use Windows) :
```
// Author: wlzhouzhuan
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pb push_back
#define fir first
#define sec second
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, t) memset(...
T2> void ckmin(T1 &a, T2 b) { if (a > b) a = b; } template void ckmax(T1
59.
[Tutorial] Minimum Deque Here I will describe a way to maintain deque that will allow us to find the smallest element in deque at any time. Maybe this technique is well-known, but I couldn’t find any info about it, so decided to post it there.
### Minimum Stack and Minimum Queue
First, we want to maintain stack with the ability to find its smallest element whenever we want. Let's store minimums on the corresponding prefix of stack along with elements. This way we can easily push/pop elements and find minimum in $O(1)$.
Minimum Queue can be maintained using two Minimum Stacks: one stack will store some elements from beginning, and the other from the end. We will push elements to the second stack and pop them from the first. If the first stack becomes empty, then we move all elements from the second stack into the first. It will work in $O(N)$ amortized.
### Minimum Deque
Actually, we can maintain Minimum Deque the same way we maintain Minimum Queue, but it will be too slow. The problem is the num...
();} void push(int x) { int mn = x; if (!empty()) mn = min(mn, getmin());
st.push({x, mn, struct mindeque { minstack l, r, t; void rebalance() { bool f = false; if
(r.empty()) {f
60.
Codeforces Round #564 Editorial [problem:1173A]
Idea: [user:ouuan,2019-06-07]
<spoiler summary="Tutorial">
Consider the two edge cases: all the $z$ persons upvote / all the $z$ persons downvote. If the results are the same in these two cases, it is the answer. Otherwise, the result is uncertain.
</spoiler>
<spoiler summary="Solution">
```cpp
#include <iostream>
using namespace std;
const char result[4] = {'+', '-', '0', '?'};
int solve(int x, int y)
{
return x == y ? 2 : x < y;
}
int main()
{
int x, y, z;
cin >> x >> y >> z;
cout << result[solve(x + z, y) == solve(x, y + z) ? solve(x, y) : 3];
return 0;
}
```
</spoiler>
[problem:1173B]
Idea: [user:Sooke,2019-06-07]
<spoiler summary="Tutorial">
- $m\ge\left\lfloor\frac n 2\right\rfloor+1$
Consider the chess pieces $1$ and $n$.
$\because\begin{cases}|r_1-r_n|+|c_1-c_n|\ge n-1\\\\|r_1-r_n|\le m-1\\\\|c_1-c_n|\le m-1\end{cases}$
$\therefore m-1+m-1\ge n-1$
$\therefore m\ge\frac{n+1}2$
$\because m\...
bool nroot(int x); void rotate(int x); void Splay(int x); void access(int x);
int findroot(int, void add(int u, int v); void dfs(int u);
Tutorial of Codeforces Round 564 (Div. 1)
Tutorial of Codeforces Round 564 (Div. 2)
61.
Neowise Labs Contest 1 (Codeforces Round 1018, Div. 1 + Div. 2) Editorial [Sorry about problem H.](https://codeforces.me/blog/entry/142069)
Thank you for understanding, and we hope you enjoyed the rest of the problems :D
---
<h3>[problem:2096A]</h3>
Idea: [user:SanguineChameleon,2025-04-20] <br>
<spoiler summary="Step 1">
Create your own test cases and solve them! What can you observe?
</spoiler>
<spoiler summary="Step 2">
What is the length of the $n$-th stick?
<spoiler summary="Answer">
- If $s_{n - 1} = \texttt{<}$, then $a_n = 1$, because the $n$-th stick must be shorter than all the other sticks.
- If $s_{n - 1} = \texttt{>}$, then $a_n = n$, because the $n$-th stick must be longer than all the other sticks.
</spoiler>
</spoiler>
<spoiler summary="Step 3">
Can we do something similar for the remaining sticks?
<spoiler summary="Answer">
Yes! Remove the $n$-th stick, and then solve for the remaining $n - 1$ sticks.
We can make similar observations about the $(n - 1)$-th stick.
Then, remove the $(n - 1)$-th st...
void test() { int n, k; cin >> n >> k; int m = k - 1;, void test() { int n; cin >> n;
62.
[Tutorial] 2-SAT Introduction
==================
In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time. -[Wikipedia](https://en.wikipedia.org/wiki/2-satisfiability)
If you have not heard of propositional logic before, plead read about it [here](https://brilliant.org/wiki/propositional-logic/). Wikipedia links have been provided wherever a term has been used for the first time in this tutorial. The whole algorithm is based on graph theory so it will help to be familiar with direc...
// Extracting strongly connected components void scc(int u, int id) { vis[u] =
true, void add_edge(int u, int v) { g[u].push_back(v); gr[v].push_back(u); }, void dfs(int u) { vis[u] = true;, void scc(int u, int id) { vis[u] = true; comp[u] = id;, void solve() { int N; cin >> N;
63.
[Tutorial] Simulating Cost Flow You can also read this on my blog: https://mzhang2021.github.io/cp-blog/simulating-cost-flow/
Thanks to [user:gabrielwu,2023-07-19] for proofreading.
---
This post assumes knowledge of [min/max cost flow](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem) and a rough understanding of the high-level methods for solving (successive shortest path and cycle canceling). Knowledge of specific algorithms and implementation details are not expected. Also solutions to some problems will use [Aliens trick](https://web.archive.org/web/20210511092429/http://www.serbanology.com/).
---
The cost flow problem is a well-known problem in literature that a whole slew of competitive programming problems can be formulated as. Unfortunately, competitive programming problems typically have constraints set too high for directly running even the most state of the art cost flow algorithm. However, in certain problems the flow network will have a very specific setup that allows us to figure ...
void add(T x) { pq.push(x); }, void rem(T x) { pending.push(x); while (!pq.empty() && !pending.empty() &&
pq.top
64.
Algorithm Gym :: Graph Algorithms Welcome to the new episode of [user:PrinceOfPersia,2015-01-31] presents: Fun with algorithms ;)
You can find all the definitions here in the book "Introduction to graph theory", Douglas.B West.
[cut]
Important graph algorithms :
DFS
---
The most useful graph algorithms are search algorithms. DFS (Depth First Search) is one of them.
While running DFS, we assign colors to the vertices (initially white). Algorithm itself is really simple :
~~~~~
dfs (v):
color[v] = gray
for u in adj[v]:
if color[u] == white
then dfs(u)
color[v] = black
~~~~~
Black color here is not used, but you can use it sometimes.
Time complexity : $O(n + m)$.
#### DFS tree
DFS tree is a rooted tree that is built like this :
~~~~~
let T be a new tree
dfs (v):
color[v] = gray
for u in adj[v]:
if color[u] == white
then dfs(u) and par[u] = v (in T)
...
~~~~~ vector euler; void dfs(int v,int p = -1){ euler.push_back(v); for(auto u
: adj[v, ~~~~~ void dfs(int v){ for(auto u : adj[v]) if(u - par[v]) dfs(u), p[v] +=
p[u]; } ~~~~~, ~~~~~ void dfs(int v,int p = -1){ if(par + 1) h[v] = h[p] + 1; par[v] = p;
for(auto u
65.
Very hard bug in a very simple code Take a look at this code:
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
vector<int> k;
int f()
{
k.push_back(3);
return 3;
}
int main()
{
k.push_back(1);
k[0] = f();
cout << k[0];
}
~~~~~
</spoiler>
At first glance, it should output $3$ because that's what $f()$ returns, which is then assigned to $k_0$. But when executed, this code outputs $1$!
This code is very short and everything seems clear, we're simply assinging $k_0$ to the return value of $f()$ which is $3$, and the push_back in $f()$ clearly doesn't affect the result... or does it?
<h3>How an assingment operation really works</h3>
It may seem obvious at first, we just copying one value to another, but let's see how compiler actually handles this operation.
Consider this code. ([Source](https://en.cppreference.com/w/cpp/language/eval_order.html))
<spoiler summary="Code">
~~~~~
#include <cstdio>
int a() { return std::puts("a...
void z(int, int, int) {}
66.
Codeforces Round #800 Editorial ###[problem:1694A]
Idea: [user:AmShZ,2022-06-16]
<spoiler summary="Solution">
[tutorial:1694A]
</spoiler>
<spoiler summary="Implementation">
~~~~~
# include <bits/stdc++.h>
using namespace std;
int t, A, B;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> t;
while (t --){
cin >> A >> B;
for (int i = 0; i < min(A, B); ++ i)
cout << "01";
for (int i = 0; i < abs(A - B); ++ i)
cout << (A < B ? 1 : 0);
cout << '\n';
}
return 0;
}
~~~~~
</spoiler>
###[problem:1694B]
Idea: [user:AmShZ,2022-06-16]
<spoiler summary="Solution">
[tutorial:1694B]
</spoiler>
<spoiler summary="Implementation">
~~~~~
# include <bits/stdc++.h>
using namespace std;
int t, n;
string S;
long long ans;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> t;
while (t --){
cin >> n >> S, ans = n;
for (int i = 1; i < n; ++ i)
if (S[i] != S[i - 1])
ans += i;
cout << ans << '\n';
...
void bld(int id, int s, int e){ if(e - s == 1){ seg[id] = cst[int(cnl[s] >
0)][int(cnr[s] > 0, void mofen(int pos, int val){ for (pos += 5; pos < N; pos += pos & - pos)
fen[pos] = min(fen
Tutorial of Codeforces Round 800 (Div. 1)
Tutorial of Codeforces Round 800 (Div. 2)
67.
Educational Codeforces Round 151 Editorial [problem:1845A]
Idea: [user:BledDest,2023-06-30]
<spoiler summary="Tutorial">
[tutorial:1845A]
</spoiler>
<spoiler summary="Solution (awoo)">
~~~~~
for _ in range(int(input())):
n, k, x = map(int, input().split())
if x != 1:
print("YES")
print(n)
print(*([1] * n))
elif k == 1 or (k == 2 and n % 2 == 1):
print("NO")
else:
print("YES")
print(n // 2)
print(*([3 if n % 2 == 1 else 2] + [2] * (n // 2 - 1)))
~~~~~
</spoiler>
[problem:1845B]
Idea: [user:adedalic,2023-06-30]
<spoiler summary="Tutorial">
[tutorial:1845B]
</spoiler>
<spoiler summary="Solution (adedalic)">
~~~~~
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
pt A, B, C;
inline bool read() {
if(!(cin >> A.x >> A.y))
return false;
cin >> B.x >> B.y;
cin >> C.x >> C.y;
r...
inline void solve() { FFT::precalc();, inline void solve() { cout << (dist(A, B) + dist(A, C) - dist(B, C)) / 2 + 1 <<
endl; }
68.
Global Round 19 Editorial We hope you enjoyed the contest! We recommend you to read all tutorials even if you solve the problem, maybe you will learn something new.
[problem:1637A]<br>
Idea: [user:__JustMe__,2022-02-12].
<spoiler summary="Hint 1">
What does happen if the array is already sorted?
</spoiler>
<spoiler summary="Hint 2">
What does happen if there are two indexes $i$ and $j$, such that $i < j$ and $a_i > a_j$?
</spoiler>
<spoiler summary="Tutorial">
[tutorial:1637A]
</spoiler>
<spoiler summary="Solution">
```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
for (int i = 0; i < t; i++) {
int n;
cin >> n;
vector<int> a(n);
for (auto& u : a)
cin >> u;
if (!is_sorted(a.begin(), a.end()))
cout << "YES\n";
else
cout << "NO\n";
}
}
```
</spoiler>
[problem:1637B]<br>
Idea: [user:__JustMe__,2022-02-12] and [user:Mangooste,2022-02-12].
...
void increase(int pos) { for (pos++; pos <= n; pos += pos & -pos) bit[pos]++; }, void input() { cin >> n; vec.resize(n); for (auto& c : vec) cin >> c;, void solve() { int n; cin >> n;
Tutorial of Codeforces Global Round 19
69.
General ideas **// Finally translated!**
Hi everyone!
Do you like ad hoc problems? I do hate them! That's why I decided to make a list of ideas and tricks which can be useful in mane cases. Enjoy and add more if I missed something. :)
[cut]<br>
**1. Merging many sets in $O(n\log{n})$ amortized.** If you have some sets and you often need to merge some of theme, you can do it in naive way but in such manner that you always move elements from the smaller one to the larger. Thus every element will be moved only $O(\log{n})$ times since its new set always will be at least twice as large as the old one. Some versions of DSU are based on this trick. Also you can use this trick when you merge sets of vertices in subtrees while having dfs.
**2. Tricks in statements, part 1.** As you may know, authors can try to hide some special properties of input to make problem less obvious. Once I saw constraints like $\relax 1 \leq a \leq b \leq 10^5, \dots, ab \leq 10^5$. Ha-ha, nice joke. It is actually...
void inverse(int *from, int *to) { if(to - from == 1) return; int *mid, ~~~~~ void transform(int *from, int *to) { if(to - from == 1) return; int
70.
Educational Codeforces Round 103 Editorial [problem:1476A]
Idea: [user:vovuh,2021-01-30]
<spoiler summary="Tutorial">
[tutorial:1476A]
</spoiler>
<spoiler summary="Solution (adedalic)">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
long long n, k;
cin >> n >> k;
long long cf = (n + k - 1) / k;
k *= cf;
cout << (k + n - 1) / n << endl;
}
return 0;
}
~~~~~
</spoiler>
[problem:1476B]
Idea: [user:adedalic,2021-01-30]
<spoiler summary="Tutorial">
[tutorial:1476B]
</spoiler>
<spoiler summary="Solution (adedalic)">
~~~~~
#include<bits/stdc++.h>
using namespace std;
typedef long long li;
const int INF = int(1e9);
int main() {
int t; cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
vector<int> p(n);
for (int i = 0; i < n; i++)
cin >> p[i];
li x = 0;
li pSum = p[0];
for (int i = 1; i < n; i++) {
x = max(x, (100ll * p[i] - k * pS...
void build() { return build(0, 0, n); }, void upd(int pos, int val) { upd(0, 0, n, pos, val); }
71.
Educational Codeforces Round 142 Editorial [problem:1792A]
Idea: [user:BledDest,2023-01-25]
<spoiler summary="Tutorial">
[tutorial:1792A]
</spoiler>
<spoiler summary="Solution (Neon)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int cnt1 = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
cnt1 += (x == 1);
}
cout << n - cnt1 / 2 << '\n';
}
}
~~~~~
</spoiler>
[problem:1792B]
Idea: [user:BledDest,2023-01-25]
<spoiler summary="Tutorial">
[tutorial:1792B]
</spoiler>
<spoiler summary="Solution (awoo)">
~~~~~
for _ in range(int(input())):
a1, a2, a3, a4 = map(int, input().split())
if a1 == 0:
print(1)
else:
print(a1 + min(a2, a3) * 2 + min(a1 + 1, abs(a2 - a3) + a4))
~~~~~
</spoiler>
[problem:1792C]
Idea: [user:BledDest,2023-01-25]
<spoiler summary="Tutorial">
[tutorial:1792C]
</spoiler>
<spoiler summary="Solut...
inline void solve() { factM(m1, m2);, void factM(li m1, li m2) { mFact.clear();, void precalc() { int wb = binPow(g, (MOD - 1) / (1 << LOGN));
72.
Educational Codeforces Round 106 Editorial [problem:1499A]
Idea: [user:adedalic,2021-03-19]
<spoiler summary="Tutorial">
[tutorial:1499A]
</spoiler>
<spoiler summary="Solution (adedalic)">
~~~~~
fun main() {
repeat(readLine()!!.toInt()) {
val (n, k1, k2) = readLine()!!.split(' ').map { it.toInt() }
val (w, b) = readLine()!!.split(' ').map { it.toInt() }
if (k1 + k2 >= 2 * w && (n - k1) + (n - k2) >= 2 * b)
println("YES")
else
println("NO")
}
}
~~~~~
</spoiler>
[problem:1499B]
Idea: [user:BledDest,2021-03-19]
<spoiler summary="Tutorial">
[tutorial:1499B]
</spoiler>
<spoiler summary="Solution (Neon)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int i = s.find("11");
int j = s.rfind("00");
cout << (i != -1 && j != -1 && i < j ? "NO" : "YES") << endl;
}
}
~~~~~
</spoiler>
[problem:1499C]
Idea: [use...
void merge_paths(int x, int y, int v) { if(x == y) {, void pop_back() { ds[d].pop_back(); }, void pop_front() { ds[d].pop_front(); }, void push_back(int i) { safe_push_back(ds[d], i, c); }, void push_front(int i) { safe_push_front(ds[d], i, c); }, void reverse() { ::reverse(ds[d]); swap(s, t); }
73.
Educational Codeforces Round 91 Editorial [problem:1380A]
Idea: [user:BledDest,2020-07-12]
<spoiler summary="Tutorial">
[tutorial:1380A]
</spoiler>
<spoiler summary="Solution (Ne0n25)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int n;
int a[N];
void solve() {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 1; i < n - 1; ++i) {
if (a[i] > a[i - 1] && a[i] > a[i + 1]) {
cout << "YES" << endl;
cout << i << ' ' << i + 1 << ' ' << i + 2 << endl;
return;
}
}
cout << "NO" << endl;
}
int main() {
int T;
cin >> T;
while (T--)
solve();
}
~~~~~
</spoiler>
[problem:1380B]
Idea: [user:adedalic,2020-07-12]
<spoiler summary="Tutorial">
[tutorial:1380B]
</spoiler>
<spoiler summary="Solution (adedalic)">
~~~~~
fun main() {
val winBy = mapOf('R' to 'P', 'S' to 'R', 'P' to 'S')
repeat(readLine()!!.toInt()) {
val s = readLine()!!
val maxCnt = s.groupingBy { it }.eachCount().maxBy ...
void add(int &a, int x) { a += x; a %= MOD; }
74.
Codeforces Round 1034 (Div. 3) Editorial I hope you all enjoyed the contest!
<spoiler summary="Rating Predictions">
| Predictor | A | B | C | D | E | F | G |
|------------------------------------|--------|--------|--------|--------|--------|--------|--------|
| [user:AksLolCoding,2025-07-01] | 800 | 900 | 1000 | 1500 | 1500 | 1800 | 1700 |
| [user:__baozii__,2025-07-01] | 800 | 800 | 1200 | 1500 | 1500 | 1600 | 1900 |
| [user:DivinePunishment,2025-07-01] | 800 | 900 | 1100 | 1400 | 1500 | 1600 | 1900 |
| [user:Edeeva,2025-07-01] | 800 | 800 | 1000 | 1200 | 1600 | 1800 | 2200 |
| [user:efishel,2025-07-01] | 800 | 800 | 1000 | 1200 | 1400 | 1500 | 1900 |
| [user:-firefly-,2025-07-01] | 800 | 800 | 900 | 1400 | 1500 | 1700 | 2000 |
| [user:hashman,2025-07-01] | 800 | 900 | 1100 | 1600 | 1500 | 1800 | ...
void solve(){ int n; cin >> n; cout << (n % 4 ? "Alice" : "Bob") << '\n'; }
Tutorial of Codeforces Round 1034 (Div. 3)
75.
Educational Codeforces Round 101 Editorial [problem:1469A]
Idea: [user:BledDest,2020-12-29]
<spoiler summary="Tutorial">
[tutorial:1469A]
</spoiler>
<spoiler summary="Solution 1 (BledDest)">
~~~~~
t = int(input())
for i in range(t):
s = input()
if len(s) % 2 == 0 and s[0] != ')' and s[-1] != '(':
print('YES')
else:
print('NO')
~~~~~
</spoiler>
<spoiler summary="Solution 2 (BledDest)">
~~~~~
t = int(input())
for i in range(t):
s = input()
n = len(s)
a = [s[i] for i in range(n)]
cnt = n // 2 - 1
for j in range(n):
if a[j] == '?':
if cnt > 0:
cnt -= 1
a[j] = '('
else:
a[j] = ')'
bal = 0
minbal = 0
for j in range(n):
if a[j] == '(':
bal += 1
else:
bal -= 1
minbal = min(bal, minbal)
print('YES' if bal == 0 and minbal >= 0 else 'NO')
~~~~~
</spoiler>
[problem:1469B]
Idea: [user:Bled...
inline void solve() { vector ans; calc(n, ans);, void calc(int n, vector &ans) { if (n == 2) return;
76.
Codeforces Round #846 (Div. 2) — Tutorial [problem:1780A]
Idea: [user:AndreyPavlov,2023-01-24] <br> Preparation: [user:AndreyPavlov,2023-01-24] <br> Editorialist: [user:AndreyPavlov,2023-01-24]
<spoiler summary="Tutorial">
Note that there are two variants of which numbers to take to make their amount odd: $3$ odd number; $2$ even and $1$ odd. Let’s save all indices of even and odd numbers into two arrays, and check both cases.
</spoiler>
<spoiler summary="Implementation (Python)">
~~~~~
def solve():
n = int(input())
a = list(map(int, input().split()))
odd, even = [], []
for i in range(n):
if a[i] % 2 == 0:
even.append(i + 1)
else:
odd.append(i + 1)
if len(odd) >= 1 and len(even) >= 2:
print("YES")
print(odd[0], even[0], even[1])
elif len(odd) >= 3:
print("YES")
print(odd[0], odd[1], odd[2])
else:
print("NO")
t = int(input())
for test in range(t):
solve()
~~~~~
</spoiler...
template void print(T x, string end = "\n") { cout << x << end; }, void add (char c) { lst = add(lst, get(c)); }
Tutorial of Codeforces Round 846 (Div. 2)
77.
Editorial for Codeforces Round #919 (Div. 2) ##Information about the round
<spoiler summary="Rating predictions (inspired by BucketPotato's editorial)">
| Person | A | B | C | D | E | F1 | F2 |
|--------------------------------------------|------|------|------|------|------|------|------|
| [user:sum,2024-01-13] | 800 | 1300 | 1500 | 1900 | 2000 | 2200 | 2900 |
| [user:oursaco,2024-01-13] | 800 | 1100 | 1300 | 1600 | 1800 | 2100 | 3100 |
| [user:omeganot,2024-01-13] | 900 | 1000 | 1400 | 1700 | 1900 | 2200 | 2800 |
| [user:sriniv,2024-01-13] | | | | 1900 | 2000 | 1900 | |
| [user:apple_method,2024-01-13] | 1000 | 1200 | 1400 | 1900 | 1600 | | |
| [user:awesomeguy856,2024-01-13] | 800 | 1100 | 1400 | 1800 | 1900 | 2000 | 2800 |
| [user:nonrice,2024-01-13] | 900 | 1000 | 1400 | 1750 | | | |
| [user:null_aw...
void solve(){ int n, k, x; cin >> n >> k >> x;, void solve(){ int n, k; cin >> n >> k;, void solve(){ int n, q; cin >> n >> q;, void solve(){ int n; cin >> n;
Tutorial of Codeforces Round 919 (Div. 2)
78.
Educational Codeforces Round 90 Editorial [problem:1373A]
Idea: [user:Roms,2020-06-26]
<spoiler summary="Tutorial">
[tutorial:1373A]
</spoiler>
<spoiler summary="Solution (pikmike)">
~~~~~
for tc in range(int(input())):
a, b, c = map(int, input().split())
print(1 if a < c else -1, end=" ")
print(b if c < a * b else -1)
~~~~~
</spoiler>
[problem:1373B]
Idea: [user:Roms,2020-06-26]
<spoiler summary="Tutorial">
[tutorial:1373B]
</spoiler>
<spoiler summary="Solution (Roms)">
~~~~~
for _ in range(int(input())):
s = input()
print('DA' if min(s.count('0'), s.count('1')) % 2 == 1 else 'NET')
~~~~~
</spoiler>
[problem:1373C]
Idea: [user:Roms,2020-06-26]
<spoiler summary="Tutorial">
[tutorial:1373C]
</spoiler>
<spoiler summary="Solution (Roms)">
~~~~~
for _ in range(int(input())):
s = input()
cur, mn, res = 0, 0, len(s)
for i in range(len(s)):
cur += 1 if s[i] == '+' else -1
if cur < mn:
mn = cur
res +=...
void read() { cin >> n >> k; }
79.
Educational Codeforces Round 95 Editorial [problem:1418A]
Idea: [user:vovuh,2020-09-15]
<spoiler summary="Tutorial">
[tutorial:1418A]
</spoiler>
<spoiler summary="Solution (vovuh)">
~~~~~
for i in range(int(input())):
x, y, k = map(int, input().split())
print(((y + 1) * k - 1 + x - 2) // (x - 1) + k)
~~~~~
</spoiler>
[problem:1418B]
Idea: [user:BledDest,2020-09-15]
<spoiler summary="Tutorial">
[tutorial:1418B]
</spoiler>
<spoiler summary="Solution (Ne0n25)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
void solve() {
int n;
cin >> n;
vector<int> a(n), b(n), c;
forn(i, n) cin >> a[i];
forn(i, n) cin >> b[i];
forn(i, n) if (!b[i])
c.push_back(a[i]);
sort(c.rbegin(), c.rend());
int j = 0;
forn(i, n) {
if (b[i]) cout << a[i] << ' ';
else cout << c[j++] << ' ';
}
cout << '\n';
}
int main() {
int T;
...
inline void solve() { fore(d, 1, N) { for(int pos = d; pos < N; pos += d
80.
Blowing up unordered_map 2024 edition It is already well-known that using `unordered` series in Codeforces is super dangerous, and it is not recommended to use them at all unless you know how to prevent them properly (well, even if you know, just using a regular `map` or `set` is more beneficial in most cases). Thanks to [Blowing up unordered_map, and how to stop getting hacked on it](https://codeforces.me/blog/entry/62393), it is easy to access to the basics of hacking these hash-based structures. In this blog, I'm going to get into more details on how it works, and the ideas to hack them with various constraints on the variables.
The basics
------------------
As mentioned in the linked blog, gcc implements its hash table simply by modding the key with certain primes, and these primes vary between different versions of gcc. So, basically the easiest way to make a hack case is to put numerous distinct multiples of these primes. However, an important thing to note is that it's a _list_ of primes instead of just one pr...
unordered_set st; void test_evils(const vector& evils) { st = unordered_set();
81.
Catalan Numbers and Generating Uniform Balanced Bracket Sequences Hi everyone! Today [user:nor,2022-05-27] sir and I would like to talk about generating uniform bracket sequences. Over the past few years when preparing test cases, I have had to generate a uniform bracket sequence a few times. Unfortunately I could not figure out how, so I would like to write a blog about this now. Hopefully this blog would be useful to future problem setters :) Scroll down to the end of the blog to copy our generators.
First, let's define some things. A bracket sequence is a string with $n$ $\texttt{(}$ s and $n$ $\texttt{)}$ s. A **balanced** brackets sequence is a bracket sequence with the additional constraint that it becomes a valid arithmetic expression when we add some $\texttt{1}$ s and $\texttt{+}$ s. Let $p$ be the prefix sum array of a bracket sequence (we assign $1$ to $\texttt{(}$ and $-1$ to $\texttt{)}$ and take the prefix sum). For example, if our bracket sequence is $\texttt{())()((())}$, then $p=[1,0,-1,0,-1,0,1,2,1,0]$.
An alternate way to thi...
void solve(int pl,int pr,string &s){ if (pl==pr) return;
82.
Educational Codeforces Round 171 Editorial [problem:2026A]
Idea: [user:adedalic,2024-10-29]
<spoiler summary="Tutorial">
[tutorial:2026A]
</spoiler>
<spoiler summary="Solution (adedalic)">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int X, Y, K;
cin >> X >> Y >> K;
int M = min(X, Y);
cout << "0 0 " << M << " " << M << endl;
cout << "0 " << M << " " << M << " 0" << endl;
}
}
~~~~~
</spoiler>
[problem:2026B]
Idea: [user:BledDest,2024-10-29]
<spoiler summary="Tutorial">
[tutorial:2026B]
</spoiler>
<spoiler summary="Solution (Neon)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<long long> a(n);
for (auto& x : a) cin >> x;
long long ans = 1e18;
auto upd = [&](vector<long long> a) {
sort(a.begin(), a.end());
for (int i = 1; i < (int)a.size(); ++i)
if (a[i - 1] == a[i...
struct mindeque { minstack l, r, t; void rebalance() { bool f = false; if
(r.empty()) {f
83.
Codeforces Round #722 Editorial Hi, Codeforces!
[problem:1529A]
problem idea and solution: [user:AmShZ,2021-05-24]
<spoiler summary="editorial">
[tutorial:1529A]
</spoiler>
<spoiler summary="official solution">
~~~~~
// khodaya khodet komak kon
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll> pll;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x)...
inline void upd(int &x, int y){ if (x>y) x=y;}, void MshtDFS(int u) { L[u] = timer++; for (int v : Msht[u]) { MshtDFS(v
Tutorial of Codeforces Round 722 (Div. 1)
Tutorial of Codeforces Round 722 (Div. 2)
84.
Educational Codeforces Round 124 Editorial [problem:1651A]
Idea: [user:BledDest,2022-03-11]
<spoiler summary="Tutorial">
[tutorial:1651A]
</spoiler>
<spoiler summary="Solution (BledDest)">
~~~~~
t = int(input())
for i in range(t):
n = int(input())
print(2 ** n - 1)
~~~~~
</spoiler>
[problem:1651B]
Idea: [user:adedalic,2022-03-11]
<spoiler summary="Tutorial">
[tutorial:1651B]
</spoiler>
<spoiler summary="Solution (awoo)">
~~~~~
for _ in range(int(input())):
n = int(input())
if 3**(n-1) > 10**9:
print("NO")
else:
print("YES")
print(*[3**x for x in range(n)])
~~~~~
</spoiler>
[problem:1651C]
Idea: [user:adedalic,2022-03-11]
<spoiler summary="Tutorial">
[tutorial:1651C]
</spoiler>
<spoiler summary="Solution (adedalic)">
~~~~~
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
typedef long long li;
const int INF = int(1e9);
int n;
vector<int> a, b;
inline bool read() {
if(!(ci...
inline void solve() { li bst = 10ll * INF;
85.
CodeForces Round 872(Div. 1&2) Editorial ## A. LuoTianyi and the Palindrome String
Consider the substring of $s$ from the second character to the last, or $s_2s_3\cdots s_n$. If it's not palindrome, then the answer must be $n-1$. What if it's palindrome? This implies that $s_2=s_n$, $s_3=s_{n-1}$, and so on. Meanwhile, the fact that $s$ is palindrome implies $s_1=s_n$, $s_2=s_{n-1}$, etc. So we get $s_1=s_n=s_2=s_{n-1}=\cdots$ or that all characters in $s$ is the same. In this situation, every subsequence of $s$ is palindrome of course, so the answer should be $-1$.
<spoiler summary="Code">
```cpp
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#define ll int
#define ft first
#define sd second
//#define endl '\n'
#define pb push_back
#define ll long long
#define pll pair<ll,ll>
#define no cout<<"NO"<<'\n'
#define no_ cout<<"No"<<'\n'
#def...
struct DS { multiset l,r; ll sum; DS(void){ clear();} void clear(void){ l.clear
Tutorial of Codeforces Round 872 (Div. 1)
Tutorial of Codeforces Round 872 (Div. 2)
86.
std::generator and recursive lambdas in C++23 Hi everyone!
As Codeforces now [supports C++23](https://codeforces.me/blog/entry/133046), it seems to be the right time to discuss some of the particularly interesting features.
Some noteworthy ones that were already mentioned elsewhere include:
- `views::zip` that maps two ranges into pairs `(A[i], B[i])`.
- `views::enumerate` that maps range into pairs `(i, a[i])`.
- `views::adjacent<k>` that maps range into tuples `(a[i], ..., a[i+k-1])`.
- `views::cartesian_product` that maps two ranges into pairs `(A[i], B[j])` with all possible `i` and `j`.
- Some more [specialized views](https://en.cppreference.com/w/cpp/ranges).
- `ranges::to<Container>` that creates a container out of a view, e.g. `to<vector>(views::iota(0, n))`.
- `ranges::fold_left` and `ranges::fold_right`, range versions of `std::accumulate`/`std::reduce`.
- `insert_range`/`append_range`/`prepend_range`/`assign_range` for containers (not in GCC yet).
- `print`/`println` for formatted printing (it seems t...
```cpp vector factors; void factorize(uint64_t m) { if(is_prime(m
87.
Codeforces Round #601 Editorial [problem:1255A]
Author: [user:UncleGrandpa925,2019-11-20].
Prepared by [user:UncleGrandpa925,2019-11-20]
<spoiler summary="Tutorial">
[tutorial:1255A]
</spoiler>
[problem:1255B]
Author: [user:prof.PVH,2019-11-20] ft. [user:MikeMirzayanov,2019-11-20].
Prepared by [user:UncleGrandpa925,2019-11-20]
<spoiler summary="Tutorial">
#### Modelize the problem
We modelize the problem as graph, where each fridge is a vertex and each chain is an edge between two vertexes. The problem is now equivalent to: Given a graph with $n$ vertexes, each vertex has a value $a_i \ge 0$. We have to add $m$ edges to the graph such that each vertex is connected to at least two different vertexes and the total cost of edges added is minimum. The cost of an edge is the sum of value of its two end-points.
#### Observe some basic properties of graph
Now, each edge added will increase the sum of degree of all vertexes by 2. So adding m edges will make the sum of degree equal to $2 \times m$. ...
void process(void) { memset(board, 0, sizeof board); memset(res, 0, sizeof res);
Tutorial of Codeforces Round 601 (Div. 1)
Tutorial of Codeforces Round 601 (Div. 2)
88.
Optimal Incremental MST in 20 lines of code Hello Codeforces!
Some of you might know `BottleneckTree.h` from [my KACTL fork](https://github.com/bicsi/kactl/blob/master/content/graph/BottleneckTree.h) (although it's a little obscure for an ICPC notebook; oh well). [user:freak93,2026-11-05] and I wrote it in 2021. The header says the complexity is "probably $O(\log n)$ amortized". It all started from a 2020 solution by [user:RestingRajarshi,2026-11-05] (more on that at the end). After about 6 years of on-and-off thinking about it, and with the help of Claude, we finally have an answer: it's not :). There are inputs where it takes $\Omega(\sqrt n)$ per operation.
The good news is that a small change in the main loop fixes it, and this time we have a proof. We wrote a paper about it: [Incremental Minimum Spanning Trees on a Napkin](https://arxiv.org/abs/2611.05713). I think the structure is super elegant and short enough to be useful in contests, so I'm writing a blog about it.
Prerequisites: none, really. It helps to know ...
] = INF + 1; } void rot(int x) { int p = link[x], g = link[p]; swap(cost[x],
cost[p
89.
Educational Codeforces Round 92 Editorial [problem:1389A]
Idea: [user:BledDest,2020-07-30]
<spoiler summary="Tutorial">
[tutorial:1389A]
</spoiler>
<spoiler summary="Solution (BledDest)">
~~~~~
t = int(input())
for i in range(t):
l, r = map(int, input().split())
if l * 2 > r:
print(-1, -1)
else:
print(l, l * 2)
~~~~~
</spoiler>
[problem:1389B]
Idea: [user:Roms,2020-07-30]
<spoiler summary="Tutorial">
[tutorial:1389B]
</spoiler>
<spoiler summary="Solution 1 (pikmike)">
~~~~~
for _ in range(int(input())):
n, k, z = map(int, input().split())
a = [int(x) for x in input().split()]
ans = 0
s = 0
mx = 0
for t in range(z + 1):
pos = k - 2 * t
if pos < 0:
continue
mx = 0
s = 0
for i in range(pos + 1):
if i < n - 1:
mx = max(mx, a[i] + a[i + 1])
s += a[i]
ans = max(ans, s + mx * t)
print(ans)
~~~~~
</spoiler>
<spoiler summary="Solution 2 (pikmike)">
~~~~~
for _ in range(int(input())):
n, k, z = map(int, ...
void add(int l, int r, int val) { return add(0, 0, n, l, r, val); }, void cut(int x, int y, int weight) { process_edge(x, y, -1, weight); }, void link(int x, int y, int weight) { process_edge(x, y, 1, weight); }, void upd(int pos, int val) { return upd(0, 0, n, pos, val); }
90.
Codeforces Global Round 10 — Editorial We hope you liked the problems! We apologize for the weak pretests for A and B -- that was a major oversight on our part. Hopefully you were still able to enjoy the contest regardless :)
We have to apologize to [user:antontrygubO_o,2020-08-16] a bit here -- the rejection count mentioned in the [editorial](https://codeforces.me/blog/entry/79974) for [contest:1372] actually also included this round, as the problems from that round and problems A through G in this round were created together. We did have one more problem rejected after that round happened, bringing up the total to 73. For reference, here are the overall rejection counts for each problem:
<spoiler summary="Rejection Counts">
- A: 12
- B: 16
- C: **6**
- D: 19
- E: 18
- F: 2
Total: **73**
</spoiler>
Without further ado, here are the tutorials for each of the problems:
[tutorial:1392A]
<spoiler summary="Solution (Kotlin) by golions">
~~~~~
import java.io.*
import java.util.*
import kotlin.math...
void fft(vector & a, bool invert) { int n = a.size();
Tutorial of Codeforces Global Round 10
91.
Codeforces Round 887 (Div 1, Div 2) Tutorial We hope you enjoyed these problems :) This contest has been in the works for almost a year.
<spoiler summary = "About the Authors">
This round was mostly made possible by problemsetters from the [CerealCodes](https://www.cerealcodes.org/) initiative!
CerealCodes is an organization based in the United States dedicated to running high quality competitive programming contests. You can check out our previous contest [here](https://codeforces.me/gym/103886).
</spoiler>
**UPD: D1D Editorial have been updated**
**UPD 2: D1D Editorial now has images by [user:EmeraldBlock,2023-08-01]. As an apology gift for being so slow, the image generator is programmatic and available [here](https://artofproblemsolving.com/texer/codeforces).**
#### [problem:1853A]
Problem Credits: [user:buffering,2023-06-02]
Analysis: [user:buffering,2023-06-02]
<spoiler summary="Hint 1">
To make $a$ not sorted, we just need to pick one index $i$ so $a_i > a_{i + 1}$. How do we do this?
</spoiler...
void setIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
Tutorial of Codeforces Round 887 (Div. 1)
Tutorial of Codeforces Round 887 (Div. 2)
92.
Link Cut Tree implementation Hello!
Recently I have been trying to learn link cut trees (and splay trees, for that matter). I have tried to polish an implementation that is short (for our ICPC notebooks), and also easy to use and extend. I might be extending this blog post towards a tutorial on how link cut trees are used and, more so, how this template can be used.
The implementation is here:
<spoiler summary="Implementation">
```
struct SplayTree {
struct Node {
int ch[2] = {0, 0}, p = 0;
long long self = 0, path = 0; // Path aggregates
long long sub = 0, vir = 0; // Subtree aggregates
bool flip = 0; // Lazy tags
};
vector<Node> T;
SplayTree(int n) : T(n + 1) {}
void push(int x) {
if (!x || !T[x].flip) return;
int l = T[x].ch[0], r = T[x].ch[1];
T[l].flip ^= 1, T[r].flip ^= 1;
swap(T[x].ch[0], T[x].ch[1]);
T[x].flip = 0;
}
void pull(int x) {
int l = T[x].ch[0], r = T[x].ch[1]; push...
void reroot(int x) { access(x); T[x].flip ^= 1; push(x); }
93.
DP on Trees Tutorial A certain question on Quora and some junior asking about DP on Trees is what inspired this post. Its been a long time since I wrote any tutorial, so, its a welcome break from monotonicity of events.
Pre-requisites:
- Will to read this post thoroughly. :)
- Also, you should know basic dynamic programming, the optimal substructure property and memoisation.
- Trees(basic DFS, subtree definition, children etc.)
Dynamic Programming(DP) is a technique to solve problems by breaking them down into overlapping sub-problems which follow the optimal substructure. We all know of various problems using DP like subset sum, knapsack, coin change etc. We can also use DP on trees to solve some specific problems.
We define functions for nodes of the trees, which we calculate recursively based on children of a nodes. One of the states in our DP usually is a node $i$, denoting that we are solving for the subtree of node $i$.
As we do examples, things will get clear for you.
...
void rec(int cur_node){
94.
Polynomial Round 2022 (Div. 1 + Div. 2) Editorial Thanks for your participation! I am so sorry for my careless review. We were preparing for this round for many months and made some problems which writers and testers are all like. We do want to give everyone a good time to enjoy the contest. But carelessness is deadly. In problem B, some test cases should have been made, but we missed them in not only the pretests but also the final tests. In fact, we had not noticed it until some suspicious hacks appeared. I and all co-authors sincerely regret our mistake and hope you can forgive us.
Besides, few people are cyberbullying authors, please do not do so. If you have a bad experience, you can downvote me because of our fault.
[problem:1774A]
Idea: [user:cirno_9baka,2022-12-17]
<spoiler summary="Solution">
The answer is the number of $1$s modulo $2$.
We can get that by adding '-' before the $\text{2nd}, \text{4th}, \cdots, 2k\text{-th}$ $1$, and '+' before the $\text{3rd}, \text{5th}, \cdots, 2k+1\text{-th}$ $1$.
</spoiler...
const int N = 1e6 + 5; int t[N * 2], nxt[N * 2], cnt, h[N]; int n, d; void
add(int x, int y
95.
Educational Codeforces Round 192 Editorial [problem:2242A]
Idea: [user:BledDest,2026-07-07]
<spoiler summary="Tutorial">
[tutorial:2242A]
</spoiler>
<spoiler summary="Solution (BledDest)">
~~~~~
t = int(input())
for i in range(t):
k = int(input())
a = list(map(int, input().split()))
if max(a) > 2 or a.count(2) > 1:
print('YES')
else:
print('NO')
~~~~~
</spoiler>
[problem:2242B]
Idea: [user:FelixArg,2026-07-07]
<spoiler summary="Tutorial">
[tutorial:2242B]
</spoiler>
<spoiler summary="Solution (FelixArg)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
const int INF = 1'000'000'007;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++){
cin >> a[i];
}
vector<int> pref1(n + 1);
vector<int> pref2(n + 1);
for (int i = 0; i < n; i++){
pref1[i + 1] = pref1[i] + (a[i] == 1 ? 1 : -1);
pref2[i + 1] = pref2[i] + (a[i] == 3 ? -1 : 1);
}
int mn = INF;
for (int i = 1; i < n; i++){
...
void dfs(int v) { if (!v) { return; }, void solve() { cin >> l >> r >> n;, void solve() { int n, k; cin >> n >> k;, void solve() { int n; cin >> n;
96.
Heavy-light decomposition implementation Recently I've been looking for a good heavy-light decomposition code I can just copy-paste and continue to live happily. To my greatest disappointment, I didn't find one and had to write my own.
First, there's this blog explaining what HLD is http://blog.anudeep2011.com/heavy-light-decomposition/, but it doesn't contain full code. Also it uses LCA for queries, which is absolutely unnecessary and complicates things too much.
Second, there's this implementation https://sites.google.com/site/indy256/algo/heavy_light. (It has been updated, so the comment is related to old version). OK, complete working code, and it doesn't use LCA. But it has too many arrays. Way too many! Also it's mixed with segment tree code, and I'd rather separate the logic.
Third, there's this post http://apps.topcoder.com/forums/?module=Thread&threadID=796128&start=0&mc=8. So far the best looking code, but it has only LCA method and no path query handling, which is the point of HLD. [cut] So, I refined the ...
void set(int v, const T& value) { tree.set(treePos[v], value); }
97.
Educational Codeforces Round 131 Editorial [problem:1701A]
Idea: [user:BledDest,2022-07-09]
<spoiler summary="Tutorial">
[tutorial:1701A]
</spoiler>
<spoiler summary="Solution (vovuh)">
~~~~~
for _ in range(int(input())):
a = [list(map(int, input().split())) for i in range(2)]
cnt = sum([sum(a[i]) for i in range(2)])
if cnt == 0:
print(0)
elif cnt == 4:
print(2)
else:
print(1)
~~~~~
</spoiler>
[problem:1701B]
Idea: [user:BledDest,2022-07-09]
<spoiler summary="Tutorial">
[tutorial:1701B]
</spoiler>
<spoiler summary="Solution (Neon)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << 2 << '\n';
for (int i = 1; i <= n; ++i) if (i % 2 != 0)
for (int j = i; j <= n; j *= 2)
cout << j << ' ';
cout << '\n';
}
}
~~~~~
</spoiler>
[problem:1701C]
Idea: [user:BledDest,2...
void recalc(int v) { t[v] = getVal(v * 2 + 1) + getVal(v * 2 + 2); }
98.
Codeforces Round #635 Editorial [problem:1337A]
Idea: [user:Sooke,2020-04-16]
<spoiler summary="Tutorial">
[tutorial:1337A]
</spoiler>
<spoiler summary="Solution by Sooke">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int t, a, b, c, d;
int main() {
for (cin >> t; t; t--) {
cin >> a >> b >> c >> d;
cout << b << " " << c << " " << c << endl;
}
return 0;
}
~~~~~
</spoiler>
[problem:1337B]
Idea: [user:EternalAlexander,2020-04-16]
<spoiler summary="Tutorial">
[tutorial:1337B]
</spoiler>
<spoiler summary="Solution by EternalAlexander">
~~~~~
#include <bits/stdc++.h>
int x,n,m,t;
void solve(){
scanf("%d%d%d",&x,&n,&m);
while (x>0&&n&&x/2+10<x){n--;x=x/2+10;}
if (x<=m*10)printf("YES\n");
else printf("NO\n");
}
int main(){
scanf("%d",&t);
while(t--)solve();
return 0;
}
~~~~~
</spoiler>
[problem:1336A]
Idea: [user:EternalAlexander,2020-04-16]
<spoiler summary="Tutorial">
[tutorial:1336A]
</spoiler>
<spoiler...
void dfs(int i, long long x) { if (i == k) { p[__builtin_popcountll(x)]++;
return; } dfs
Tutorial of Codeforces Round 635 (Div. 1)
Tutorial of Codeforces Round 635 (Div. 2)
99.
Efficient 3D Convex Hull Tutorial _Warning: The following contains graphic depictions of geometry, precision errors, and degenerate cases. Viewer discretion is advised._
### Prerequisites
I assume the reader is familiar with:
- 2D Convex Hulls
- 3D Vector Operations (dot and cross products)
### Introduction
Recall that in the 2D convex hull problem, you are given a set of 2D points, and you must compute the smallest convex polygon containing all the given points. By convex, we mean that for any two points $A$ and $B$ inside the polygon, the entire line segment $AB$ is also inside the polygon.
The problem in 3D is completely analogous. You are given $n$ 3D points, and you must compute the smallest convex polyhedron containing all the given points. Similarly, a polyhedron is convex if for any two points $A$ and $B$ inside the polyhedron, the line segment $AB$ is also inside the polyhedron.
In the 2D case, it is more obvious what the output is. We can simply output a circular list of vertices on the ...
is a reference to the F2 edge pointer void glue(face *F1, face *F2, edge* &e1,
edge* &e2) { e1
100.
Educational Codeforces Round 57 Editorial [problem:1096A]
<spoiler summary="Tutorial">
[tutorial:1096A]
</spoiler>
<spoiler summary="Solution (PikMike)">
~~~~~
T = int(input())
for i in range(T):
l, r = map(int, input().split())
print(l, l * 2)
~~~~~
</spoiler>
[problem:1096B]
<spoiler summary="Tutorial">
[tutorial:1096B]
</spoiler>
<spoiler summary="Solution (Vovuh)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
string s;
cin >> n >> s;
int cntl = 0, cntr = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == s[0]) {
++cntl;
} else {
break;
}
}
for (int i = n - 1; i >= 0; --i) {
if (s[i] == s[n - 1]) {
++cntr;
} else {
break;
}
}
if (s[0] == s[n - 1]) {
cout << ((cntl + 1) * 1ll * (cntr + 1)) % 998244353 << endl;
} else {
cout << (cntl + cntr + 1) % 998244353;
}
return 0;
}
~~~~~
</spoiler>
...
inline void solve() { sort(a, a + k);
101.
Codeforces Round 864 (Div. 2) Editorial [problem:1797A]
<spoiler summary="Tutorial">
[tutorial:1797A]
</spoiler>
<spoiler summary="Solution (rui_er)">
```cpp
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
#define y1 y114514
int T, n, m, x1, y1, x2, y2;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
int f(int x, int y) {
if((x == 1 || x == n) && (y == 1 || y == m)) return 2;
if(x == 1 || x == n || y == 1 || y == m) return 3;
return 4;
}
int main() {
for(scanf("%d", &T);T;T--) {
scanf("%d%d%d%d%d%d", &n, &m, &x1, &y1, &x2, &y2);
printf("%d\n", min(f(x1, y1), f(x2, y2)));
}
return 0;
}
```
</spoiler>
[problem:1797B]
<spoiler...
int T, n, k, a[N][N]; template void chkmin(T& x, T y) {if(x > y) x = y;}
template
Tutorial of Codeforces Round 864 (Div. 2)
102.
Educational Codeforces Round 86 Editorial [problem:1342A]
Idea: [user:BledDest,2020-04-27] and [user:adedalic,2020-04-27]
<spoiler summary="Tutorial">
[tutorial:1342A]
</spoiler>
<spoiler summary="Solution (Roms)">
~~~~~
for _ in range(int(input())):
x, y = map(int, input().split())
a, b = map(int, input().split())
b = min(b, a + a)
if x < y:
x, y= y, x
print(y * b + (x - y) * a)
~~~~~
</spoiler>
[problem:1342B]
Idea: [user:adedalic,2020-04-27]
<spoiler summary="Tutorial">
[tutorial:1342B]
</spoiler>
<spoiler summary="Solution (adedalic)">
~~~~~
fun main() {
val T = readLine()!!.toInt()
for (tc in 1..T) {
val t = readLine()!!
val s = t.toCharArray().distinct().joinToString("").repeat(t.length)
println(s)
}
}
~~~~~
</spoiler>
[problem:1342C]
Idea: [user:BledDest,2020-04-27] and [user:adedalic,2020-04-27]
<spoiler summary="Tutorial">
[tutorial:1342C]
</spoiler>
<spoiler summary="Solution (Bled...
void solve() { scanf("%d", &n); forn(i, n) scanf("%d", &a[i]);
103.
Codeforces Round #647 Editorial [problem:1362A]
Author: [user:Anadi, 2020-06-04]
<spoiler summary="Tutorial">
[tutorial:1362A]
</spoiler>
<spoiler summary="Solution">
```
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL getR(LL a){
while(a % 2 == 0)
a /= 2;
return a;
}
void solve(){
LL a, b;
scanf("%lld %lld", &a, &b);
if(a > b) swap(a, b);
LL r = getR(a);
if(getR(b) != r){
puts("-1");
return;
}
int ans = 0;
b /= a;
while(b >= 8)
b /= 8, ++ans;
if(b > 1) ++ans;
printf("%d\n", ans);
}
int main(){
int quest;
scanf("%d", &quest);
while(quest--)
solve();
return 0;
}
```
</spoiler>
[problem:1362B]
Authors: [user:Anadi, 2020-06-04] and [user:Okrut, 2020-06-04]
<spoiler summary="Tutorial">
[tutorial:1362B]
</spoiler>
<spoiler summary="Solution">
```
//O(n * maxA) solution
#include <bits/stdc++.h>
using namespace std;
const int N = 1025;
int n;
int in[N];
bool is[N];
bool ch...
void no_answer(){ puts("-1"); clear(); }, void read(){ map M;
104.
Codeforces Round 916 (Div. 3) Editorial [problem:1914A]
Idea: [user:BledDest,2023-12-20]
<spoiler summary="Tutorial">
[tutorial:1914A]
</spoiler>
<spoiler summary="Solution (awoo)">
~~~~~
for _ in range(int(input())):
n = int(input())
s = input()
print(sum([s.count(chr(ord('A') + i)) >= i + 1 for i in range(26)]))
~~~~~
</spoiler>
[problem:1914B]
Idea: [user:Roms,2023-12-20]
<spoiler summary="Tutorial">
[tutorial:1914B]
</spoiler>
<spoiler summary="Solution (BledDest)">
~~~~~
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int i = 0; i < n; i++) a[i] = n - i;
reverse(a.end() - k - 1, a.end());
for(int i = 0; i < n; i++)
{
if(i) cout << " ";
cout << a[i];
}
cout << endl;
}
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
solve();
return 0;
}
~~~~~
</spoiler>
[problem:1914C]
Idea: [user:Roms,2023-12-20]
<spoiler summary="Tutorial">
[tutorial:1914...
inline void solve() { vector ids(n); iota(ids.begin(), ids.end(), 0);
Tutorial of Codeforces Round 916 (Div. 3)
105.
Codeforces Round 930 (Div. 1, Div. 2) Editorial Thank you for participation and we hope you enjoy this round :)
#### [D2A — Shuffle Party](https://codeforces.me/contest/1937/problem/A)
Idea : [user:chromate00,2023-08-27]
<spoiler summary="Hint (for thinkers)">
If you think in terms of $k$, it might be hard to find the solution. Maybe it will be helpful if you fix $d$ and find the $k$ which will be swapped with $d$.
</spoiler>
<spoiler summary="Hint (for observers)">
Try bruteforcing for, say, $n \le 20$. Do you see a pattern?
</spoiler>
<spoiler summary="Tutorial">
On $n=1$, the answer is trivially $1$.
On $n=2$, index $1$ and $2$ are swapped. The answer is therefore $2$.
For $n>2$, let us assume the element $1$ is on index $a$ and it will be swapped with index $k$. Then, $a$ must be $k/2$. We will prove this by contradiction. Let us assume that there is no divisor greater than $a$, and $a$ is lesser than $k/2$. But then, as $a$ is a multiple of $2$ in the base condition, $k$ must be a multiple of $2...
template void print(vector x){for(auto i: x) cout << i << ' ';cout << "\n
Tutorial of Codeforces Round 930 (Div. 1)
Tutorial of Codeforces Round 930 (Div. 2)
106.
Educational Codeforces Round 137 Editorial [problem:1743A]
Idea: [user:fcspartakm,2022-10-18]
<spoiler summary="Tutorial">
[tutorial:1743A]
</spoiler>
<spoiler summary="Solution 1 (awoo)">
~~~~~
for _ in range(int(input())):
n = int(input())
a = set(map(int, input().split()))
ans = 0
for i in range(10000):
num = str(i)
num = (4 - len(num)) * '0' + num
used = set(num)
if len(used) != 2:
continue
d1 = int(used.pop())
d2 = int(used.pop())
if (not d1 in a) and (not d2 in a) and num.count(num[0]) == 2:
ans += 1
print(ans)
~~~~~
</spoiler>
<spoiler summary="Solution 2 (fcspartakm)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int n;
inline void read() {
cin >> n;
int x;
for (int i = 0; i < n; ++i)
cin >> x;
}
inline int fac(int n) {
int res = 1;
for (int i = 2; i <= n; i++) {
res *= i;
}
return res;
}
inline int c(int n, int k) {
return fac(n) / fac(k) / fac(n - k);
}
inline void sol...
inline void solve() { cout << c(10 - n, 2) * c(4, 2) << endl; }
107.
Educational Codeforces Round 81 Editorial [problem:1295A]
Idea: [user:adedalic,2020-01-30]
<spoiler summary="Tutorial">
[tutorial:1295A]
</spoiler>
<spoiler summary="Solution (BledDest)">
~~~~~
t = int(input())
for i in range(t):
n = int(input())
if(n % 2 == 1):
print(7, end='')
n -= 3
while(n > 0):
print(1, end='')
n -= 2
print()
~~~~~
</spoiler>
[problem:1295B]
Idea: [user:Roms,2020-01-30]
<spoiler summary="Tutorial">
[tutorial:1295B]
</spoiler>
<spoiler summary="Solution (adedalic)">
~~~~~
#include<bits/stdc++.h>
using namespace std;
typedef long long li;
int n, x;
string s;
inline bool read() {
if(!(cin >> n >> x >> s))
return false;
return true;
}
inline void solve() {
int ans = 0;
bool infAns = false;
int cntZeros = (int)count(s.begin(), s.end(), '0');
int total = cntZeros - (n - cntZeros);
int bal = 0;
for(int i = 0; i < n; i++) {
if(total == 0) {
if(bal == x)
infAns = tru...
inline void solve() { int ans = 0; bool infAns = false;
108.
Educational Codeforces Round 62 Editorial [problem:1140A]
<spoiler summary="Tutorial">
[tutorial:1140A]
</spoiler>
<spoiler summary="Solution (adedalic)">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
return true;
}
inline void solve() {
int cnt = 0, pos = 0;
while(pos < n) {
cnt++;
int mx = pos;
while(pos < n && pos <= mx) {
mx = max(mx, a[pos]);
pos++;
}
}
cout << cnt << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
if(read()) {
solve();
}
return 0;
}
~~~~~
</spoiler>
[problem:1140B]
<spoiler summary="Tutorial">
[tutorial:1140B]
</spoiler>
<spoiler summary="Solution (Roms)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int t, n;
string s;
int main(){
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> n >> s;
int res = n - ...
void rollback() { cur--; (*where[cur]) = val[cur]; }
109.
Codeforces Round 965 (Div. 2) Editorial #### [problem:1998A]
Problem Credits: [user:sum,2024-07-03] <br>
Analysis: [user:cry,2024-07-03]
<spoiler summary="Solution ">
We can construct a solution by fixing all $x_i$ as $x_c$ or all $y_i$ as $y_c$. For example, if we fix all $y_i$ as $y_c$, then we can output pairs $(x_c-1, y_c), (x_c+1, y_c), (x_c-2, y_c), (x_c+2, y_c), ... , (x_c- \lfloor \frac{k}{2} \rfloor, y_c), (x_c + \lfloor \frac{k}{2} \rfloor, y_c)$. If the $k$ is odd, we need one more pair, so just output $(x_c, y_c)$.
</spoiler>
<spoiler summary="Code (C++)">
```cpp
#include <iostream>
using namespace std;
int main() {
int t; cin >> t;
while(t--){
int x, y, k; cin >> x >> y >> k;
for(int i = 0; i < k - k % 2; i++){
cout << x - (i & 1 ? 1 : -1) * (i / 2 + 1) << " " << y << "\n";
}
if(k & 1){
cout << x << " " << y << "\n";
}
}
}
```
</spoiler>
#### [problem:1998B]
Problem Credits: [user:satyam343,2024-08-07] <br>
Analysis: [user:cry,2024-07-03]
<spoiler summ...
void solve(){ cin >> n >> x;
Tutorial of Codeforces Round 965 (Div. 2)
110.
Educational Codeforces Round 130 Editorial [problem:1697A]
Idea: [user:vovuh,2022-06-13]
<spoiler summary="Tutorial">
[tutorial:1697A]
</spoiler>
<spoiler summary="Solution (vovuh)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", H"r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int tc;
cin >> tc;
while (tc--) {
int n, m;
cin >> n >> m;
int sum = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
sum += x;
}
cout << max(0, sum - m) << endl;
}
return 0;
}
~~~~~
</spoiler>
[problem:1697B]
Idea: [user:BledDest,2022-06-13]
<spoiler summary="Tutorial">
[tutorial:1697B]
</spoiler>
<spoiler summary="Solution (Neon)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, q;
cin >> n >> q;
vector<long long> p(n), s(n + 1...
void must(int x){ either(x, x); }
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/11/2026 06:05:04 (k1).
Desktop version, switch to mobile version.
Supported by
