OR Convolution for Common People Several years ago, a wise person told me that a convolution on a bitwise operator is possible: Given $A, B$ of size $2^N$, you can compute $C[i] = \sum_{j \oplus k = i} A[j] B[k]$ $C[i] = \sum_{j \land k = i} A[j] B[k]$ $C[i] = \sum_{j \lor k = i} A[j] B[k]$ in $O(2^N N)$ time. Cool! I asked a wise person, how such things are possible. A wise person replied, _"Of course you know how FFT works, let's begin with Fast Welsh-Hadamard Transform..."_ I said, No. I don't know how FFT works. Thank you. Then I just threw it into my ICPC teamnote. Years have passed, I still don't know how FFT works, and while writing some stupid essay, a random idea came to my mind. I wondered, "Does nobody really know this? Why anyone didn't explain OR convolution this way?". I searched on Google, and nobody was telling things this way, so this is certainly not a common explanation. But why? It should be. Let me use my time to change things for good. ## Sum of Subsets For convenience, I'll...

Полный текст и комментарии »

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$ ...

Полный текст и комментарии »

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...

Полный текст и комментарии »

Problem Topics Good Day to you! I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now &mdash; so here it is: <spoiler summary="aho"> http://www.spoj.com/problems/ADAJOBS/ URI 2226 (5) //[NICE][NUMBERS][DP] http://www.spoj.com/problems/SUB_PROB/en/ http://codeforces.me/contest/696/problem/D 8 http://www.spoj.com/problems/AHOCUR/ 5 //Aho-Corassic + DP https://www.codechef.com/problems/LYRC (5) //Sample aho-brute-force http://codeforces.me/problemset/problem/346/B //Proposed by [user:bradyawn,2019-08-03] </spoiler> <spoiler summary="automat"> 6861 [LA] //CYK UVA 10679 //Suffix Automat http://www.spoj.com/problems/STRMATCH/ //Suffix Automat &mdash; trie might do too http://www.spoj.com/problems/NSUBST...

Полный текст и комментарии »

Essentials of Elementary Number Theory This is a blog starting from the very basics of number theory, in a way that flows fluidly from one concept to another and is based in developing an intuitive feeling for the basics of elementary number theory. This is not a blog to simply gloss over. I consider more of a guided exploration into the world of discovering things in the world of number theory, and I don't expect anyone to immediately understand all the insights in this blog. But if you put an honest effort into discovering how I find these insights you will find much use for my blog. If you do not know some notation or some elementary theorem I use you should refer to this. <spoiler summary="Elementary definitions"> We start with the basic definition that is at the heart of number theory. Let $a \mid b$ (read a divide(s) b) for some $a,b \in \mathbb{Z}$ for some if there exists $k \in \mathbb{Z}$ such that $b = ak$. Similarly $a \not\mid b$ if there does not exist such $k$. If $g \mid a$, then $g \mid ab$. ...

Полный текст и комментарии »

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...

Полный текст и комментарии »

Linear Basis (Xor Basis Extended) As part of the graduation requirements for my school, I have to complete a simple research project, so I decided to do something related to data structure and algorithms. I believe I have come out with a data structure that maintains the basis of vectors in $(\mathbb{Z}/m\mathbb{Z})^d$, where $m$ **may not be prime**. Since this was related to competitive programming, I think it is a good idea to share it here. Hopefully, this algorithm is actually novel :P I would like to thank: - [user:icypiggy,2021-12-26] for being my research mentor and tolerating my dumb questions - [user:rama_pang,2021-12-26] and [user:adamant,2021-12-28] for their helpful suggestions and comments Please comment under the blog or message me on codeforces if any parts are unclear or wrong. Also, I hope that some LGMs can help solve the open problems in this blog. # Introduction Maintaining the basis of vectors in $(\mathbb{Z}/2 \mathbb{Z})^d$, also known as the xor basis algorithm is a well-studie...

Полный текст и комментарии »

How to Solve Questions [Dominater Version] Recently, I got a request asking me to write down my thought process while solving questions. So, here is the promised blog. I would like to thank [user:Iceknight1093,2024-08-30], [user:qwexd,2024-08-30], [user:Sana,2024-08-30], [user:Everule,2024-08-30] and [user:NovusStellachan,2024-08-30] for proof reading and suggesting edits in the blog. Special thanks to [user:satyam343,2024-08-30] for discussing most of the blog with me. <h3> 1. Overview </h3> The blog contains my solutions to $7$ problems in a wide range of ratings, starting from $1200$ all the way upto $2700$. Each problem has a step-by-step solution and you can notice how there are no large jumps in logic, but everything comes naturally. I do not claim that this is always possible in each problem, however I solve majority of CF problems in such a manner. There are certainly other high rated people who will have completely different methods of solving. However, this is about what works for me. There are some meta ...

Полный текст и комментарии »

Editorial of Codeforces Round 860 (Div. 2) Thank you all for participating, I hope you enjoyed the problems! You can rate the problems of the round in the corresponding spoilers. [problem:1798A]<br> <div class="spoiler"> <b class="spoiler-title">Hint 1</b> <div class="spoiler-content" style="display: none;"> For each index $i$, it makes no sense to perform the operation $\ge 2$ once, since applying the operation with the same index twice does not change anything. </div></div> <div class="spoiler"> <b class="spoiler-title">Hint 2</b> <div class="spoiler-content" style="display: none;"> Condition $a_n = \max(a_1, a_2, \ldots, a_n)$ is equivalent to $a_i \leq a_n$ for all $i$. So for each index $i$ there are only 2 conditions: $a_i \leq a_n$ and $b_i \leq b_n$. </div></div> <div class="spoiler"> <b class="spoiler-title">Tutorial</b> <div class="spoiler-content" style="display: none;"> [tutorial:1798A]</div></div> <spoiler summary="Solution"> ``` for _ in range(int(input())): n = int(input()) a = li...

Полный текст и комментарии »

Implicit Prime Factorisation Those of us who have been doing cp for a long time, have come to love the representation of numbers as an infinite prime power vector i.e. $$n = \prod p_i^{e_i} = [e_1, e_2, \ldots ] = v_n$$ Where $n$ is a number and $p_i$ is the $i$ th prime number. This has many useful properties for problems, such as mapping $$n \times m \sim v_n + v_m$$ $$n / m \sim v_n - v_m$$ $$n \mid m \sim v_n \le v_m$$ $$\gcd(n, m) \sim \min(v_n, v_m)$$ $$lcm(n, m) \sim \max(v_n, v_m)$$ All the above operations are done elementwise. However in some cases, the problem authors may forbid you from factorising the numbers, by perhaps increasing $n$ to around $10^{36}$ where there isn't any simple factorisation algorithm to do it in reasonable time. However using effective prime factorisation, we can use these properties freely on a set of numbers. If this set contained all integers, then it would require us to truly prime factorise the integer. However, we only need to use these operations on a subset...

Полный текст и комментарии »

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...

Полный текст и комментарии »

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> ...

Полный текст и комментарии »

Tutorial of Codeforces Round 729 (Div.2) <spoiler summary="A Tutorial"> The answer is 'yes' if and only if there are exactly $n$ odd numbers. </spoiler> <spoiler summary="A Code"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--){ int n,cnt[2]={0}; cin>>n; for(int i=1,x;i<=n*2;i++)cin>>x,cnt[x%2]++; if(cnt[0]==n)puts("Yes"); else puts("No"); } return 0; } ~~~~~ </spoiler> <spoiler summary="B Hint 1"> What kind of element in the set is important? </spoiler> <spoiler summary="B Hint 2"> If $x$ is in the set, but $x-b$ is not, $x$ is important. Why? </spoiler> <spoiler summary="B Hint 3"> How can we find all important elements? </spoiler> <spoiler summary="B Tutorial"> First check specially if $b=1$. Let's consider when $n$ is in $S$. The answer is when the smallest number $m$ in $S$ that $n\ \mathrm{mod}\ b=m\ \mathrm{mod}\ b$ is less than $n$. It's easy to see that a new case of $x\ \mathrm{mod}\ b$ can only appear wh...

Полный текст и комментарии »

Educational Codeforces Round 188 Editorial [problem:2204A] Idea: [user:BledDest,2026-03-17] <spoiler summary="Tutorial"> [tutorial:2204A] </spoiler> <spoiler summary="Solution (BledDest)"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; for(int i = 0; i < t; i++) { int n; cin >> n; string s; cin >> s; cout << s.find("RL") + 2 << endl; } return 0; } ~~~~~ </spoiler> [problem:2204B] Idea: [user:fcspartakm,2026-03-17] <spoiler summary="Tutorial"> [tutorial:2204B] </spoiler> <spoiler summary="Solution (BledDest)"> ~~~~~ #include<bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i]; int mx = 0; int ans = 0; for(int i = 0; i < n; i++) { if(a[i] >= mx) ans++; mx = max(mx, a[i]); } cout << ans << "\n"; } int main() { ...

Полный текст и комментарии »

Convolution, In the Perspective of 3-Dimensional Tensors Hello everyone! Convolution is perhaps the first class of algorithms that one encounters in competitive programming requiring algebraic knowledge. There are many types of convolutions that we are interested in, including: - **Sequential convolution** (i.e., polynomial multiplication), - **XOR convolution**, - **AND/OR convolution**, - **GCD/LCM convolution**, - **Subset convolution**, and others. One of the most well-known ways to understand fast algorithms for these convolutions is through their associated algebraic structures. These algebraic structures can often be decomposed using the Chinese Remainder Theorem (CRT) into simpler components, i.e., direct products. For instance, in the case of XOR convolution, the algebraic structure arises from the computation rules of the group algebra: $$ R[\mathbb Z_2^n]\colon \left(\sum_{g\in \mathbb Z_2^n} a_g g\right) \left(\sum_{g\in \mathbb Z_2^n} b_g g\right) = \left(\sum_{g,h\in \mathbb Z_2^n} a_g b_h (g+h) \right), $$...

Полный текст и комментарии »

Möbius function, Möbius inversion explaination from a combinatorics perspective When I first learn Möbius function, all the resources I found just explain everything algebraically (e.g. substitute $[\gcd = 1]$ using the identity $\sum\limits_{d | \gcd}\mu(d) = [\gcd = 1]$ when solving certain kind of gcd counting problem, then start to do a bunch of algebra and boom! the problem is solved, and I don't know why it works lol) which is not very motivated in my opinion. But after rethinking about it after solving [this problem](https://codeforces.me/problemset/problem/2045/K), I think I can shed some light on the motivation behind Möbius function, from a combinatorics perspective. #### Definition of Möbius function $$\mu(n) = \begin{cases}(-1)^c & \text{ if } n \text{ is square-free and } n \text { have } c \text{ different prime divisors}\\ 0 & \text{ if } n \text{ is not square-free}\end{cases}$$ What a weird function? Why do we want to define something based on number of prime divisors and why do we want to let everything not square-free to be zero? Yo...

Полный текст и комментарии »

Первоапрельский контест 2016: разбор задач В этом году 3 человека решили все задачи, что ровно на 3 больше, чем в 2014! А вот участников, решивших хотя бы одну задачу, было всего 1097. #### [problem:656A] В этой задаче надо было определить последовательность целых чисел по двум примерам и названию задачи. Это оказалось неожиданно сложно, гораздо сложнее, чем мне казалось. Поиск по OEIS показывает, что хотя последовательностей, содержащих числа из примеров, довольно много, ровно одна из них имеет отношение к Леонардо да Винчи (а если сразу искать "Da Vinci", последовательностей находится всего две). http://oeis.org/A221180 &mdash; последовательность степеней двойки, вычисленная да Винчи с ошибкой и записанная в "Codex Madrid I". #### [problem:656B] Одно слово: [typoglycemia](https://en.wikipedia.org/wiki/Typoglycemia). [cut] Существует миф (не подтвержденный никаким известным исследованием) о том, что люди легко читают текст даже с перемешанными буквами, если первая и последняя буквы слов остатся на своих места...

Полный текст и комментарии »

Educational Codeforces Round 183 Editorial [problem:2145A] Idea: [user:fcspartakm,2025-10-07] <spoiler summary="Tutorial"> [tutorial:2145A] </spoiler> <spoiler summary="Solution (fcspartakm)"> ~~~~~ #include <iostream> using namespace std; int main() { int t; cin >> t; for(int i = 0; i < t; i++) { int n; cin >> n; cout << (3 - n % 3) % 3 << endl; } } ~~~~~ </spoiler> [problem:2145B] Idea: [user:BledDest,2025-10-07] <spoiler summary="Tutorial"> [tutorial:2145B] </spoiler> <spoiler summary="Solution (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n, k; string s; cin >> n >> k >> s; int a = count(s.begin(), s.end(), '0'); int b = count(s.begin(), s.end(), '1'); int c = count(s.begin(), s.end(), '2'); string ans(n, '+'); for (int i = 0; i < n; ++i) { if (i < a + c || i >= n - b - c) ans[i] = '?'; if (i < a...

Полный текст и комментарии »

Editorial of Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) [problem:1654A] Author: [user:TheScrasse,2022-02-24]<br> Preparation: [user:TheScrasse,2022-02-19] <spoiler summary="Hint 1"> Suppose you want to choose pieces of cake $i$, $j$. Can you make them adjacent in $1$ move? </spoiler> <spoiler summary="Solution"> The answer is the sum of the $2$ maximum weights. You can always pick the $2$ maximum weights: if they are $a_i$ and $a_j$ ($i < j$), you can flip the subsegment $[i, j-1]$ to make them adjacent. The result can't be larger, because the sum of the weights of any $2$ pieces of cake is never greater than the sum of the $2$ maximum weights. Iterating over all pairs of pieces of cake is enough to get AC, but you can solve the problem in $O(n \log n)$ by sorting the weights and printing the sum of the last $2$ values, or even in $O(n)$ if you calculate the maximum and the second maximum in linear time. Complexity: $O(t \cdot n^2)$, $O(t \cdot n \log n)$ or $O(t \cdot n)$ </spoiler> Official solution: [submissi...

Полный текст и комментарии »

[Tutorial] Inclusion-Exclusion Principle Hello, Codeforces! The reason why I am writing this blog is that my ACM/ICPC teammate [user:calabash_boy_love_15,2019-01-18] is learning this technique recently(he is a master in string algorithms,btw), and he wanted me to provide some useful resources on this topic. I found that although many claim that they do know this topic well, problems concerning inclusion-exclusion principle are sometimes quite tricky and not that easy to deal with. Also, after some few investigations, the so-called "Inclusion-Exclusion principle" some people claim that they know wasn't the generalized one, and has little use when solving problems. So, what I am going to pose here, is somewhat the "Generalized Inclusion-Exclusion Principle". Most of the describing text are from the graduate text book _Graduate Text in Mathematics 238, A Course in Enumeration_, and the problems are those that I encountered in real problem set, so if possible, I'll add a link to the real problem so that you can solve it by yours...

Полный текст и комментарии »

Introduce my masterpieces of math problem I sometimes make problems and post them in Japanese local contest [yukicoder](https://yukicoder.me/). I want many people to know math problems I made, so I introduce some of them. Let's try!! [LCMST](https://yukicoder.me/problems/no/1917) ------------------ #### Problem Statement Consider a complete graph $G$ on $N$ vertices. The weight of edge between vertex $i$ and $j$ is least common multiple of $A_i$ and $A_j$. Find the total weight of the edges contained in a minimum spanning tree of $G$. #### Constraints - $2\leq N \leq 10^6$ - $1\leq A_i\leq 10^5$ - Time Limit is 4000ms #### Sample Consider the case where $N=3$ and $A=(2,3,4)$. The answer is $10$. This is optimal to draw edges between $(1,2),(1,3)$. These have weights $\mathrm{lcm}(A_1,A_2)=\mathrm{lcm}(2,3)=6, \mathrm{lcm}(A_1,A_3)=\mathrm{lcm}(2,4)=4$, respectively. #### Hints <spoiler summary="Hint1"> If $A_i=A_j$, draw a edge between $(i,j)$. So you need only consider the case $A$ is distinct. </spo...

Полный текст и комментарии »

[Tutorial] Math note — Möbius inversion If you've ever taken some lessons on competitive programming, chances are that you have already heard about one of the most famous formula: the Möbius inversion. This article is aimed to provide some basic insight on what is the Möbius inversion, as well as how to apply it in various programming tasks. Prequisite ================== If you are not familiar with the linear sieve and multiplicative functions, it is recommended that you read about them first [here](http://codeforces.me/blog/entry/54090). I will introduce some frequently used notations and lemmas first. Notation ------------------ 1. $[P]$ refers to the boolean expression, i.e. $[P]=1$ when $P$ is true, and $0$ otherwise. 2. $\lfloor x \rfloor$ refers to rounding $x$ down to the nearest integer. Thus $\lfloor \frac{q}{p} \rfloor$ refers to the integer division. 3. $d|n$ means that d can divide n (without a remainder). The following functions are all multiplicative functions, where $p$ is a prime numbe...

Полный текст и комментарии »

Codeforces Round #948 (Div. 2) Editorial We hope you enjoyed the problems. Problem [problem:1977A] was created by [user:Stefan2417,2024-05-27] and prepared by [user:alexchist,2024-05-27]. Problem [problem:1977B] was created by [user:alexchist,2024-05-27] and prepared by [user:Stefan2417,2024-05-27]. Problem [problem:1977C] was created and prepared by [user:Stefan2417,2024-05-27]. Problem [problem:1977D] was created and prepared by [user:alexchist,2024-05-27]. Problem [problem:1977E] was created and prepared by [user:Stefan2417,2024-05-27]. [problem:1977A] <spoiler summary="Tutorial"> Note that one action with the cube changes the parity of the number of cubes in the tower. Therefore, if the parities of $n$ and $m$ do not match, it is impossible to build the tower. Also, if $n < m$, the tower cannot be built either. In all other cases, it is possible to build a tower of height $m$ in $m$ operations, and then add and remove a cube until the operations are exhausted. </spoiler> <spoiler summary="Author...

Полный текст и комментарии »

CSES Additional Problems I (new problems only) Tutorial Hello Codeforces. I was stuck on a 3 hour flight with nothing to do, so what better way to spend my time than catching up on the new CSES problems. But it turns out I finished those too quick so I guess I'm writing the solutions for some of them here. No one probably asked. This will only cover the new problems from the 2025 update and in the **Additional Problems I** section. For old problem solutions you can probably find them somewhere on the internet. For new problems not in this section, some of their solutions are in [this blog](https://codeforces.me/blog/entry/142894). ### [Distinct Values Sum](https://cses.fi/problemset/task/3150/) <spoiler summary="Smash Me"> Consider each distinct value separately. Say we are focused on $x$ and denote the indices where $x$ occurs in $a$ as $b_1, b_2, \ldots, b_k$. We want to count the number of subarrays that covers at least one element in $b$. Let's break $[1, n]$ into intervals separated by each $b_i$, so we have intervals $[...

Полный текст и комментарии »

[Tutorial] Number theory — Storing information about multiples/divisors Hello everyone,<br> here is a very simple idea that can be useful for (cp) number theory problems, especially those concerning multiples, divisors, $\text{GCD}$ and $\text{LCM}$. Prerequisites: basic knowledge of number theory (divisibility, $\text{GCD}$ and $\text{LCM}$ properties, prime sieve). Idea ------------------ Let's start from a simple problem. _You are given $n$ pairs of positive integers $(a_i, b_i)$. Let $m$ be the maximum $a_i$. For each $k$, let $f(k)$ be the sum of the $b_i$ such that $k | a_i$. Output all pairs $(k, f(k))$ such that $f(k) > 0$._ An obvious preprocessing is to calculate, for each $k$, the sum of the $b_i$ such that $a_i = k$ (let's denote it as $g(k)$). Then, there are at least $3$ solutions to the problem. #### Solution 1: $O(m\log m)$ For each $k$, $f(k) = \sum_{i=1}^{\lfloor m/k \rfloor} g(ik)$. The complexity is $O\left(m\left(\frac{1}{1} + \frac{1}{2} + \dots + \frac{1}{m}\right)\right) = O(m\log m)$. #### Solution 2: $O(n\sq...

Полный текст и комментарии »

Codeforces Round #360 Editorial [+ Challenges!] Hi again! If you notice typos or errors, please send a private message. ### [688A: Opponents](http://codeforces.me/contest/688/problem/A) #### Solution Let's find out for each row of the given matrix if it is completely consisting of _ones_ or not. Make another array $canWin$, and set $canWin_i$ equal to one if the $i$-th row consists at least one _zero_. Then the problem is to find the maximum subsegment of $canWin$ array, consisting only ones. It can be solved by finding for each element of $canWin$, the closest zero to it from left. The complexity of this solution is $O(nd)$, but the limits allow you to solve the problem in $O(nd^2)$ by iterating over all possible subsegments and check if each one of them is full of _ones_ or not. <spoiler summary="C++ code"> ~~~~~ // . .. ... .... ..... be name khoda ..... .... ... .. . \\ #include <bits/stdc++.h> using namespace std; inline int in() { int x; scanf("%d", &x); return x; } const int N = 202; int ...

Полный текст и комментарии »

On Div2ABs 2 years ago, [user:antontrygubO_o,2022-04-27] wrote [a blog](https://codeforces.me/blog/entry/75163) about div2ABs where he expressed his opinions that d2ABs should not be about "here is a statement, please implement what is written there". Thanks to him, the quality of d2ABs (and problem quality in general) have certainly improved. However, I still believe that there still quite large differences between how coordinators/problemsetters view d2ABs and how the intended participants view them. From the survey made by [user:kpw29,2022-04-27], we can see that most people agree that most people agree that we should **primarily** consider the target audience when proposing a task. I too think if a task is boring to div 1 contestants, we should not think of that as a reason to immediately disqualify a problem from being a d2A.  I think when people judge the interesting-ness of d2As, they try...

Полный текст и комментарии »

Editorial of Codeforces Round #701 (Div. 2) [problem:1485A] Author: [user:TheScrasse,2021-02-07]<br> Preparation: [user:MyK_00L,2021-02-07] <spoiler summary="Hint 1"> Suppose that you can use $x$ operations of type $1$ and $y$ operations of type $2$. Try to reorder the operations in such a way that $a$ becomes the minimum possible. </spoiler> <spoiler summary="Hint 2"> You should use operations of type $2$ first, then moves of type $1$. How many operations do you need in the worst case? ($a = 10^9$, $b = 1$) </spoiler> <spoiler summary="Hint 3"> You need at most $30$ operations. Iterate over the number of operations of type $2$. </spoiler> <spoiler summary="Solution"> Notice how it is never better to increase $b$ after dividing ($\lfloor \frac{a}{b+1} \rfloor \le \lfloor \frac{a}{b} \rfloor$). So we can try to increase $b$ to a certain value and then divide $a$ by $b$ until it is $0$. Being careful as not to do this with $b<2$, the number of times we divide is going to be $O(\log a)$. In particular, i...

Полный текст и комментарии »

Hello 2026 Editorial We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated! <spoiler summary="Rate The Contest!"> - Great contest - Good contest - Average contest - Bad contest </spoiler> ## [2183A &mdash; Binary Array Game](https://codeforces.me/contest/2183/problem/A) Idea & Preparation: [user:wangmarui,2025-12-23] <spoiler summary="Rate The Problem!"> - Good Problem - Okay Problem - Bad Problem - Didn't Solve </spoiler> <spoiler summary="Hint 1"> If the sequence $a$ consists entirely of $1$ s, what will Alice do? </spoiler> <spoiler summary="Hint 2"> Consider discussing the values of $a_1$ and $a_n$. </spoiler> <spoiler summary="Solution"> First, if the entire sequence consists of $1$ s, Alice wins immediately by operating on the whole sequen...

Полный текст и комментарии »

Codeforces Round 1106 Discussion Stream (with Hints) The editorial video for [contest:2238] is now available [here](https://youtu.be/ZJeKaVFtOuE). Do check out the [CF Video Editorial Finder](https://codeforces.me/blog/entry/154724) browser extension. [problem:2238A] <spoiler summary="Hint 1"> Do we really need to reorder more than once? </spoiler> <spoiler summary="Hint 2"> Any subtraction done after a reorder could have been done before it instead.<br> So optimal strategy is: subtract some elements, then reorder at most once. </spoiler> <spoiler summary="Hint 3"> Compute cost without reordering — check if $a_i \geq b_i$ for all $i$. Cost = $\sum (a_i - b_i)$. </spoiler> <spoiler summary="Hint 4"> Compute cost with reordering — sort both arrays. Pair largest $a_i$ with largest $b_i$, and so on.<br> Check feasibility. Cost = $c + \sum (a_i - b_i)$.<br> <br> Why this pairing? If the largest $b_i$ is 20, at least one $a_i$ must be $\geq 20$. If the second largest is 10, at least two $a_i$ must be $\geq 10$, ...

Полный текст и комментарии »

Codeforces Round #781 (Div. 2) Editorial Again, I hope that you liked all the problems. Share your ideas and solutions in the comments, because there are always different ones! So, the editorial: <spoiler summary="A: GCD vs LCM"> [problem:1665A] <spoiler summary="Editorial"> In this problem it is enough to print $n - 3$, $1$, $1$, $1$. It is easy to see that this answer is correct for any $n \ge 4$. </spoiler> <spoiler summary="Implementation (C++, shishyando)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int T; cin >> T; while (T --> 0) { int n; cin >> n; cout << n - 3 << ' ' << 1 << ' ' << 1 << ' ' << 1 << '\n'; } return 0; } ~~~~~ </spoiler> </spoiler> <spoiler summary="B: Array Cloning Technique"> [problem:1665B] <spoiler summary="Editorial"> We will use a greedy technique. Let's find the most common element in the array. Let it be $x$ and let it occur $k$ times in the array. Then let's make a copy where all elements...

Полный текст и комментарии »

Very detailed (text+video) editorial for Codeforces Round 1103 The full editorial video for [contest:2236] is [now available here](https://youtu.be/Y91ChDX4apQ) &mdash; over 3 hours of problem discussions and solutions. Enjoy! I'll update this blog later with submission links and video timestamps. For now, I'm exhausted after finishing this video editorial. Problems are discussed in the following order: A → B → C → D → E → F1 → F2 → G. --- [problem:2236A] <spoiler summary="Hint 1"> What is the smallest possible final height that all towers can reach? </spoiler> <spoiler summary="Hint 2"> Remember that every tower must receive a strictly positive increment. </spoiler> <spoiler summary="Hint 3"> If the tallest tower has height mx, can the final height be mx? </spoiler> <spoiler summary="Hint 4"> Try making every tower equal to mx+1. </spoiler> <spoiler summary="Hint 5"> For a tower of height h[i], how much do we need to add? </spoiler> <spoiler summary="Hint 6"> The answer is determined by the tower requiri...

Полный текст и комментарии »

[Tutorial] Chinese Remainder Theorem **#IjustWantContribution** Hello Codeforces. In this post, I would like to introduce some of you to a very popular, yet maybe not fully understood technique called Chinese Remainder Theorem (CRT). I have seen many articles that present CRT in a way that lacks practical competitive programming approach (no info about how to handle overflows, how to implement it effectively, what to do when modulos are not coprime etc.) and derivation of the formulas seem like some sort of guesswork. The purpose of this article is to address this issue. **Problem and solution** You are given two pairs (main goal is to solve it for $t$ pairs) of integers $(a_1, n_1)$, $(a_2, n_2)$. **There is no assumption that $n_1$ and $n_2$ are coprime**. Find an integer $x$ that satisfies $$ \left\{ \begin{array}{c} x \equiv a_1 \pmod {n_1} \\ x \equiv a_2 \pmod {n_2} \end{array} \right. $$ This system of congruences implies that $$ \left\{ \begin{array}{c} x = a_1 + n_1k_1 \\ x = a_2 + n_2k_...

Полный текст и комментарии »

Educational Round 102 A-E Editorial and Thoughts [My solutions on GitHub](https://github.com/Sky-Nik/Codeforces/tree/main/edu-102) ### A. Replacing Elements The minimum value that an element can get is the sum of the two smallest elements of the initial array. Constraints allowed to find such pair in $O(n^2)$ by brute force. One can also sort the array in $O(n \log n)$ and take `a[0] + a[1]`. However, the optimal method to select $k$ min elements is, of course, a heap with a size limit of $k$ elements which performs this job in $O(n \log k)$. We then change every element to this value if such a change reduces it, and compare against the limit. ### B. String LCM We have to print the lcm anyways, so we can just generate it by looping over two string simultaneously with a pair of indices. If lcm exists then its length is the lcm of lengths of the two strings, hence it is relatively short. If we encounter a pair of different symbols while iterating then lcm does not exist and we print -1. ### C. No More Inversions If yo...

Полный текст и комментарии »

1st Hunger Games Small Editorial — Hints Here's the first part of Hunger Games Editorial prepared by community. There are only my hints, see also the second blog, which will be soon published, with different, more detailed solutions written by many people :) I'd like to thank problemsetters team ([user:PrinceOfPersia,2015-08-26], [user:keyvankhademi,2015-08-26] and [user:AliA,2015-08-26]) for such wonderful contest. Hints will be probably updated when I'll learn more beautiful solutions for these problems :) Enjoy! **Problem A: Good Numbers** Suppose first integer is multiplied A times and second &mdash; B times. How many ways are there to complete the big number? Did we count something more than once? **Problem B: Hamro and array** Try to count numbers on even and odd positions separately. **Problem C: Hamro and Vampire Diaries** Suppose A[1] = x. How do we calculate A[1 + 3]? How to calculate next and all other values of A? What happens if n mod 3 = 0? **Problem D: Hamro and tools** Read abo...

Полный текст и комментарии »

Сodeforces Round 512 (and Technocup — Elimination Round 1) Editorial [problem:1030A] <spoiler summary="Tutorial"> [tutorial:1030A] </spoiler> <spoiler summary="Solution"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; int curMax = 0; for(int i = 0; i < n; i++) { int curAns; cin >> curAns; curMax = max(curMax, curAns); } puts(curMax > 0 ? "HARD" : "EASY"); return 0; } ~~~~~ </spoiler> [problem:1030B] <spoiler summary="Tutorial"> [tutorial:1030B] </spoiler> <spoiler summary="Solution"> ~~~~~ #include<bits/stdc++.h> using namespace std; int n, d; int m; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> d; cin >> m; for(int i = 0; i < m; ++i){ int x, y; cin >> x >> y; bool ok = true; if(!((x - y) <= d && (x - y) >= -d)) ok = false; if(!((x + y) <= n + n - d && (x + y) >= d)) ok = false; if(ok) puts("YES"); else puts("NO"); } return 0; } ~~~~~ </spoiler> [problem:...

Полный текст и комментарии »

Hello 2015 Editorial ### Div.2 A &mdash; [Cursed Query](/gym/100571/problem/A) You should make a sequence $s_1,s_2,...,s_n$ such that $s_i = a_1 + a_2 + ... + a_i$ and use a binary search to find the first element that is greater than $t$ % $s_n$ (or `upper_bound` function in C++ ). Source code : [Here](http://paste.ubuntu.com/9710602/) ### Div.2 B &mdash; [Troynacci Query](/gym/100571/problem/B) First of all, compute sequence $f$ (0-based), then consider we have a sequence $p$ (also 0-based) (partial sum), initially all members are $0$. For each query, if $l < r$, then do : ~~~~~ p[l] = (p[l] + f[0]) % mod; p[l+1] = (p[l+1] + f[1]) % mod; p[l+1] = (1LL * p[l+1] + mod - 1LL * ((1LL * b * f[0]) % mod)) % mod; p[r + 1] = (1LL * p[r+1] + mod - f[r - l + 1]) % mod; p[r + 2] = (1LL * p[r+2] + mod - 1LL * ((1LL * a * f[r-l]) % mod)) % mod; ~~~~~ otherwise, do this : ~~~~~ p[l] = (p[l] + f[0])%mod; p[r+1] = (1LL * p[r+1] + mod - ((1LL * b * f[0])%mod))%mod...

Полный текст и комментарии »

Editorial of Codeforces Round 963 (Div. 2) [problem:1993A] <spoiler summary="Hint"> What is the pattern of Tim's answer sheet that can give him maximum score? </spoiler> <spoiler summary="Solution"> Let's say there are $n$ problems take $A$ as the answer, therefore he can only get $n$ points with the answer $A$. The same is correct for $B$, $C$ and $D$. Therefore, the maximum score can be achieved is $min(n, A) + min(n, B) + min(n, C) + min(n, D)$. Time complexity: $O(4n)$ </spoiler> <spoiler summary="Code (python)"> ~~~~~ t = int(input()) for _ in range(t): n = int(input()) s = input() print(sum(min(n, s.count(c)) for c in "ABCD")) ~~~~~ </spoiler> [problem:1993B] <spoiler summary="Hint 1"> Find a way to make all the elements even. Then odd. </spoiler> <spoiler summary="Hint 2"> In the worst case, the number of operations required is the number of even elements + 1. Why? </spoiler> <spoiler summary="Solution"> First, if all elements already have the same parity, we don'...

Полный текст и комментарии »

Codeforces Round #196 — Разбор задач [problem:337A] -------------- В первую очередь, упорядочим числа `f[i]` по возрастанию. Теперь допустим, что самый маленький пазл, который приобретет учительница, состоит из `f[k]` фрагментов. Понятно, что в таком случае для минимизации разницы она должна приобрести наименьшие `n` пазлов, равных или превосходящих `f[k]` по размеру, то есть пазлы размеров `f[k], f[k+1], ..., f[k+n-1]` (это не совсем правильно, если среди `f[i]` встречаются повторяющиеся числа и выполняется `f[k]=f[k-1]`, но такие случаи можно не рассматривать). Разница между наибольшим и наименьшим количествами фрагментов в таком наборе равняется `f[k+n-1]-f[k]`. Чтобы выбрать оптимальное `f[k]`, переберем значение `k` от 1 до `m-n` и выберем наименьшую возможную разницу. Таким образом, весь алгоритм выглядит следующим образом: ~~~~~ read(n, m, f[1..m]) sort(f[1..m]) best = INFINITY for k = 1 to m-n best = min(best, f[k+n-1] - f[k]) print best ~~~~~ [cut] - [problem:337B] --------- До...

Полный текст и комментарии »

1st Hunger Games Large Editorial — Community solutions This is the second part of Hunger Games Editorial, hope you'll enjoy it :) And again, thanks for stuff for awesome contest, congratz for survivors too! **UPD**: Problems B, D, E, Q, T, W are now available, more soon :) **Editorial Hall of Fame:** [user:Stonefeang,2015-08-26] [user:Andres_Unt,2015-08-26] [user:cuber2460,2015-08-26] [user:Anonym_KALEP,2015-08-26] [user:adamant,2015-08-26] [user:ngoisao_93,2015-08-27] [user:gendelpiekel,2015-08-27] [user:fcdkbear,2015-08-27] [user:izrak,2015-08-27] **Problem A: Good Numbers.** Tutorial by: [user:ngoisao_93,2015-08-28] Call `LCM(i, j)` the lowest common multiple of i and j. First, we should analyse that if x is divisible by `LCM(p^i, q^j)`, then x is divisible by `p^i` and `q^j` at the same time. Call set `s(i, j)` the set of number x in range [l, r] that x is divisible by `LCM(p^i, q^j)`. Call `|s(i, j)|` the size of s(i, j). We can find out that: `|s(i, j)| = |s(1, j)| - |s(1, i-1)| = r/LCM(p^i, q^j...

Полный текст и комментарии »

My ultra-short problemset which can be read in 60s (Last updated time:$2023/8/31,14$ problems) Hi guys,here I'd like to share some of my problems(will continue to be updated, depending on your feedback). All the problems are created by myself. They contain my aesthetic of problems: the neater,the better. Interest and educational significance are also important. You can find the editorial for all the problems in the link,so I will only write down some interesting points under the statement. Let's go :) #### [1.Increasing and Decreasing](https://mirror.codeforces.com/contest/1864/problem/A) Construct an array $a$ consisting of $n$ integers which satisfies the following conditions: - $a_1=x,a_n=y$; - $a$ is **strictly** increasing; - if we denote $b_i=a_{i+1}-a_{i}$ for $1 \leq i \leq n-1$, then $b$ is **strictly** decreasing. <spoiler summary="Constraint"> $1 \le x < y \le 1000,3 \le n \le 1000$ </spoiler> <spoiler summary="Difficulty"> DIV2A </spoiler> <spoiler summary="Point"> One of the easi...

Полный текст и комментарии »

Разбор Codeforces Round #122 Пожалуйста, задавайте возникающие у вас вопросы по задачам. Особенно это касается задачи D, так как она оказалась наиболее сложной. **Задача <<Экзамены>>** По условию $2n \le k \le 5n$. Если $k < 3n$ то некоторые экзамены мы сможем сдать только на $2$. Таких будет $3n-k$. Если же $3n \le k$, то мы все экзамены сдадим как минимум на три. **Задача <<Квадрат>>** Пусть карандаш идет по прямой и ставит крестики через каждые $(n+1)$ точку. Поставим в соответствие положению на прямой положение на квадрате. А именно, точке $x$ на прямой будет соответствовать точка, в которую придет карандаш, сдвинувшись по периметру квадрата на $x$. Тогда левому нижнему углу квадрата соответствуют все точки вида $4np$ для некоторого целого неотрицательного $p$. Поставленным крестиками будут соответствовать точки $k(n+1)$. Самая ближайшая точка совпадения двух семейств, за исключением начальной, будет в LCM($n+1$, $4n$) (LCM --- НОК). Тогда всего мы поставим $\frac{LCM(n+1,4n)}{n+1} + 1$ крестиков. *...

Полный текст и комментарии »

Codeforces Round #613 (Div. 2) Editorial [tutorial:1285A] <spoiler summary="code"> ```cpp #include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long int n; string s; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> s; cout << n + 1 << endl; } ``` </spoiler> [tutorial:1285B] <spoiler summary="code"> ```cpp #include <bits/stdc++.h> using namespace std; #define finish(x) return cout << x << endl, 0 #define ll long long int n; vector <int> a; bool solve(){ cin >> n; a.resize(n); for(auto &i : a) cin >> i; ll sum = 0; for(int i = 0 ; i < n ; i++){ sum += a[i]; if(sum <= 0) return 0; } sum = 0; for(int i = n - 1 ; i >= 0 ; i--){ sum += a[i]; if(sum <= 0) return 0; } return 1; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while(T--){ if(solve()) cout << "YES\n";...

Полный текст и комментарии »

Codeforces Round #992 (Div.2) Editorial [problem:2040A] <spoiler summary="Editorial"> [tutorial:2040A] </spoiler> <spoiler summary="Solution C++"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int tt; cin >> tt; while (tt--) { int n, k; cin >> n >> k; vector < vector <int> > b(k); for (int i = 1; i <= n; i++) { int x; cin >> x; b[x % k].push_back(i); } int res = -1; for (int i = 0; i < k; i++) { if ((int)b[i].size() == 1) { res = b[i][0]; break; } } if (res == -1) { cout << "NO" << endl; } else { cout << "YES" << endl << res << endl; } } return 0; } ~~~~~ </spoiler> <spoiler summary="Solution Python"> ~~~~~ for _ in range(int(input())): n, k = map(int, input().split()) a = list(map(int, input().split())) b ...

Полный текст и комментарии »

Codeforces Round #818 (Div. 2) Разбор. Задача A. Идея [user:Igorbunov,2022-09-02] <spoiler summary="Hint 1"> У нас могут быть только следующие пары чисел $(x, x)$, $(x, 2 \cdot x)$, $(x, 3 \cdot x)$ </spoiler> <spoiler summary="Решение"> Давайте заметим, что у нас могут быть только следующие пары чисел: $(x, x)$, $(x, 2 \cdot x)$, $(x, 3 \cdot x)$. <spoiler summary="Доказательство:"> Пусть $d = gcd(a, b)$, тогда заметим, что не может быть $a = k \cdot d$, где $k > 4$, так как иначе $lcm$ точно будет не меньше $k \cdot d > 3 \cdot d$. Тогда остается только варианты выше, а также $(2 \cdot d, 3 \cdot d)$. Но в этом случае $lcm = 6 \cdot d$. </spoiler> Количество первого типа $n$, второго $2 \cdot \lfloor \frac{n}{2} \rfloor$, третьего $2 \cdot \lfloor \frac{n}{3} \rfloor$. А значит, ответ на задачу равен $n + 2 \cdot \left( \lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{3} \rfloor \right)$. </spoiler> ------------------------------ Задача B. Идея [user:FairyWinx,2022-09-02] <spoiler summary="Hint 1...

Полный текст и комментарии »

Minimized LCM Construction Hi guys! Today, we will see how to solve this problem: _You are given two positive integers **n** and **x**. Find an array of positive integers with length **n** and sum **x** that has minimum LCM._ Let's start with a simple brute force solution that creates every possible valid array and finds the minimum LCM: ~~~~~ void solve_1(int len, int sum, int cur, int& ans) { if (len == 0) { if (sum == 0) { ans = min(ans, cur); } return; } int rem = sum - len + 1; for (int val = 1; val <= rem; val++) { solve_1(len - 1, sum - val, lcm(val, cur), ans); } } int ans = x; solve_1(n, x, 1, ans); ~~~~~ This solution is currently able to solve all valid inputs, constrained up to `(x <= 25)`. In order to understand how to optimize it further let's see what kind of arrays it generates: ~~~~~ [1, 2, 2, 4] [1, 2, 4, 2] [4, 2, 1, 2] [4, 2, 2, 1] ~~~~~ It's a case of _(n, x) = (4, 9)_ and as you can ...

Полный текст и комментарии »

Codeforces Round 1003 Discussion Stream (with Hints) [Original blog](https://aryanc403.com/editorial/codeforces-round-1003/) [I'm currently live discussing the problems.](https://www.twitch.tv/aryanc403) I will add problemwise timestamp after the discussion stream. You can join in if something in this blog is unclear or if you have more questions. VOD: [Twitch](https://www.twitch.tv/videos/2376873914) and [YouTube](https://youtu.be/I78mJIx4JQ0) [problem:2065A] <spoiler summary="Idea"> Find the length n of the string, and then print first n-2 chars and then i. </spoiler> My submission &mdash; [submission:305152340] [problem:2065B] <spoiler summary="Hint 1"> Let n be the length of the string. Answer is either 1 or n </spoiler> <spoiler summary="Hint 2"> If there exists adjacent 2 equal chars, we can reduce the string to length 1. The idea is we remove these 2 equal chars, and then replace them with one nearby char, thereby ensuring that we still have 2 adjacent eq...

Полный текст и комментарии »

OMORI CONTEST Editorial Thank you for joining the [contest](https://codeforces.me/contestInvitation/fc8da6d6845e77adc452e754d3d84c1086148c59) &#128522;. <spoiler summary="How did you find the contest?"> - Great - Good - Average - Bad - Trash </spoiler> <spoiler summary="Which problem is your favourite?"> - SUNNY - AUBREY - HERO - KEL - MARI - BASIL - OMORI </spoiler> #### [A. SUNNY](https://codeforces.me/gym/551481/problem/A) <spoiler summary="Editorial"> <spoiler summary="Problem Tags"> `bijections` `dynamic-programming` </spoiler> <spoiler summary="Hint 1"> Try to find a bijection, meaning try to find another problem such that its solution is equivalent to the original problem but is easier to solve. </spoiler> <spoiler summary="Hint 2"> Try to notice what happens to the difference array of $a$ when Sunny plays a note. </sp...

Полный текст и комментарии »

Codeforces Trainings Season 1 Episode 4: Editorial ### A. Arrangement of RGB Balls (difficulty: easy) If, among 3 consecutive balls, there are no two of the same color, then there's exactly one ball of every color among them. Thereforce, the sequence is determined by the order of the first 3 balls. Imagine these are RGB; then, the sequence continues as RGBRGBRGB... There are only $3!=6$ possible initial triples, so we can try all the sequences defined by them, and for every one of them, check if it can be constructed. [cut] When is it possible to construct such a sequence? Take the initial triple to be "GRB", for example (the idea for other triples is analogous). It's clear that the sequence is "GRB" repeated some $K$ times, and after that, there are the first 0, 1 or 2 balls from that triple (for example, "GRBGRBGR" or just "G"). It's clear that $K=min(R,G,B)$. So it's possible to construct iff $1\ge G-K \ge R-K \ge B-K$. Testing the existence of any sequence can be done in $O(1)$ time like this. There are $O(1)$ possib...

Полный текст и комментарии »

Editorial of Educational Codeforces Round 13 ### [problem:678A] The problem was suggested by Abdrakhman Ismail [user:Ismail_A,2016-06-16]. We should find minimal $x$, so $x\cdot k>n$. Easy to see that $x=\lfloor\frac nk\rfloor+1$. To learn more about floor/ceil functions I reccomend the book of authors Graham, Knuth, Patashnik "Concrete Mathematics". There is a chapter there about that functions and their properties. <spoiler summary="С++ solution"> ~~~~~ li n, k; bool read() { return !!(cin >> n >> k); } void solve() { cout << (n / k + 1) * k << endl; } ~~~~~ </spoiler> Complexity: $O(1)$. ### [problem:678B] The problem was suggested by Arthur Jaworski [user:KingArthur,2016-06-16]. Two calendars are same if and only if they have the same number of days and starts with the same day of a week. So we should simply iterate over years and maintain the day of a week of January, 1st (for example). Easy to see that the day of a week increases by...

Полный текст и комментарии »

Codeforces Round #785 (Div. 2) Editorial I am sorry for the weak tests in B, for C being a little standardish and for misjudging the relative difficulties of E and F. Nevertheless, I hope you enjoyed the round. Here is the editorial. Do provide your feedback on each problem so that I can improve upon them the next time. #### [A. Subtle Substring Subtraction](https://codeforces.me/contest/1673/problem/A) <spoiler summary="Hint 1"> Greedy </spoiler> <spoiler summary="Hint 2"> The answer depends on whether the length of $s$ is even or odd and on the first and last characters of $s$ if the length is odd. </spoiler> <spoiler summary="Tutorial"> The problem can be solved greedily. Let $n$ be the length of the given string. - If the $n$ is even, it is always optimal for Alice to remove the whole string. - If the $n$ is odd, it is always optimal for Alice to remove either $s_1s_2\ldots s_{n-1}$ or $s_2s_3\ldots s_n$ based on which gives the higher score and then Bob can remove the remaining character ($s_n$ or ...

Полный текст и комментарии »

Codeforces Round 931 (Div. 2) Editorial [1934A &mdash; Too Min Too Max](https://codeforces.me/contest/1934/problem/A) <spoiler summary="Solution"> <spoiler summary="Hint 1"> What will be answer if there were only $4$ elements in the array? </spoiler> <spoiler summary="Solution"> Suppose if there were only $4$ elements in the array. Let them be $a \leq b \leq c \leq d$. Then the answer will be maximum of the three cases which are listed as follows:- $$|a-b|+|b-c|+|c-d|+|d-a| = 2*d - 2*a$$ $$|a-b|+|b-d|+|d-c|+|c-a| = 2*d-2*a$$ $$|a-c|+|c-b|+|b-d|+|d-a| = 2*(d+c)-2*(a+b)$$ so clearly $2*(d+c)-2*(a+b)$ is the maximum. So, to maximize this we can set $d$, $c$ as large as possible and $a$, $b$ as small as possible i.e. $d=a_n$, $c=a_{n-1}$, $b=a_{2}$ and $a=a_{1}$ where $a_i$ means $i^{th}$ element in sorted order of given array. </spoiler> </spoiler> <spoiler summary="Code (C++)"> ``` #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false);...

Полный текст и комментарии »

Rayan 2024 Selection Round Editorial ### &#128075; Salam Codeforces! Here are the step-by-step solutions. Hoping you enjoy them! &#128522; The announcement blog is available [here](https://codeforces.me/blog/entry/136396) and you can also explore all blogs related to Rayan [here!](https://codeforces.me/rayan) #### [problem:2034A] **Idea:** [user:ArshiaDadras,2024-11-26] &mdash; **Preparation:** [user:Amirrzwm,2024-11-26] <spoiler summary="Solution"> - **Step 1:** Prove that for the minimum value of $m$, we must have $m \% a = m \% b = 0$. - **Step 2:** To prove this, show that if $m \% a = m \% b = x > 0$, then $m-1$ will also satisfy the problem's requirements. - **Step 3:** Since $m \ge \min(a , b)$, if $x > 0$, then $m > \min(a , b)$ must hold. Therefore, $m - 1 \ge \min(a , b)$ implies that $m-1$ satisfies the requirements. - **Step 4:** Thus, $m$ must be divisible by both $a$ and $b$. The smallest such $m$ is $lcm(a, b)$ which can be calculated in $O(\log(\max(a, b)))$. </spoiler> <spoiler...

Полный текст и комментарии »

[Tutorial] Zeta, Mobius Transform to AND, OR, GCD Convolution ## Introduction [Original Post(Korean)](https://blog.naver.com/jinhan814/223175490201) For those who have studied the Inclusion-Exclusion Principle or the Mobius Inversion formula, you may have wondered about the definition of $μ(n)$ and the process of offsetting unnecessary values by multiplying $(-1)^{|s|}$. Although it is possible to show the validity of these formulas through expansion, such proofs lack intuitive clarity. In this article, I will define Zeta and Mobius Transform on a Poset and explore examples from various Posets. Understanding these concepts will provide insights into the Inclusion-Exclusion Principle and the Mobius Inversion formula. Additionally, Zeta and Mobius Transform are essential concepts connected to SOS DP and AND, OR, GCD, LCM Convolution. In the final part of the article, we will examine interesting connections to various convolutions from Zeta and Mobius Transform. ## Table of Contents 1. What is Poset? 2. Zeta, Mobius Transform on Pose...

Полный текст и комментарии »

Teamscode Spring 2023 Editorial This is the editorial for a recent contest [Teamscode](https://www.teamscode.org/). The problems are open for upsolving on [this gym](https://codeforces.me/gym/104287). Problems were prepared by [user:oursaco,2023-04-06], [user:dutin,2023-04-06], [user:thehunterjames,2023-04-06], [user:Bossologist,2023-04-06], [user:Esomer,2023-04-06], and me. ### [A. What do you do when the contest starts? Are you busy? Will you solve Bingo?](https://codeforces.me/gym/104287/problem/A) <spoiler summary = "Editorial"> <spoiler summary = "Are you busy?"> 1. WorldEnd/SukaSuka 2. Bocchi the Rock </spoiler> <spoiler summary = "No Sweep"> 1. Thomas </spoiler> <spoiler summary = "Multiplication Table"> 1. Lycoris Recoil </spoiler> <spoiler summary = "Greatest Common Multiple"> 1. Bokuben </spoiler> <spoiler summary = "A Certain Scientific Tree Problem"> 1. A Certain Scientific Railgun </spoiler> <spoiler summary = "Two and Three"> 1. Quintessential Quintluplets...

Полный текст и комментарии »

New CSES Tasks Editorials Editorial for some of the new CSES tasks. Tasks that are trivial or too similar to already existing tasks are not included. Every time I solve a new nontrivial task, I will add it here. **NOTE: ONLY READ THE SOLUTIONS IF YOU ARE COMPLETELY STUCK AND OUT OF IDEAS. CSES tasks are the kinds of tasks you can solve at a random time by random chance. You might read a task today and solve it next week. Or next month. Or next 3 months. So read at your own risk.** ## Sorting & Searching <spoiler summary="Distinct Values Subsequences"> For each value $x$, we can include $0$ or $1$. If $f(x)$ is the number of times $x$ appears in the array, Then there are $f(x) + 1$ ways to pick $0$ or $1$ occurrences of $x$. Since every value is independent of every other values, we will take the product of $f(x) + 1$ over all $x$. This can be done with `std::map` or sorting. </spoiler> ## Dynamic Programming <spoiler summary="Mountain Range"> Let $L_i$ be the nearest greater element o...

Полный текст и комментарии »

Codeforces Round 1003 (Div. 4) Editorial <spoiler summary="Rating Predictions"> | Predictor | A | B | C1 | C2 | D | E | F | G | H | |--------------------------------------------|------|------|------|------|------|------|------|------|------| | [user:Proof_By_QED,2025-02-04] | 800 | 800 | 900 | 1300 | 1200 | 1500 | 1700 | 1800 | 2100 | | [user:DivinePunishment,2025-02-04] | 800 | 1000 | 900 | 1400 | 1400 | 1400 | 1600 | 1700 | | | [user:poi,2025-02-04] | 800 | 800 | 800 | 1000 | 1200 | 1200 | 1700.223 | 1600 | Didn't solve so $\infty$ | | [user:mathtsai,2025-02-04] | 800 | 900 | 1000 | 1200 | 1400 | 1500 | 1700 | 1600 | | | [user:macaquedev,2025-02-04] | 800 | 800 | 800 | 900 | 1200 | 1300 | 1400 | 1400 | | | [user:Intellegent,2025-02-04] | 800 | 800 | 900 | 1100 | 1300 | 1500 | 1700 | 1800 | 2100 | | [user:cry,2025-01-15] | 800 | 800 | 900 | 1100 | 1300 | ...

Полный текст и комментарии »

Codeforces Round #848 (Div. 2) Editorial [problem:1778A] <spoiler summary="Tutorial"> [tutorial: 1778A] </spoiler> <spoiler summary="Code"> ```C++ #include <bits/stdc++.h> using namespace std; const int sz = 1e5 + 10; int ara[sz]; int main() { int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); int sum = 0; for(int i = 1; i <= n; i++) { scanf("%d", &ara[i]); sum += ara[i]; } int ans = -1e9; for(int i = 1; i < n; i++) { if(ara[i] == ara[i+1]) { if(ara[i] == 1) ans = max(ans, sum-4); else ans = max(ans, sum+4); } else ans = max(ans, sum); } printf("%d\n", ans); } return 0; } ``` </spoiler> [problem:1778B] <spoiler summary="Tutorial"> [tutorial: 1778B] </spoiler> <spoiler summary="Code"> ```C++ #include <bits/stdc++.h> using namespace std; ...

Полный текст и комментарии »

AtCoder Beginner Contest 150 English Solutions #A &mdash; 500 Yen Coins We are essentially asked whether $500K \geq X$. We can determine this using an if statement. If you'd like to be fancy, you can shorten your code using the ternary operator, printing $\texttt{500K >= X ? "Yes" : "No"}$. Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc150/submissions/9382642) --- #B &mdash; Count ABC There are several ways to do this. The first is to compute each three-letter substring of $S$, either through brute force or your language's substring computation function, then comparing them to "ABC". Another, which I implemented, is to simply iterate over each position in the string up to $N-3$, using zero-indexing, and check whether $S[i] = A$, $S[i+1] = B$, and $S[i+2] = C$. If so, we increment the answer. Either way, we can maintain a count of "ABC" substrings and return it at the end. (Of course, we theoretically could use a more complicated pattern matching algorithm, but because the str...

Полный текст и комментарии »

Codeforces Round #825 (Div. 2) Editorial Thank you for participation! We apologize for problem D that turned out to be harder than expected. Still, we hope that you liked most of the problems. In case you found C2 tedious to implement or found many cases to deal with, I would recommend you to have a look at the intended solution. I think it is interesting and easy to implement. [problem:1736A] <spoiler summary="Solution"> It is easy to observe that the second operation needs to be performed **at most** once. Now, we just need to check $2$ cases, one in which the re-arrangement operation is used, and one in which it is not. If the re-arrangement operation is to be used, then we just need to make the counts of $0$s and $1$s in $a$ equal to that of $b$. Without loss of generality assume $a$ contains $x$ more $0$s than $b$, then the cost in this case will just be $x + 1$ (extra one for re-arrangement cost). If the re-arrangement operation is not to be used, then we just need to make each element of $a$ equal to ...

Полный текст и комментарии »

Invitation to Insomnia Qualifier 2022 Hello Codeforces! Computer Club, MNNIT Allahabad, India is glad to invite you to the annual programming competition of MNNIT, INSOMNIA, which is an ACM-ICPC style team programming contest of 2.5 hours duration held on Codeforces during its annual technical fest Avishkar. The team can consist up to 3 members. <b>Contest Details: </b> <ol> <li> Qualifiers: </li> <ul> <li> Start Time: Wednesday, November 9, 21:00 IST</li> <li> Duration: 2.5 hours</li> </ul> <li> Finals: </li> <ul> <li> Start Time: Sunday, November 13, 12:00 IST</li> <li> Duration: 2.5 hours</li> </ul> </ol> **Top 25** global teams, and **Top 25** teams from MNNIT (based on the result of Qualifiers) will qualify to the Finals. The prize distribution for global teams is mentioned below: <br>  Teams consisting of MNNIT students only will be eligible for a seperate prize pool. Register your team for the qualifiers here: https://forms.gle/BKsbKfoGzSxC394R8 <br>...

Полный текст и комментарии »

Codeforces Round 1008 (Div. 1, Div. 2) Editorial I hope everyone enjoyed the tasks, and thank you for participating. Thank you to the coordinators and testers for suggesting solutions and modifications to the tasks, as I alone wouldn't be able to solve my own tasks or make it to how it is right now. Also thank you to them for dealing with me since July. Please tell me in the comments if the editorial is written incorrectly or unintelligibly somewhere. I'm not the best at phrasing some things, and would appreciate amendments to the editorial. [problem:2078A] <spoiler summary="Hint"> Something doesn't change after each operation. </spoiler> <spoiler summary="Solution"> The average of the entire array doesn't change after each operation. Simply check whether the average value of $a$ is $x$ or not. Time complexity: $\mathcal{O}(n)$ per test case. Submission: [submission:310297520] </spoiler> [problem:2078B] <spoiler summary="Hint 1"> Try to put as many people in cell $n$ as possible. </spoiler> <spoile...

Полный текст и комментарии »

[Educational] Combinatorics Study Notes (1) Hello Codeforces! Today I'll be writing about what I have learnt about combinatorics, which played, and, in my opinion, will still be playing a important role in both Codeforces and CP (short for competitive programming). However, combinatorics is such a great subject that made that impossible for me to write it all in one blog. So, this is just the very first blog, which is for beginners. If you are interested, please, pay attention to this account and I'll give posts as series for a long term. If you have found some mistakes in the text, or if you have some questions about the topic, please, leave a comment, and I'll check it weekly and reply. Also, if you find some grammar mistakes, a kind comment will be also welcomed. ### Thanks - [user:happyivan,2022-12-21], [user:Ptilon,2022-12-22], [user:ck1ne,2022-12-22] for pointing out some problems in the text. - [user:kill_all_placeholder,2022-12-21], [user:hydracody,2022-12-22] for providing possible topics. ### Content...

Полный текст и комментарии »

TheForces Round #45 (DIV3-Forces2) Editorial [A](https://codeforces.me/gym/106177/problem/A) Idea:[user:wakanda-forever,2025-11-11] <spoiler summary="solution"> For any non-decreasing sequence $(b_1, b_2, \ldots, b_m)$, $b_1$ $|$ $b_2$ $|$ $b_3$ $|$ $\cdots$ $|$ $b_m$ $\ge$ $b_1$. So, it is always better to consider subsequences of length $1$. Out of these, we can simply choose the smallest element and this is always optimal. Time Complexity: $O(n)$. </spoiler> <spoiler summary="code(C++)"> ```cpp #include<bits/stdc++.h> using namespace std; int main(){ int t; cin >> t; while(t--){ int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i]; cout << *min_element(a.begin(), a.end()) << '\n'; } } ``` </spoiler> <spoiler summary="Rate the Problem"> Amazing problem: Good problem: Average problem: Bad problem: [likes...

Полный текст и комментарии »

TheForces Round #36 (Starters-Forces) Editorial [A](https://codeforces.me/gym/105445/problem/A) Idea:[user:Mathmodel,2024-10-25] <spoiler summary="Hints"> <spoiler summary="Hint 1"> Divide $n$ to odd and even </spoiler> <spoiler summary="Hint 2"> How we can represent palindrome string ? <spoiler summary="Answer"> $$\displaystyle s=[\text{segment}](\text{median})[\text{segment reversed}]$$ </spoiler> </spoiler> <spoiler summary="Hint 3"> Denote the sum of segment is $f$ and sum of medians is $h$ then $m=2f+h$ </spoiler> <spoiler summary="Hint 4"> Focus on median when $n$ is even and use the symmetric property </spoiler> <spoiler summary="Hint 5"> See the $\min$ and $\max$ case for odd and even $n$ </spoiler> </spoiler> <spoiler summary="Analysis"> For odd values of $n$ we can re-express string $s$ as $$s_1s_2...s_{\lceil \frac{n}{2} \rceil}...s_n$$ Note that $s_1+s_2+...+s_{\lfloor \frac{n}{2} \rfloor}=s_{\lceil \frac{n}{2} \rceil+1}+....+s_n$ , so we can assume the sum as $f$...

Полный текст и комментарии »

2019 Summer PtzCamp, Day 8: XIX Open Cup Onsite, Editorial This editorial corresponds to [contest:103652], a.k.a "Jingzhe Tang Contest 2", held on Sept. 1st, 2019. Moreover, this problem set is a selection of "CCPC-Wannafly Winter Camp 2018, Day 2 (Div. 1 & Div. 2)" held on Jan 30th, 2019. Feel free to comment on the tutorials listed in the following (with some follow-up questions left to readers). Hope you enjoy solving these problems. --- [problem:103652A] <spoiler summary="solution"> The number of updates can be counted as the number of ordered pairs $(u, v)$ such that when $u$ is going to be removed, there exists at least one path between $u$ and $v$. If the path between $u$ and $v$ is unique in the original graph, we can conclude that pair exists if $u$ is the first removed node on the path with respect to an order, and $\frac{1}{cnt(u, v)}$ of all possible orders would meet this condition, where $cnt(u, v)$ is the number of nodes on the unique path between $u$ and $v$ (inclusive). In other cases, there exist exactly tw...

Полный текст и комментарии »

[Tutorial] Math note — Dirichlet convolution Originating from [Project Euler](https://projecteuler.net/), Dirichlet convolution saw its use in optimizing the problem to compute the partial sum of some specific multiplicative function. This article is aimed to introduce the exact technique applied. Prequisite ================== This tutorial can be viewed as an extension of [the previous tutorial](http://codeforces.me/blog/entry/53925), so I recommend to take a look at that one first. Dirichlet convolution ================== [Dirichlet convolution](https://en.wikipedia.org/wiki/Dirichlet_convolution) is a way to generate a new function from two functions. Specifically, the Dirichlet convolution of two functions $f(x)$ and $g(x)$ is: $$ \displaystyle f*g(x)=\sum_{d|x}f(d)g(\frac{x}{d}) $$ We already know that one property of such convolution is that if $f(x)$ and $g(x)$ are all multiplicative, $f*g(x)$ is multiplicative as well. Based on the property of the Möbius inversion $\sum_{d|n}\mu(d)=\epsilon(n)=[n=1]...

Полный текст и комментарии »

Codeforces round #717 editorial ### [problem:1516A] The general approach to minimizing an array lexicographically is to try to make the first element as small as possible, then the second element, and so on. So greedily, in each operation, we'll pick the first non-zero element and subtract $1$ from it, and we'll add that $1$ to the very last element. You can make the implementation faster by doing as many operations as you can on the first non-zero element simultaneously, but it's not necessary. Code link: https://pastebin.com/pBsychs2 ### [problem:1516B] So let's try to understand what the final array looks like in terms of the initial array. The best way to see this is to look at the process backwards. Basically, start with the final array, and keep replacing an element with the $2$ elements that xor-ed down to it, until you get the initial array. You'll see that the first element turns into a prefix, the second element turns into a subarray that follows this prefix, and so on. Hence, the whole process ...

Полный текст и комментарии »

Code Release for TheForce Round #42 Top 10 Hello, Codeforces. Today, as the main manager of a contest, I have decided to release the code for [TheForce Round # 42](https://codeforces.me/gym/105846) Top 10. The reason for this decision is that during the middle of the contest, we noticed unusual standings:  As a convention of codeforces, the code of all participants after the contest will be made public. I have decided to do the same thing here, and I believe that if you are a normal and honest participant, it will not infringe upon any of your rights. Also, we are checking the code of the participants and making cautious judgments. The allocation of prizes and the calculation of TheForce Rating will be delayed. Sorry for any inconvenience caused. We sincerely hope to maintain a fair and honest competitive environment for all participants. Integrity is the cornerstone of programming contests, and we believe that upholding these values...

Полный текст и комментарии »

Nebius Round 2 and Codeforces Round 1088 Editorial <spoiler summary="Rating Predictions"> | Predictor | A | B | C | D | E | F | G | H | |----------------------------------|-----|-----|-----|------|------|------|------|------| | [user:Proof_by_QED,2026-03-27] | 800 | 1300 | (1400-2000) | 1700 | 2100 | 2400 | 2600 | 3500| | [user:nifeshe,2026-03-27] | 800 | 1400 | (1400-1900) | 1800 | 2200 | 2600 | 3000 | 3500| | [user:dinohaur,2026-03-27] | 800 | 1200 | (1400-1700) | 2100 | 2300 | 2600 | 2900 | 3300 | | [user:_istil,2026-03-27] | 800 | 1200 | (1300-1800) | 1900 | 2300 | 2500 | 2800 | 3300 | | [user:Dragos,2026-03-27] | 800 | 1400 | (1400-1900) | 1800 | 2100 | 2400 | 2800 | 3500 | | [user:Argentum47,2026-03-27] | 800 | 1300 | (1400-2000) | 1900 | 2200 | 2500 | ? | ? | | [user:simplelife,2026-03-27] | 800 | 1200 | (1200-1800) | 1600 | 2000 | 2500 | 6700 | 6700 | | [user:AksLolCoding,2026-03-27] | 800 | 1000 | (1100-1800) | 1600 | 1900 | 2400 | ? | ? | | [user:nik_exists,2026-03-27]...

Полный текст и комментарии »

[GYM] Damascus-CPC 2018 — Editorial A. Martadella Strikes Again ================== if $ R*R > 2*r*r $ print $1$, otherwise print $2$ $R$ and $r$ should be **long long** or **double** to avoid overflow [C++ Code](https://pastebin.com/1CKZu6yN) B. Amer and Graphs ================== Since the edges are undirected ,we can store the edges ${u,v}$ as $(u \le v)$ for every edge $(1 \le i \le n)$. Let's assign a unique number for every unique edge in the array, then our problem will be reduced to : Find the number of different segments of the array which have the exact same elements ( same frequencies as well for each element ). This problem is a classic hashing problem that can be solved this way : let's choose some random large prime numbers $P$ and $MOD$ ,for example $P=304933 , MOD=10^9+7$. replace every element ${x_i}$ from the array with $ P^{x_i} \% MOD $. now the final problem is about finding different segments of the array which have the same sum value $\% MOD$ . This sol...

Полный текст и комментарии »

Codeforces Round 951 (Div. 2) Editorial Thank you for participating! [problem:1979A] ------------------ <spoiler summary="Solution"> Let $m$ be the maximum among the numbers $a_i, a_{i + 1},\ldots, a_j$. Notice that there always exists such $k$ that $i \le k < j$ and $a_k = m$ or $a_{k + 1} = m$. Therefore, we can assume that Bob always chooses the pair of numbers $p$ and $p + 1$ ($1 \le p < n$) as $i$ and $j$. Therefore you need to consider the maximums in pairs of adjacent elements and take the minimum among them. Let $min$ be the found minimum, then it is obvious that the answer is equal to $min - 1$. </spoiler> <spoiler summary="Code"> ~~~~~ #include <iostream> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; int a[n]; for (int& i : a) { cin >> i; } int mini = max(a[0], a[1]); for (int i = 1; i < n - 1; i++) { mini = min(mini, max(a[i], a[i + 1])); } ...

Полный текст и комментарии »

UT Open 2025 Editorial Hope you enjoyed our contest! The editorial is below: [A &mdash; Fishy Tank](https://codeforces.me/gym/105811/problem/A) Author: [user:DylanSmith,2025-04-10] <br/> Idea: [user:fishy15,2025-04-10] <spoiler summary="Solution"> The problem asks to place $n$ fishies into a $15\times25$ tank (including the borders). One way that we can accomplish this is by placing a single fishy at the beginning of rows $2$ to $n+1$, and no fishies in rows $n+2$ to $14$. This works since at most $10$ rows will have fishies (one for each fishy) and we have $13$ rows to work with. Make sure to print the border of the tank properly. Fun fact, the judge solution places the fishies uniformly at random into the tank. You can view this solution [here](https://gist.github.com/DylanSmith63/8340fd6bd9b7ca49f6d1c493200f954f). (It is definitely not the simplest solution, but the output looks really nice) </spoiler> [B &mdash; Card Counting](https://codeforces.me/gym/105811/problem/B) Author: [us...

Полный текст и комментарии »

Codeforces Round 1089 (Div. 2) Editorial Thank you for participating in our round. We apologise for C2 being too hard compared to C1. UPD : Added an alternative solution to B, which contains the original solution with a diagram for better understanding. [problem:2210A] Idea: [user:ritam1234,2026-03-27], Preparation: [user:ritam1234,2026-03-27] <spoiler summary="Solution"> We observe that $$x \bmod (x-1) = \begin{cases} 1 & \text{if } x > 2 \\ 0 & \text{if } x = 2 \end{cases}$$ Now observe that the sequence $n, n-1, \dots, 1$ satisfies the problem's condition (since $1 \ge 1 \ge \dots \ge 0$). Hence, the sequence $n, n-1, \dots, 1$ works. </spoiler> [problem:2210B] Idea: [user:ritam1234,2026-03-27], Preparation: [user:ritam1234,2026-03-27], [user:Argentum47,2026-03-27] <spoiler summary="Hint 1"> Suppose the game ends at chair $k$ (or chair $n+1$ if the game ends after successfully visiting the $n-th$ chair) , try to find the maximum number of chairs you can visit as a function of $k$. </spoil...

Полный текст и комментарии »

Zaglol FCDS Contest Solutions **[Zaglol Contest &mdash; FCDS level 1:](https://codeforces.me/gym/106350)** Problem [A. Zaglol welcoming](https://codeforces.me/gym/106350/problem/A): <spoiler summary="Solution"> Print **FCDS** </spoiler> <spoiler summary="Code"> ~~~~~ #include <iostream> using namespace std; int main() { cout << "FCDS" << endl; } ~~~~~ </spoiler> Problem [B. Baby Baraa in ALBAIK](https://codeforces.me/gym/106350/problem/B): <spoiler summary="Hint"> Notice that the values of $a_i$ are bounded: $(1 \le a_i \le 100)$. </spoiler> <spoiler summary="Solution"> It is easy to see that the $O(N^2)$ brute-force approach will be too slow for the given constraints. Therefore, we need a faster way to count, for each $i$, how many indices $j > i$ satisfy $(a_i > a_j)$. Since that the values of $a_i$ are bounded: $(1 \le a_i \le 100)$, we can use a frequency array to count how many numbers smaller than a given value appear to its right. We process the array fro...

Полный текст и комментарии »

Editorial: VI UnBalloon Contest Hey everyone! I hope everyone enjoyed the problems of [contest:105900]. This editorial contains the description of the solutions and their implementation. Feel free to discuss them in the comments! #### Problem A - Idea: [user:lucassala,2025-05-18] - Preparation: [user:lucassala,2025-05-18] <spoiler summary="Solution"> The problem is designed to deceive and seem like a graph problem, but the constraint that a mountain of a lower level must always be chosen before a mountain of a higher level makes the solution much easier. With this, we can see that it is always possible to pick the mountain of level $1$ before level $2$, and so on. Formally speaking, it is always possible to pick a mountain $i$ before a mountain $j$ if $i < j$. Therefore, the smallest lexicographical order is the numbers from $1$ to $N$, sorted. It is always possible to have an answer, so the possibility of printing $-1$ was also included to distract the competitors. </spoiler> <spoiler summary="C...

Полный текст и комментарии »

Codeforces Round #284 Editorial ## [problem:499A] One can solve the problem using greedy algorithm: if we can skip $x$ minutes at current moment without skipping any good moment &mdash; we do that, otherwise &mdash; watch another minute of the film. ## [problem:499B] In this task you must find for every string in the text the pair containing that string, and from two strings of that pair output the shortest one. ## [problem:498A] / [problem:499C] It can be easily proved that, if two points from statement are placed on different sides of some line, this line will be crossed anyway. So, all we need to do is to cross all these lines, so the answer is the number of these lines. To check if two points lies on different sides of a line one can simply use its coordinates to place in line equation and check if these two values have different signs. Solution complexity &mdash; $O(n)$. ## [problem:498B] / [problem:499D] Let's numerate all the songs and seconds starting from 0. Problem will be sol...

Полный текст и комментарии »

[GYM] Codeforces Round #383 (Hard) editorial Hello again, It’s [user:Arpa,2016-12-22] as usual :P. Hope you enjoyed from the Gym, and it’s here is the editorial. Problem packages are available [here](https://mega.nz/#F!b0ITUahD!eiz9jBfvPlmv9hM8n1ov2Q). Solutions are available [here](https://mega.nz/#F!P1YVhaJT!2c0_pq7MW78XXdNJ6Qh9xw) separately. Preparation details: -------------------- The problems authored by me when the main contest was authoring. Here is a table, showing the percentage of expected accepts (in my opinion, before the contest) and the number of accepts. <table width="100%"> <tr><td></td> <td>A</td> <td>B</td><td>C</td><td>D</td></tr> <tr><td>Expected</td> <td>100%</td> <td>30%</td><td>70%</td><td>10%</td></tr> <tr><td>Accepted</td> <td>27</td> <td>0</td><td>8</td><td>0</td></tr> </table> Difference from main problems -------------------- **A** : $n$ is bigger, binary_pow will not work. You need to calculate $n \mod 4$ in a faster way. **B** : $n$ and also numbers are much bigger, simp...

Полный текст и комментарии »

[For Beginners] Video Tutorials COPS Youtube Channel Hello, Codeforces community The Club of Programmers, IIT BHU is excited to announce the completion of beginners playlist of COPS YouTube channel. The content is made for beginners to enable them to kickstart their journey in the field of competitive programming. The videos and the corresponding document not only provide explanation to the concept but also provide a proper roadmap on how to study these concepts along with the practice problems. Youtube Channel link : [https://www.youtube.com/channel/UC01TZlNfu29QgG4FmUqVsdg/featured?view_as=subscriber](https://www.youtube.com/channel/UC01TZlNfu29QgG4FmUqVsdg/featured?view_as=subscriber) I am also providing the concept wise link to the videos for the beginners- - [Array, vector and pair](https://www.youtube.com/watch?v=bQ7rNIS3ZGs&list=PLLt4yMoVgczX0qAe_Q1ZHpDdd3_IRrCx6&index=1&t=1s) - [STL String](https://www.youtube.com/watch?v=899Dck1YF6M&list=PLLt4yMoVgczX0qAe_Q1ZHpDdd3_IRrCx6&index=2) - [Time and space complexit...

Полный текст и комментарии »

Sliding Window: Handling Non-Invertible Operators # Sliding Window The sliding window technique is a powerful approach for solving problems involving subarrays. It works by maintaining a subarray (window) of elements and moving (sliding) this window across the data to compute results efficiently. --- ## Introduction When I first learned the sliding-window trick for **sum**, it felt like magic: out went an O(n·K) double loop, in came an O(n) solution. Then I tried to do the same for **minimum** and promptly got stuck. You can’t “subtract” a minimum! In this tutorial you’ll learn: 1. How **invertible** operators (sum, XOR) let you slide in O(n) 2. Why **non-invertible** operators (min, max, GCD…) break the simple trick 3. A general O(n) approach using **two stacks** and **aggregation** --- ## 1. Invertible Operators: Sum & XOR If you can **undo** your operation in O(1), the sliding window is trivial. ### 1.1 Fixed-Size Window Sum ```cpp vector<int> slideSum(const vector<int>& a, int K) { int ...

Полный текст и комментарии »

prefix sum overview this blog will talk about prefix sums in general , how to use them , nice tricks , etc ... this blog was made to summarize HCPC-2025 training for prefix sums at Homs university / Syria. overview ================== ###1. what is prefix sum? ###2. get range sum in $O(1)$ ###3. find number of sub arrays with sum equal to $x$ (map trick) ###4. even more prefix sums lets start: ###1. what is prefix sum? prefix sum of an array a of size $n$ is another array of size $n+1$ as follows: ``` a(1) a(2) a(3) ... a(n) p(0)=0 p(1)=a(1) p(2)=a(1)+a(2) p(3)=a(1)+a(2)+a(3) ... p(n)=a(1)+a(2)+...+a(n) ``` so in general $p(i)$ contains the sum of all elements up to $i$ and we introduce another element at the front representing the empty prefix we can build prefix sum array in simple one line of code ``` for(int i=1;i<=n;i++)p[i]=p[i-1]+a[i]; ``` this is the only info we care about (for now). ###2.get range sum in ...

Полный текст и комментарии »

Codeforces Round 1103 (Div. 3) Editorial [problem:2236A] Idea: [user:arsen1y,2026-06-13] <spoiler summary="Tutorial"> [tutorial:2236A] </spoiler> <spoiler summary="Solution (arsen1y)"> ~~~~~ #include <bits/stdc++.h> #define int long long using namespace std; const int INF = (int) 1e18; int32_t main() { std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int _; cin >> _; while (_--) { int n; cin >> n; vector <int> a(n); int mx = -INF; int mn = INF; for (int i = 0; i < n; ++i) { cin >> a[i]; mx = max(mx, a[i]); mn = min(mn, a[i]); } cout << mx - mn + 1 << "\n"; } return 0; } ~~~~~ </spoiler> [problem:2236B] Idea: [user:eyfxrby,2026-06-13] <spoiler summary="Hint"> Try to find a property that does not change during operations. </spoiler> <spoiler summary="Tutorial"> [tutorial:2236B] </spoiler> <spoiler summ...

Полный текст и комментарии »

What you need to know about Least Common Multiple (LCM)? Least common multiple (LCM), typically denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b. Number theory dictates that the product of gcd(a, b) and lcm(a, b) is ab for positive integers, a and b ie lcm is simply absolute value of ab divided by gcd(a, b). When dealing with the greatest common divisor (GCD), the typical approach involves utilizing Bézout's identity, which builds upon the Euclidean theorem. Bézout's identity states that for integers a and b with a greatest common divisor d, there exist integers x and y such that ax + by = d. The extended Euclidean algorithm can be employed to compute a pair of Bézout coefficients efficiently. ~~~~~ static int gcd(int a, int b) { if (b == 0)return a; else return gcd(b, a % b); } static int lcm(int a, int b){ return Math.abs(a * b) / gcd(a, b); } ~~~~~ However, it's worth noting that this method may lead to integer overflow issues, particularly when dealing with larg...

Полный текст и комментарии »

Compiler Error in (C++17, C++20) I would like you to read the full story and give me some feedback on it, Thank You. Today I was solving this amazing [problem:715A] problem. After finding the idea and implementing it in C++, I submitted it in C++17 and later in C++20. But I was getting the wrong answers in the main test 5. At first, I thought my idea was wrong and I tried to prove my idea. Thinking about the problem the whole day I got nothing wrong with my approach and implementation. By not finding any other way I opened my submission and then I saw the reasons for the wrong answer [submission:198441320]. But in theory and my implementation method, there could not have errors such as this. After that, I got experimental and tested the code, and changed certain bits. But whatever I did it didn't change the verdict. The main part of my code was: ~~~~~ ll lcm(ll a, ll b){ ll LCM = (a * b); return LCM; } void solve(){ ll n; scl(n); // scan in long long ...

Полный текст и комментарии »

E. G-C-D, Unlucky! — Editorial I found that [problem](https://codeforces.me/contest/2126/problem/E) pretty cool, so I solved it and I wanted to formalise a proof and I figured, since the editorial isn't out yet I may as well give a formal proof of necessary and sufficient conditions for $a$ to exist. If there is an easier way to prove it let me know, I'm curious. Once you have the necessary and sufficient conditions, you can just check them, if they hold print(YES) (it'll work since they're sufficient), if they don't hold, print(NO) (it'll work because they're necessary). Let $p$ and $s$ be two sequences of integers of size $n > 1$. I'm looking for necessary and sufficient conditions such that we can find a sequence $a$ of size $n$ such that we can write for all $1 \leq i \leq n$, $p_i$ as $\text{GCD}(a_1, a_2, ..., a_i)$ and $s_i$ as $\text{GCD}(a_i, a_{i+1}, ..., a_n)$. #### Necessary conditions: Suppose we do have a sequence $a$ of size $n$ such that we can write for all $1 \leq i \leq n$, $p_i$ as $\t...

Полный текст и комментарии »

[Tutorial] A New Perspective on Numbers and Operators: Introducing Group Theory We often start our mathematical journey with counting, primes, and basic arithmetic. Then we encounter modular arithmetic, with its intriguing properties and theorems like Euclid's algorithm and the Chinese Remainder Theorem. But what if there's a deeper, more abstract framework that ties all these concepts together? You might have encountered hints that group theory is behind some clever algorithms and data structures ([like this comment suggests](https://codeforces.me/blog/entry/103174?#comment-915676)). But if you've tried to learn about it, you might have found resources that felt either too abstract and disconnected from your existing knowledge ([for instance](https://zhtluo.com/cp/from-burnside-to-polya-a-short-introduction-to-group-theory.html)), or too intimidating and complex ([like this one](https://codeforces.me/blog/entry/91731)). This blog aims to bridge that gap. We'll start with familiar ground in discrete math and modular arithmetic, and then progressively in...

Полный текст и комментарии »

Digit DP "tricks" Prereq: [this digit dp blog](https://codeforces.me/blog/entry/53960) Cut the flag dimension ------------------------- Usually, whatever states you use in the recursive dp function, you will memoize it. And often you will have some thing like this ~~~~~ int memo[pos][...][...][low] ~~~~~ Where `low` is the flag that checks if the current number is already smaller than the considered number. It is totally possible to subtract this dimension (half the memory needed) by manipulating it in the recursive function: Example problem: [Perfect Number](https://codeforces.me/contest/919/problem/B) This is what "normal" code would look like: <spoiler summary="normal code"> ~~~~~ ll mem[20][11][2]; ll dp(int pos, int sum, bool lo) { if(sum > 10) return 0; if(pos == n) return (sum == 10); ll& res = mem[pos][sum][lo]; if(res != -1) return res; res = 0; int mx = lo ? 9 : v[pos]; for(int d = 0; d <= mx; d++) ...

Полный текст и комментарии »

TheForces Round #43 (DIV2-Forces) Editorial Reminder: We welcome you to participate in the official DIV1/DIV2 round scheduled on the 31st! [A](https://codeforces.me/gym/106014/problem/A) Idea:[user:tamzid1,2025-07-25] <spoiler summary="solution"> We can see if $x$ is a perfect square, $x^x$, $x^{(x^x)}$, $\ldots$ are also perfect square. Proof: assume $x=y^2$, $x^z=(y^z) \cdot (y^z)$. So the answer is the number of perfect squares not greater than $n$. There are exactly $\lfloor \sqrt{n} \rfloor$ integers $x$ (with $1 \leq x \leq n$) such that $x$ is a mystic number. </spoiler> <spoiler summary="code(C++)"> ```cpp #include <iostream> #include <cmath> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; cout << static_cast<int>(sqrt(n)) << '\n'; } return 0; } ``` </spoiler> <spoiler summary="Rate the Problem"> Amazing problem: Goo...

Полный текст и комментарии »

ANCC Lockout Prelims Editorial We'd like to thank you all for participating in the contest, and hope you enjoyed it. --- [A &mdash; Distinct Strings](https://codeforces.me/gym/508320/problem/A) Idea: [user:etherinmatic,2024-03-04] [user:MridulAhi,2024-03-04] <br> <spoiler summary="Solution"> On selecting a substring of length $n$ from $p = s + s$, we get a cyclic rotation of $s$. So, the problem is equivalent to counting the number of distinct cyclic shifts of $s$. The constraints are small enough to allow bruteforce method of forming all cyclic shifts of $s$ and deleting the equal ones after sorting them. Time complexity : $O(n^2$log$n)$. Bonus task: Try solving the problem for $n \leq 10^6$. </spoiler> <spoiler summary="Implementation"> ``` #include<bits/stdc++.h> using namespace std; #define all(x) begin(x), end(x) #define sz(x) static_cast<int>((x).size()) int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; ...

Полный текст и комментарии »

Visualizing Number Theory on Grids Hello Codeforces! Recently, I authored the problem **[Contest Wanderer](https://codeforces.me/gym/696136/problem/E)**. The problem asks a very simple question: If you start walking on an $N \times M$ grid that wraps around its boundaries (moving $a$ steps down and $b$ steps right), how many unique starting positions do you need to pick to guarantee you step on every single cell in the room? Many people look at grid problems and immediately think of Grid Covering, DP with Broken Profiles, or Bipartite Matching. But this problem is a trap. It is purely **Number Theory and Modular Arithmetic**. Visualizing the Cycle: Two examples: **1.** $4 \times 6$:  **2.** $3 \times 6$:  Things to notice: -> No matter where you start on this grid, your path will eventually loop back to your exact starting coordinate. ->...

Полный текст и комментарии »

Aleppo-CPC 2025 Tutorial Thank you for participating in our contest, share your solutions and ideas in the comments. Problem A: [GCD MEX](https://codeforces.me/gym/106007/problem/A) Problem Author: [user:Go8,2025-07-18], Tutorial By: [user:Hosen_ba,2025-07-20] <spoiler summary="Tutorial"> make the first element $a_1 = lcm(1,2,\cdots,n-1)$ and the other $n-1$ elements $(1,2,3,...,n-1)$, then you will have $gcd(a_1,1) = 1$, $gcd(a_1,2) = 2$, $\cdots$ etc. then the $mex$ is at least $n$ </spoiler> <spoiler summary="Code"> ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long void solve() { int n; cin>>n; if(n==1) { cout<<0<<endl; return; } ll x=1; cout<<n<<endl; for(ll i=1; i<n; i++) { cout<<i<<" "; x=(x*i)/__gcd(x,i); } cout<<x<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t=1; cin>>t; while(t--) { solve();...

Полный текст и комментарии »

Editorial [GYM] 2018 BACS Contest replay [problem:101864A] Setter: [user:ISwearItIsMyLastContest,2018-08-10] Alternate Writer: [user:prophet_ov_darkness,2018-08-10], [user:s_h_shahin,2018-08-10] <spoiler summary="Editorial"> This problem actually reflect the [josephus problem](https://en.wikipedia.org/wiki/Josephus_problem). The main part of this problem is to find Number of possible Y such that **josephus(Y,2) = X** . After finding this rest part is obvious calculation. Let’s see first few values of josephus(i,2): 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 We can see that there is a nice pattern here. **josephus(n,2)** is an increasing odd sequence that restarts with **josephus(n,2) = 1** whenever the index **n** is a power of 2. First we will find minimum value of p such that **josephus(p,2) = X**. we can do this in **O(log n)** , because for every **q>0** **josephus(2^q-1,2) = 2q^-1** and **josephus(2^q,2) = 1**. So we can run loop through q >= 0 and find highest value of **q** such that **josephus(2...

Полный текст и комментарии »

Properties Of GCD function • GCD of a set of numbers can be thought as a blue-print of those numbers. If u keep adding the GCD you can make all numbers that belong in that set. • Every common divisor of a and b is a divisor of gcd(a,b). • Gcd(a,b) where both a and b are non-zero, can also be defined as the smallest positive integer d which can be a solution/which can be expressed as a linear combination of a and b in the form d=a*p + b*q, where both p and q are integers. • Gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|. • If 'a' divides b*c and gcd(a,b)=d , then a/d divides c. • If m is a non-negative integer, then gcd(m⋅a, m⋅b) = m⋅gcd(a, b).It also follows from this property that if gcd(a,b)=g, then a/g and b/g should be coprime. Try to derive it yourslef. • If m is any integer gcd(a,b)=gcd(a+m*b,b). • The GCD: gcd(a, b) = gcd(b, a%b). • If m is a positive common divisor of a and b, then gcd(a/m, b/m) = gcd(a, b)/m. • GCD is a m...

Полный текст и комментарии »

Newton School Grand Coding Contest 2022 Editorial #### A. First Day at Newton School ------------------ <spoiler summary = "Solution"> ~~~~~ //C++ implementation #include <iostream> #include <string> using namespace std; int main () { string s; cin >> s; if (s == "Apple") cout << "Gravity"; else cout << "Space"; } ~~~~~ </spoiler> #### B. A Growing Rivalry ------------------ <spoiler summary = "Solution"> Let the number of rounds won by Nutan be $n$ and that won by Tusla be $t$. As $n + t = L$, we are given that $n + t$ is odd. Thus, we have $n \neq t$ as otherwise $n + t$ will be even. So we can see that there is no draw possible, one of Nutan or Tusla must have won more rounds than the other. To find whom, we first initialize $n = t = 0$. We will then iterate through each character of the string $S$. If the character is 'N', we increment $n$ by $1$, otherwise we increment $t$ by $1$. After we have finished iterating the string, if $n < t$ then Tusla has won, otherwise Tesla has won. You ca...

Полный текст и комментарии »

Editorial for TheForces Round #40 #### [Problem A &mdash; Submission Bait II](https://codeforces.me/gym/105767/problem/A) Author: [user:wuhudsm,2025-03-07] Preparer: [user:Banis,2025-03-07] <spoiler summary="Hint"> Think about what it means for one number to divide another. If $x$ and $y$ are two distinct integers and $x$ divides $y$ then $x$ can't be too big with respect to $y$, more specifically $x \leq \frac{y}{2}$. How can we use this in our problem? </spoiler> <spoiler summary="Solution"> Read the hint first. $\newline$ While constructing the array $a$ of size $n$, the goal is to pick numbers from $1$ to $2n$ such that no number divides another. The hint gives us a nudge: $x | y \implies x \leq y/2$, so what if we construct the array in a way that $\text{min}(a)$ (the smallest element of the array) is greater than $\frac{\text{max}(a)}{2}$ (half of the maximum element). We can construct the array $[n + 1 \ldots 2n]$ which satisfies our required condition. $\newline$ Time Complexity : $O(n)$ </...

Полный текст и комментарии »

Topics Problems Good Day to you! While a lot of us, when he begins to start competitive programming he found difficult to found problems on some topics in the beginning to practice of it, and same thing for a lot of ICPC Communites that they have started. These are some topic not advanced and videos, problems and articles on them. <br> <spoiler summary="Prefix Sum & Frequency Array"> [Wonderful Coloring](https://codeforces.me/contest/1551/problem/B1) [Do Not Be Distracted](https://codeforces.me/contest/1520/problem/A) [Letter](https://codeforces.me/problemset/problem/43/B) [Pangram](https://codeforces.me/problemset/problem/520/A) [Andryusha and Socks](https://codeforces.me/contest/782/problem/A) [Count Numbers](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/A) [Count Characters](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/B) [Range Sum Query](https://codeforces.me/group/c3FDl9EUi9/contest/262795/problem/E) [Count a's](https...

Полный текст и комментарии »

Codeforces Round #1091 and CodeCraft '26 (Div. 2) Editorial [problem:2217A] =============== **Idea:** [user:shakr,2026-04-06] <br> **Problem Setting:** [user:AS23,2026-04-06], [user:shakr,2026-04-06] <spoiler summary="Hint 1"> What if Shaunak never uses the special move? </spoiler> <spoiler summary="Hint 2"> If Shaunak uses the special move, is using it on the first turn any different from using it later? </spoiler> <spoiler summary="Hint 3"> The above two cases are independent, and give you two conditions for Shaunak to win. What are they? </spoiler> <spoiler summary="Solution"> In a game without special moves, every turn reduces the total sum of the array, $\sum a_i$, by exactly $1$. Thus, the game lasts exactly $\sum a_i$ turns. The first player (Shaunak) wins if $\sum a_i$ is odd, and the second player (Yash) wins if $\sum a_i$ is even. <ul> <li><b>If $\sum a_i$ is odd:</b> Shaunak plays normally and wins. He doesn't need the special move.</li> <li><b>If $\sum a_i$ is even:</b> Shaunak is guaranteed to lose ...

Полный текст и комментарии »

Introducing GCD in math and CP # Introducing **gcd**: sacrifice one variable to gain tight constraints In problems with two (or more) integer variables it’s often profitable to **factor out their gcd**: let $d=\gcd(x,y)$, then write $x=a d,\ y=b d$ with **$\gcd(a,b)=1$**. Sure, you’ve added one more variable ($d$), but in exchange you get the **coprimality** of $a,b$, which sharply restricts the search space, makes divisibility statements “split” into clean factors, and simplifies the final casework/estimates. --- ## How to apply (6-step template) 1. **Normalize.** Handle zeros/signs first (e.g., consider the cases $x=0\leftrightarrow y=0$, $x,y>0$, etc.). 2. **Introduce gcd.** Put $d=\gcd(x,y)$, set $x=a d,\ y=b d$ with $\gcd(a,b)=1$. 3. **Cancel powers of $d$.** Divide the original equation/divisibility by the **maximal** power of $d$. 4. **Split divisibility.** Any statement like $U(a,b)\mid V(a,b)$ with coprime pieces often forces a “big” factor to divide one **rigid** component. 5. **Finish...

Полный текст и комментарии »

Codeforces Round #328 Problem Analysis Problem A. PawnChess -------------------- Player A wins if the distance of his nearest pawn to the top of the board is less than or equal to the distance of the Player’s B nearest pawn to the bottom of the board (Note that you should only consider pawns that are not blocked by another pawns). Problem B. The monster and the squirrel --------------------------------------- After drawing the rays from the first vertex $(n-2)$ triangles are formed. The subsequent rays will generate independently sub-regions in these triangles. Let's analyse the triangle determined by vertices $1, i, i+1$, after drawing the rays from vertex $i$ and $(i+1)$ the triangle will be divided into $(n-i)+(i-2)=n-2$ regions. Therefore the total number of convex regions is $(n-2)^2$  If the squirrel starts from the region that have $1$ as a vertex, then she can go through each region of triangle $(1, i, i+1)$ ...

Полный текст и комментарии »

National Competitive Programming Challenge — Editorial Here is the link to the contest: [Link](https://codeforces.me/contestInvitation/6071a436743e70518e953453aadcf924bca069aa) ### [A. The Blacksmith](https://codeforces.me/gym/656191/problem/A) <spoiler summary="Credits"> - **Problem Idea**: [user:eulmelk,2025-12-12] - **Problem Setter**: [user:eulmelk,2025-12-12] </spoiler> <spoiler summary="Rate the Problem"> - **How good is this problem?** - Very Good - Good - Bad - Very Bad - **How hard is this problem?** - Very Easy - Easy - Hard - Very Hard </spoiler> #### Approach 1 <spoiler summary="Tutorial"> **Step 1**<br> $n \le 500$, so the total number of pairs is at most $\frac{n(n-1)}{2} = \frac{500 \cdot 499}{2} = 124750$. This is easily manageable within time limits. **Step 2**<br> By checking every possible pair, we never miss any valid combination. Therefore, keeping the maximum among all va...

Полный текст и комментарии »

[Editorial] Newton School December 2021 Contest Credits: [user:Lubba_Lubba,2021-10-30], [user:dnshgyl21,2021-10-30], [user:Sawarnik,2021-10-30], [user:Xzirium,2021-10-30] #### [A. AC or not?](https://my.newtonschool.co/playground/code/stlxznqa697h/) ------------------ <spoiler summary = "Solution"> Take the input in variable $n$. So if $n == 1$, print $AC$, else print $WA$. </spoiler> #### [B. ABBA](https://my.newtonschool.co/playground/code/kr38ahzcg1br/) --------------------- We solve this problem in cases: Firstly, we take the case where all the characters of the string are either ‘a’ or ‘b’. For this do not require to perform any operations as every character of the string is equal. Secondly, we take the case where ‘a’ and ‘b’ both exist at least once. Here we can either make all the characters ‘a’ or ‘b’. We try to calculate the minimum operations required to make all characters ‘a’. We also observe that there exists a character ‘b’ with adjacent character ‘a’ since ‘a’ and ‘b’ both exist at least once. We...

Полный текст и комментарии »

Editorial for IIT Hyderabad Code Clash 2025 We hope you enjoyed solving the problems, and thank you for participating! We are very sorry about the error in constraints for D. [Problem A &mdash; Denial](https://codeforces.me/gym/590383/problem/A) <spoiler summary="Intuition"> The traveler’s position after any number of moves is constrained on a fixed circle which is the circle that passes through the three points: $P$, position after first move, position after second move. For the traveler to come back to $P$, he will have to head in the same direction as the initial direction and if he is heading in the same direction as the initial direction then, he must be at $P$(else his subsequent positions wont lie on the same circle). Thus, $n\cdot a$ must be a multiple of $360$. The first time this happens is when he turns a total angle of $lcm(a,360)$, i.e, the number of moves is $\frac{lcm(a,360)}{a}$. Thus the total distance is $d \cdot \frac{lcm(a,360)}{a}$. </spoiler> <spoiler summary= "Formal proof"> Let the directi...

Полный текст и комментарии »

VK Cup Round 3 editorial [problem:542A] -------------- Let's fix the TV channel window and look for a commerical having the largest intersection with it. There are four types of commercials: lying inside the window, overlapping the window and partially intersecting the window from the left and from the right. It's easy to determine if there is overlapping commercial: it's enough to sort commercials in increasing order of the left end and then while iterating over them from left to right, keep the minimum value of a right end of a commercial. If when we pass the window $j$ and see that current value of the maximum right end is no less than $b_j$ then there exists a commercial overlapping our window and the value is equal to the $(r_i - l_i) \cdot c_i$. Among all commercials that lie inside our window we need the longest one. It can be done by similar but a bit harder manner. Let's use sweepline method. While passing through the end of the commercial $r_i$, let's assign in some data structure (like seg...

Полный текст и комментарии »

Codeforces Round #641 Orac and LCM Solution I noticed that many people were confused by the mathematics used in the soltuion of the editorial of this Div2.C question and decided to share with you my easy method for solving it. I use the property of distributivity of the lcm fucnction over gcd to simplify the solution. For three integers $ a, b, c$ we have - $ \gcd(lcm(a, b), lcm(a, c)) = lcm(a, \gcd(b, c))$ - $ lcm(\gcd(a, b), \gcd(a, c)) = \gcd(a, lcm(b, c)) $ Proof: [GCD and LCM Distribute Over Each Other](https://proofwiki.org/wiki/GCD_and_LCM_Distribute_Over_Each_Other) Hence for an array of integers, - $ \gcd(lcm(a_0, a_1), lcm(a_0, a_2) \dots lcm(a_0, a_n)) = lcm(a_0, gcd(a_1, a_2 \dots a_n)) $ - $ \gcd(lcm(a_1, a_2), lcm(a_1, a_3) \dots lcm(a_1, a_n)) = lcm(a_1, gcd(a_2, a_3 \dots a_n)) $ - $\dots$ $and$ $so$ $on$ Therefore, for every element of the array we can precalculate the $\gcd$ of its next elements. Then we can take the lcm of that precalculated value with the element and store it in a new arr...

Полный текст и комментарии »

Code Clash 2026 Editorial We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated! [A &mdash; Love of Equal Arrays](https://codeforces.me/gym/663466/problem/A) Idea: [user:nimish.agarwal.2006,2026-01-11]<br> Implementation: [user:nimish.agarwal.2006,2026-01-11] <spoiler summary="Hint"> For any index $i$, it is always possible to make $a_i = b_i$ in at most $2$ moves. </spoiler> <spoiler summary="Tutorial"> Now there are four possible cases for a fixed index $i$. 1) If $a_i = b_i$, then no operation is required. 2) If $a_i \bmod b_i = 0$, then we can multiply $b_i$ by $\frac{a_i}{b_i}$, and make $a_i$ and $b_i$ equal using one operation. 3) If $b_i \bmod a_i = 0$, then we can multiply $a_i$ by $\frac{b_i}{a_i}$, and make $a_i$ and $b_i$ equal using one operation. 4) Otherwise, we can multiply $a_i$ by $b_i$ and $b_i$ by $a_i$, making them equal in two operations. The answer is obtained by summing the minimum number ...

Полный текст и комментарии »

2022 Joint exam of 5 schools (GZEZ Round2) Editorial [A. Refreshed](https://codeforces.me/gym/104538/problem/A) ------------------ If we don't take the shortest path from $s$ to $t$ but instead detour to some vertices to gain health, we must pass through an edge with both endpoints having a sum of weights greater than 0. If we reach either vertex of such an edge, we can gain infinite health. We mark such vertices as infinite health vertices. So, either we take the shortest path from $s$ to $t$, or we take the shortest path from $s$ to an infinite health vertex, gain infinite health, and then walk to $t$. The second case can be maintained through up and down DP, which keeps track of the minimum health required to reach an infinite health vertex from each vertex. The first case is to find the prefix minimum value of the path from $s$ to $t$. It is easy to see that the prefix minimum value is either the entire path or the entire path excluding the vertex $t$. Otherwise, there must be infinite health on the path, which can b...

Полный текст и комментарии »

Разбор задач Codeforces Round #202 ### [problem:349A] В задаче требовалось выяснить, может ли кассир выдать сдачу всем посетителям кинотеатра, если билет стоит 25 рублей, у посетителей купюры номиналом 25, 50 и 100 и в кассе изначально нет денег. Рассмотрим 3 различных случая. - Если у посетителя 25 рублей, то сдачу ему давать не нужно. - Если у посетителя 50 рублей, то мы должны дать ему 25 рублей сдачи. - Если у посетителя 100 рублей, то мы должны дать ему 75 рублей сдачи. Это можно сделать двумя способами. 75=25+50 и 75=25+25+25. Заметим, что всегда выгодно попробовать сначала первый способ, а потом второй. Это верно потому, что купюры номиналом 25 рублей могут быть использован как для выдачи сдачи на 50 рублей, так и на 100 рублей, а сами купюры номиналом 50 рублей могут использоваться только для выдачи сдачи на 100 рублей. Таким образом решение – поддерживать количество купюр номиналом 25 и 50 рублей и при выдаче сдачи на 100 рублей действовать жадно – сначала пробовать выдать 25+50 рублей, а иначе 25+2...

Полный текст и комментарии »

LCM of all numbers in array Hello ! I have a problem that goes : Given $N$ positive integers $A_1, A_2, \dots, A_N$. Find $LCM(A_1, A_2, \dots, A_N)\text{ }(\text{mod } 1000000007)$. Constraint : $1\leq N \leq 10^4,$ $1\leq A_i \leq 10^9$ My approach : Use sieve to list all primes up to $M = \sqrt{A_{max}}$. For every prime $p$ up to $M$, divide each $A_i$ by $p$ as many time as possible (as long as $A_i$ is divisible by $p$), and note the largest exponent for each $p$. After every $A_i$ is 'reduced' (divided by all prime up to $M$), $A_i$ must be equal to $1$ or a prime greater than $M$. Note every distinct final result of $A_i$. This was done using `std::set`. To calculate $LCM(A_1, A_2, \dots, A_N)$, I used binary exponentiation to calculate the 'contribution' for every small prime $p \leq M$, and then multiply them with the 'contribution' for large prime, which is equal to the product of all distinct final result of $A_i$ 's. However, this approach yields TLE and I cannot figure out...

Полный текст и комментарии »

Editorial PRO-TEST Thank you everyone for participating in the PRO-TEST! ### [A &mdash; Harmendra's Helpline](https://codeforces.me/gym/701868/problem/A) #### **Prerequisites:** Number Theory, Math & Algebra <spoiler summary="Hint 1"> Try to make $\text{lcm}(c, d) = 1$. </spoiler> <spoiler summary="Hint 2"> What happens when $b = 1$? </spoiler> <spoiler summary="Solution"> We can solve this problem in $O(1)$ time by using a fixed constructive approach that works for any $n \ge 4$. Since we can choose any positive integers, we minimize the right side of the equation by setting $c = 1$ and $d = 1$, which makes $\text{lcm}(1, 1) = 1$. This simplifies our target condition to finding two numbers where $\gcd(a, b) = 1$ and their remaining sum is $a + b = n - 2$. To easily guarantee a GCD of $1$, we can fix $b = 1$, which leaves us with $a = n - 3$. Ultimately, the fixed tuple $(n - 3, 1, 1, 1)$ will always satisfy both the sum and the GCD-LCM constraints for any valid input. </spoile...

Полный текст и комментарии »

Competitive C++ Manifesto: A Style Guide # Competitive C++ Manifesto: A Style Guide There are many style guides for C++ out there, but we can't really use them as competitive programmers. We just want to write our code correctly as fast as possible! Trying to hack people here on codeforces, I realized there is a need for a style guide! Our goal is to write correct, fast, clear and consistent code. > #### Disclaimer > This is not a rulebook. You can integrate parts of it into your coding style. > Don't overthink it, especially during a contest! I'm going to use this guide for myself and to [teach my students](https://in.harbour.space/computer-science/modern-c-programming-hossein-yousefi/). I'm planning to make some good stuff in the future following these principles! Stay tuned! ## Compiler Make use of C++17. Use `-Wall -Wextra -Wshadow` flags for compilation, and try to eliminate all of the warning messages, this will prevent you from having some silly bugs. There are more debugging flags like `-fsanitize=un...

Полный текст и комментарии »

Solution Contest đầu vào CLB IT PTIT 2025 [A1. Hiệu lớn nhất (Easy)](https://codeforces.me/group/3lIrBW7byh/contest/618584/problem/A1) <spoiler summary="Solution"> Giả sử, cố định vị trí $a_j$ thì bạn cần duyệt tất cả những vị trí $a_i$ $(1 \le i \le j \le n)$, rồi tính $max(a_i - a_j)$. Nhưng độ phức tạp thuật toán sẽ là $O(n^2)$, quá xấu với giới hạn của đề bài. Để giảm thiểu độ phức tạp của thuật toán, với mỗi $a_j$, ta thấy $max(a_i - a_j) = max(a_i) - a_j$. Để nhanh chóng tìm được $max(a_i)$, bạn cần tính trước mảng pre, với $pre[i] = max(a_1, a_2, ..., a_i)$. </spoiler> <spoiler summary="Code"> ```cpp #include <bits/stdc++.h> using namespace std; const int maxN = 1e6 + 5; int a[maxN], pre[maxN]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = max(pre[i - 1], a[i]); } int res = 0; for (int i = 1; i <= n; i++) { res = max(res...

Полный текст и комментарии »

TheForces Rounds Editorials Here's the editorials of [TheForces Rounds](https://t.me/TheForcesOfficial): <spoiler summary="Round 1"> <spoiler summary="Problem A"> For a number $x$, as long as $2\le x$, it can be squared to any large number. For $0$ and $1$, the square of both numbers is equal to themselves. So just compare $0$ and $1$. <spoiler summary="Code"> ~~~ void elysia() { cin >> n; bool flag=true; for(int i=1;i<=n;++i) { cin >> a[i]; a[i]=min(a[i],2ll); if(i!=1&&a[i]<a[i-1]) flag=false; } if(flag) cout << "YES" << endl; else cout << "NO" << endl; } ~~~ </spoiler> </spoiler> <spoiler summary="Problem B"> Consider the number of times each $a_i$ is XOR in the answer. for $a_i$, calculated $i(n-i+1)$ times in the answer. Two same XOR will disappear, so checking is this an odd number then done. <spoiler summary="Code"> ~~~ void elysia() { int answer=0; cin >> n; for(int i=1;i<=n;++i) { cin >> a[i]; ...

Полный текст и комментарии »

Editorial for CodeHurdle Athlos 02 We want to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated! [Contest Link](https://codeforces.me/contestInvitation/c9482c2d71d0b5cdc04841221671e06b827c1e07) ### [A — Costly Divisibility](https://codeforces.me/gym/670769/problem/A) Writer: [user:amartya110,2026-01-19] <spoiler summary="Editorial"> In this case any $a[i]>=b[i]$ for all $(1<=i<=n)$, you can easily make a[i]%b[i]==0 by decreasing the value of a[i] or increase the value of b[i] with cost 0, and otherwise the cost is the absolute difference between a[i] and b[i]. </spoiler> <spoiler summary="Solution"> ```c++ #include <bits/stdc++.h> using namespace std; #define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define testcase int t; cin>>t; for(int i=0;i<t;i++) #define ll long long int ll lcm(ll a, ll b) { return (a / __gcd(a, b)) * b; } void solved(){ /*start*/ ll n; cin>>n; vecto...

Полный текст и комментарии »

Editorial of SPC Round 68 SPC Round 68 has been finished. Congratulations to all of the winners of this round. The standings of this round is :[here](https://toph.co/contests/training/j86aezg/standings) The problem set of this round is:[here](https://toph.co/contests/training/j86aezg) Editorial: ---------- ### A.Programmer Homecoming : Imagine three straight lines a, b, c. a = distance of (0,0) to pillar, b = distance of pillar to home, c = distance of (0,0) to home. These distances are euclidean. If the pillar is on the way to line c, then can't go home. If a + b = c then the pillar must belong to line c otherwise not. Time complexity :O(1) [code](https://ideone.com/NiKKUF) ### B.Love palindrome : According to the palindromic character we need to make equals of A[i] and A[n-i+1], (1 <= i <= n/2). All such pairs are unique. For, every n/2 pairs the cost will be minimum of their distance and x. Sum up all n/2 costs for final answer. Time complexity :O(n) [code](https://ideone.co...

Полный текст и комментарии »