You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:

  • 305 — search for 305, most probably it will find blogs about the Round 305
  • andrew stankevich contests — search for words "andrew", "stankevich" and "contests" at the same time
  • user:mikemirzayanov title:testlib — search containing "testlib" in title by MikeMirzayanov
  • "vk cup" — use quotes to find phrase as is
  • title:educational — search in title

Results

1.

expression

Last visit:  14 years ago
Registered:  14 years ago
2.
By MikeMirzayanov, 3 years ago, In English
Please, read this Hello, Codeforces. Friends. I apologize, but today I will be a bit chaotic and mix personal with public. It just happened that way, I'm sorry. Today, my mother passed away. It's hard for me to write this. Even just seeing it in text makes it feel like something from a nightmare. She was extraordinary. It's difficult for me to articulate it right now, but take my word for it. It felt like all the best qualities one could imagine in a mother converged in her. I don't know any other people so kind, sincere, non-judgmental, capable of love, listening, befriending, supporting, and taking joy in the world around them, and bringing joy to their loved ones. Mom, it's already hard without you, it feels empty. She had glioblastoma. It's an aggressive brain cancer that affects only a few people out of 100,000. I believe, I hope, that science will soon be able to tackle this disease. But for now, this diagnosis is a death sentence. Maybe some of you are or will be associated with medic...
any other forms of expression on contentious topics like national/ethnic conflicts, politics, religion, Please refrain from making posts, comments, or any other forms of expression on contentious topics

Full text and comments »

  • Vote: I like it
  • +6564
  • Vote: I do not like it

3.
By zscoder, history, 7 years ago, In English
[Tutorial] Generating Functions in Competitive Programming (Part 1) Hi everyone! Inspired by the recent [Codeforces Round 641](https://codeforces.me/contest/1349), I decided to write an introductory tutorial on generating functions here. I am by no means an expert in generating functions so I will write about what I currently know about them. [user:MiFaFaOvO,2020-05-15] has written a really interesting [blog](https://codeforces.me/blog/entry/76447) here on Codeforces about more advanced applications of generating functions, but I think there is no English tutorial on the basics of this topic yet (or at least on CP sites). Thus, I would like to share about this topic here. I plan to split this tutorial into two parts. The first part (this post) will be an introduction to generating functions for those who have never learned about them at all, and some standard examples and showcases of generating functions. The second part will be a collection of several applications of generating functions in CP-style problems. If you are already familiar with ge...
- x - x^2}$ Do you recognize the last expression? It is actually $\frac{1}{x}F(x)$ where $F(x)$ is, Do you recognize the last expression? It is actually $\frac{1}{x}F(x)$ where $F(x)$ is the OGF of

Full text and comments »

  • Vote: I like it
  • +1299
  • Vote: I do not like it

4.
By HosseinYousefi, 12 years ago, In English
C++ Tricks I see lots of programmers write code like this one: ~~~~~ pair<int, int> p; vector<int> v; // ... p = make_pair(3, 4); v.push_back(4); v.push_back(5); ~~~~~ while you can just do this: ~~~~~ pair<int, int> p; vector<int> v; // ... p = {3, 4}; v = {4, 5}; ~~~~~ [cut] [This](http://codeforces.me/blog/entry/10124) is a great C++11 tutorial for those who want to know more about C++11. #### 1. Assign value by a pair of {} to a container I see lots of programmers write code like this one: ~~~~~ pair<int, int> p; // ... p = make_pair(3, 4); ~~~~~ while you can just do this: ~~~~~ pair<int, int> p; // ... p = {3, 4}; ~~~~~ even a more complex `pair` ~~~~~ pair<int, pair<char, long long> > p; // ... p = {3, {'a', 8ll}}; ~~~~~ What about `vector`, `deque`, `set` and other containers? ~~~~~ vector<int> v; v = {1, 2, 5, 2}; for (auto i: v) cout << i << ' '; cout << '\n'; // prints "1 2 5 2" deque<vector<pair<in...
Regular expressions are useful tools in programming, we can define a regular expression by `regex

Full text and comments »

  • Vote: I like it
  • +971
  • Vote: I do not like it

5.
By tourist, history, 9 years ago, translation, In English
Hello 2018 -- Tutorial Here is the tutorial of Hello 2018. Enjoy! <spoiler summary="Modular Exponentiation"> Problem writer: [user:tourist,2018-01-08] [tutorial:913A] <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int n, m; scanf("%d %d", &n, &m); printf("%d\n", n >= 31 ? m : m % (1 << n)); return 0; } ~~~~~ </spoiler> </spoiler> <spoiler summary="Christmas Spruce"> Problem writer: [user:BudAlNik,2018-01-08] [tutorial:913B] <spoiler summary="C++ solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> p(n), deg(n); for (int i = 1; i < n; i++) { cin >> p[i]; p[i]--; deg[p[i]]++; } vector<int> sons_leaves(n); for (int i = 0; i < n; i++) { if (deg[i] == 0) { sons_leaves[p[i]]++; } } for (int i = 0; i < n; i++) { if (deg[i] > 0 && sons_leaves[i] < 3) { puts("No"); return 0; } } puts...
Problem writer: [user:BudAlNik,2018-01-08] [tutorial:913E], "); return 0; } ~~~~~ , ()) return a < b; return a.length() < b.length(); } struct Expression { int p, t; string e, Expression(string _e, int t_, int _p) : e(_e), t(t_), p(_p) {}, ])) { dp[mask][pr] = s; Expression e(s, mask, pr); q.insert(e); } }, bool operator < (const Expression& ex) const { if (ex.e == e) { if (t != ex.t) { return, set<Expression> q;, struct Expression { int p, t; string e;

Full text and comments »

Tutorial of Hello 2018
  • Vote: I like it
  • +463
  • Vote: I do not like it

6.
By adamant, history, 18 months ago, In English
Complex FFT is not as bad as you think ... Probably. Hi everyone! As some of you _might_ already know, I don't like NTT. Primary reasons for this are: - I don't like modular arithmetic optimizations (Montgomery, etc). - I don't like NTT mods, and prefer good, old $10^9+7$. - I do like algebra of complex numbers. But, to my regret, the overwhelming mainstream in modern competitive programming is NTT. Primary reasons are: - It's allegedly faster. - It needs less memory. - It has no precision issues. - People don't like algebra of complex numbers. There is nothing I can do about the last, but today I'll address the first 3. Optimizing complex FFT was on my mind for quite some time, but I didn't really work on it _that much_ until the [blog](https://codeforces.me/blog/entry/142063) by [user:Qwerty1232,2025-04-24] on optimizing NTT has dropped, which motivated me to actually put some serious effort into this. In this blog, we will primarily focus on optimizations that are specific to complex arithmetic...
The left-hand side in the expression above is, in fact, $|C'-C|_1$, the $L_1$[-norm](https

Full text and comments »

  • Vote: I like it
  • +731
  • Vote: I do not like it

7.
By zscoder, history, 7 years ago, In English
[Tutorial] Generating Functions in Competitive Programming (Part 2) Welcome to Part 2 of my tutorial on generating functions. The [first part](https://codeforces.me/blog/entry/77468) focused on introducing generating functions to those without any background in generating functions. In this post, I will demonstrate a few applications of generating functions in CP problems. Let us start with some relatively straightforward examples. Note: Unless stated otherwise, all computations are done modulo a convenient prime (usually $998244353$). Also, $[n]$ denotes the set $\\{1,2,...,n\\}$. ### Blatant Applications in Counting Problems **Problem.** [AGC 005 Problem F](https://atcoder.jp/contests/agc005/tasks/agc005_f) You have a tree $T$ with $n$ vertices. For a subset $S$ of vertices, let $f(S)$ denote the minimum number of vertices in a subtree of $T$ which contains all vertices in $S$. For all $1 \le k \le n$, find the sum of $f(S)$ over all subsets $S$ with $|S| = k$. Constraints: $n \le 2 \cdot 10^{5}$. <spoiler summary="Solution"> First, ...
the expression in **partial fractions**. Let, )x$. Then, $x = \frac{z}{1-y}$ and our expression becomes:, Let us focus on the expression $(1-y)[x^n]\frac{1}{(1-x)(1 - ye^{(1-y)x})}$ and keep in mind that, We can compute the first $n$ terms of the last expression in $O(n\log n)$ time, and we're done., })}$, which is exactly the same expression quoted in [user:Elegia,2020-05-17]'s post.

Full text and comments »

  • Vote: I like it
  • +518
  • Vote: I do not like it

8.
By maspy, history, 6 months ago, In English
On Improving Problem Statements Recently, I have often found myself somewhat concerned about the quality of problem statements on Codeforces. Of course, this may simply be due to some bias: perhaps I just happened to notice more such cases over the past few months. I also fully understand that writing and reviewing problem statements is a very difficult task. Even so, I feel that there is still room for improvement in several respects. In particular, I would appreciate it if more attention could be paid to the following points: * Finding and fixing typos before the contest, paying attention not only to the statement body but also to the input and sample sections. * Using the same expression as consistently as possible when referring to the same object or concept. * Avoiding undefined, problem-specific terminology as much as possible. * Checking whether technical terms are being used in a meaning different from their usual one. * Paying attention to potentially ambiguous expressions and arranging explanat...
also to the input and sample sections. * Using the same expression as consistently as possible when, statement body but also to the input and sample sections. * Using the same expression as consistently as

Full text and comments »

  • Vote: I like it
  • +443
  • Vote: I do not like it

9.
By -is-this-fft-, history, 4 years ago, In English
[Tutorial] FFT If I was a YouTuber, this would be the place where I fill the entire screen with screenshots of people asking me to make this. Anyway, not so long ago I gave a lecture on FFT and now [user:peltorator,2023-01-11] is giving away [free money](https://codeforces.me/blog/entry/110840), so let's bring this meme to completion. In this blog, I am going to cover the basic theory and (competitive programming related) applications of FFT. There is a long list of generalizations and weird applications and implementation details that make it faster. Maybe at some point I'll write about them. For now, let's stick to the basics. **The problem.** Given two arrays $a$ and $b$, both of length $n$. You want to quickly and efficiently calculate another array $c$ (of length $2n - 1$), defined by the following formula. $$c_k = \displaystyle \sum_{i + j = k} a_i \cdot b_j.$$ Solve it in $O(n \log n)$. First of all, why should you care? Because this kind of expression comes up in combinatorics a...
mentioned right at the beginning that this type of expression is common in formulas for counting, other kinds of convolutions, but this is the kind we care about here. Anyway, does theexpression for, First of all, why should you care? Because this kind of expression comes up in combinatorics all, Notice that this expression doesn't depend on $x$ at all (try to convince yourself that this is not

Full text and comments »

  • Vote: I like it
  • +436
  • Vote: I do not like it

10.
By cip999, 5 years ago, In English
Editorial of Global Round 15 We hope you liked the problems! Before we go ahead with the editorial, let us make some general comments about this round. Problems A, B, C, D, E, F are "div 2" problems, while problems G, H, I are meant to be solved by Grandmasters. Overall, our goal was to provide a problemset that could be enjoyable for a wide range of participants and such that the winner could solve all the problems. There were three big "jumps" in the difficlty gaps between consecutive problems. Problems A and B are meant to be easy, many contestants have the skills and the techniques to attack them (and, maybe, to solve them). Problems C, D, E, F are gradually harder but the difficulty gap between C and F is not as large as usual (and this is reflected in the score distribution). The same holds for problem G, H, I; the difficulty gap between G and I is relatively small (but there is a big score difference because coding I is much harder). Sadly, we discovered 14 minutes into the round that problem I...
Ask a query with all points. The result is a simple expression in terms

Full text and comments »

  • Vote: I like it
  • +533
  • Vote: I do not like it

11.
By -Morass-, history, 9 years ago, In English
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...
11070 UVA (5) //evaluation of expression, http://codeforces.me/contest/913/problem/E (5) //[NICE][EXPRESSION]

Full text and comments »

  • Vote: I like it
  • +428
  • Vote: I do not like it

12.
By Errichto, 7 years ago, In English
Bitwise operations for beginners You can watch my Youtube video ([link](https://www.youtube.com/watch?v=xXKL9YBWgCY&list=PLl0KD3g-oDOHpWRyyGBUJ9jmul0lUOD80)) with the same content as this blog. Anyway, enjoy. ### Introduction Let's learn bitwise operations that are useful in Competitive Programming. Prerequisite is knowing the binary system. For example, the following must be clear for you already. $$13 = 1 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1 = 1101_{(2)} = 00001101_{(2)}$$ Keep in mind that we can pad a number with leading zeros to get the length equal to the size of our type size. For example, `char` has $8$ bits and `int` has $32$. ### Bitwise AND, OR, XOR You likely already know basic logical operations like AND and OR. Using `if(condition1 && condition2)` checks if both conditions are true, while OR (`c1 || c2`) requires at least one condition to be true. Same can be done bit-per-bit with whole numbers, and it's called bitwise operations. You must know bitwise AND, OR and XOR, typed r...
, like bits `01` in the example above. An expression `x >> b` is equal to the floor of $\frac{x}{2^b, If there is no overflow, an expression `x << b` is equal to $x \cdot 2^b$, like here we had `(13

Full text and comments »

  • Vote: I like it
  • +206
  • Vote: I do not like it

13.
By Igorjan94, history, 9 years ago, In English
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...

Full text and comments »

  • Vote: I like it
  • +415
  • Vote: I do not like it

14.
By purplesyringa, history, 5 years ago, In English
Kapun's algorithm I'd like to share this one unpopular but awesome algorithm that I only heard a mention of once. Kapun's algorithm finds a hash collision for moduli as large as $10^{18}$. I know, we have *lots* of algorithms that do much better than that (and I'm writing an article on that at the moment, keep tuned), but Kapun's algorithm is really surprising in its simplicity. That its correctness is so difficult to prove is of more surprise even. Here we go. A polynomial hash of a string $s$ is defined as $$ H(s) = s_0 b^0 + s_1 b^1 + s_2 b^2 + \dots + s_{n-1} b^{n-1} \pmod M. $$ We want to find two strings with the same polynomial hash using only two characters: $0$ and $1$. We can reformulate this problem in another way. Let $a_i = b^i \mod M$, then we want to find two distinct subsets of $a$ with the same sum modulo $M$. Now *forget about the modulus*: let's just find two subsets with the same sum. Firstly, when is this possible? There are $2^n$ possible subsets and $n(M - 1) -...
find an expression of kind $\pm a_{i_1} \pm a_{i_2} \dots \pm a_{i_k} = 0$ for some $i$ and some signs, - If we have an expression with value $0$ at the moment, return this expression . - Otherwise, sort, The algorithm is as follows. Instead of finding two subsets, we will find an expression of kind, class DifferenceExpression(Expression): def __init__(self, a: Expression, b: Expression, class Expression: def __init__(self, value: int): self.value: int = value, class TrivialExpression(Expression): def __init__(self, value: int, info): super, def __eq__(self, rhs: "Expression | int"): if isinstance(rhs, int): return, def __gt__(self, rhs: "Expression"): return self.value > rhs.value, def __lt__(self, rhs: "Expression"): return self.value < rhs.value, def __ne__(self, rhs: "Expression"): return not (self == rhs), def __sub__(self, rhs: "Expression"): return DifferenceExpression(self, rhs)

Full text and comments »

  • Vote: I like it
  • +246
  • Vote: I do not like it

15.
By SanguineChameleon, 19 months ago, In English
Neowise Labs Contest 1 (Codeforces Round 1018, Div. 1 + Div. 2) Editorial [Sorry about problem H.](https://codeforces.me/blog/entry/142069) Thank you for understanding, and we hope you enjoyed the rest of the problems :D --- <h3>[problem:2096A]</h3> Idea: [user:SanguineChameleon,2025-04-20] <br> <spoiler summary="Step 1"> Create your own test cases and solve them! What can you observe? </spoiler> <spoiler summary="Step 2"> What is the length of the $n$-th stick? <spoiler summary="Answer"> - If $s_{n - 1} = \texttt{<}$, then $a_n = 1$, because the $n$-th stick must be shorter than all the other sticks. - If $s_{n - 1} = \texttt{>}$, then $a_n = n$, because the $n$-th stick must be longer than all the other sticks. </spoiler> </spoiler> <spoiler summary="Step 3"> Can we do something similar for the remaining sticks? <spoiler summary="Answer"> Yes! Remove the $n$-th stick, and then solve for the remaining $n - 1$ sticks. We can make similar observations about the $(n - 1)$-th stick. Then, remove the $(n - 1)$-th st...
Now the expression is of the form:

Full text and comments »

  • Vote: I like it
  • +242
  • Vote: I do not like it

16.
By -is-this-fft-, 5 years ago, In English
[Tutorial] Proving the inverse Ackermann complexity of Union-Find #### Introduction Most of us are familiar with the union-find data structure and the two optimizations one can do on it: _union by rank_ and _path compression_. Most tutorials will introduce these methods and state that if both optimizations are used, the complexity will be $\mathcal{O}((n + m) \alpha(n))$. Here, $n$ and $m$ are the number of vertices and queries respectively. What is $\alpha$? Generally, we are told that $\alpha$ is some mysterious function that grows very slowly: $\alpha(N) < 5$ where $N$ is the number of subsets of particles in the observable universe and whatnot. What it is is usually not clarified very much. And there is typically no proof (or intuition and other such justifications) as to why the complexity is like that: usually we're told that the complexity analysis is quite long and complicated. At the time of writing, both [cp-algorithms](https://cp-algorithms.com/data_structures/disjoint_set_union.html) and [Wikipedia](https://bit.ly/3EvnzrI) are like th...
Here I have to introduce the notation $\log^* n$. The expression $\log^* n$ denotes the number of

Full text and comments »

  • Vote: I like it
  • +448
  • Vote: I do not like it

17.
By adamant, history, 3 years ago, In English
Dirichlet convolution. Part 1: Fast prefix sum computations Hi everyone! Suppose that you need to compute some sum of a number-theoretic function that has something to do with divisors: $$\begin{gather} \sum\limits_{k=1}^n \varphi(k) = ? \\ \sum\limits_{k=1}^n \sum\limits_{d|k} d^2 = ?? \\ \sum\limits_{x=1}^n \sum\limits_{y=1}^x \gcd(x, y) = ?!? \end{gather}$$ As it turns out, such and many similar sums can be computed with Dirichlet convolution in $O(n^{2/3})$, and in this article we will learn how. Let $f(n)$ and $g(n)$ be two [arithmetic functions](https://en.wikipedia.org/wiki/Arithmetic_function). Let $F(n)$ and $G(n)$ be their prefix sums, that is $$\begin{matrix} F(n) = \sum\limits_{i=1}^n f(i), & G(n) = \sum\limits_{j=1}^n g(j). \end{matrix}$$ We need to compute a prefix sum of the [Dirichlet convolution](https://en.wikipedia.org/wiki/Dirichlet_convolution) $(f * g)(n)$. In this article, we will consider some general methods, and show how to do so in $O(n^{2/3})$ if we can compute prefix sums of $F(n)$ and $G(n)$ in ...
expression above, at least one of $i$ and $j$ must be less than $\sqrt n$. This allows us to rewrite the

Full text and comments »

  • Vote: I like it
  • +285
  • Vote: I do not like it

18.
By mohammedehab2002, history, 6 years ago, In English
Codeforces round #649 editorial ### [problem:1364A] Let's start with the whole array. If every element in it is divisible by $x$, the answer is $-1$; if its sum isn't divisible by $x$, the answer is $n$. Otherwise, we must remove some elements. The key idea is that removing an element that is divisible by $x$ doesn't do us any benefits, but once we remove an element that **isn't**, the sum won't be divisible by $x$. So let the first non-multiple of $x$ be at index $l$, and the last one be at index $r$. We must either remove the prefix all the way up to $l$ or the suffix all the way up to $r$, and we'll clearly remove whichever shorter. Code link: https://pastebin.com/j2Y8AJBA Alternatively, we can notice that this means the answer is either a prefix or a suffix, so we can simply bruteforce them all. ### [problem:1364B] TL;DR the answer contains the first element, last element, and all the local minima and maxima, where a local minimum is an element less than its 2 adjacents, and a local maximum is an e...
Let's look at the expression in the problem for 3 numbers. If $a>b$ and $b>c$ or if $a, expression will also have a $1$ because $p_i$ will make every single clause have a $1$. If it has a

Full text and comments »

  • Vote: I like it
  • +340
  • Vote: I do not like it

19.
By adamant, history, 3 years ago, In English
Stirling numbers with fixed n and k Hi everyone! In combinatorics, you often need to compute [Stirling numbers](https://en.wikipedia.org/wiki/Stirling_number) for various reason. Stirling numbers of the first kind count the number of permutations of $n$ elements with $k$ disjoint cycles, while Stirling numbers of the second kind count the number of ways to partition a set of $n$ elements into $k$ nonempty subsets. Besides that, they're often arise when you need to change between powers of $x$ and rising/falling factorials. There are three problems on Library Checker that go as follows: **[Library Checker &mdash; Stirling Number of the First Kind](https://judge.yosupo.jp/problem/stirling_number_of_the_first_kind)**. Given $N$, find $s(N, k)$ for $0 \leq k \leq N$. **[Library Checker &mdash; Stirling Number of the Second Kind](https://judge.yosupo.jp/problem/stirling_number_of_the_second_kind)**. Given $N$, find $S(N, k)$ for $0 \leq k \leq N$. **[Library Checker &mdash; Stirling Number of the First Kind (Fixed...
Expanded, the expression above transforms into the well-known explicit formula

Full text and comments »

  • Vote: I like it
  • +197
  • Vote: I do not like it

20.
By adamant, history, 3 years ago, In English
Evaluation and interpolation on geometric progression Hi everyone! Two problems were recently added to Library Checker: - **[Multipoint Evaluation (Geometric Sequence)](https://judge.yosupo.jp/problem/multipoint_evaluation_on_geometric_sequence)**. Given $f(x)$, find $f(ar^i)$ for the given $a, r$ and $0 \leq i < m$. - **[Polynomial Interpolation (Geometric Sequence)](https://judge.yosupo.jp/problem/polynomial_interpolation_on_geometric_sequence)**. Given $f(ar^i) = y_i$ for $0 \leq i \leq n$, find $f(x)$ of degree $n$. **Note**: We can divide or multiply the $k$-th coefficient of initial/resulting polynomial by $a^k$, so we may assume $a=1$. Today we'll learn how to solve both of them in $O(n \log n)$. [cut]<hr> ### Evaluation at $r^k$ Well, the first one is also known as [chirp Z-transform](https://en.wikipedia.org/wiki/Chirp_Z-transform) and it's by now standard (see [here](https://cp-algorithms.com/algebra/polynomial.html#chirp-z-transform) or [here](https://codeforces.me/blog/entry/83532)). It uses the fact th...
us to greatly simplify this expression. First of all, we should notice that now we're able to, Huh?! The coefficient near $x^i$ in this expression is the value of $g(x) = \sum\limits_{j=0}^n y, Let's divide each side by $Q_n(x) = \prod\limits_{j=0}^n (x-z^j)$, then the expression rewrites as, With this, the expression above rewrites as

Full text and comments »

  • Vote: I like it
  • +147
  • Vote: I do not like it

21.
By TeaTime, 2 years ago, In English
Counting perfect matchings Thanks to [user:t.ravnushkin,2024-09-27] for helping in writing contents of this blog. Thanks to [user:Alexdat2000,2024-09-27] for proof-reading and to [user:bashkort,2024-09-27] for announcing the month of blog posts. Even though I have started writing this blog before the announcement it would have probably been left in a trash bin due to my laziness. # Introduction Matching is a beloved topic throughout competitive programming community due to its simple nature and fun applications. Matchings are not only useful in graph theory, but are also essential in topics such as game theory, partially ordered sets and combinatorics. In this blog we are gonna talk about less known applications of the subject. The main goal of the blog is explaining the intuition behind being able to associate the number of some combinatorial species to the amount of perfect matchings and understanding when it is possible to efficiently compute their counts. The blog mainly consists of two parts: ...
permutations of size $n$. So our expression boils down to summation over all permutations. Next we define, Another expression we are going to encounter today is permanent of a matrix $A$:, As a reminder determinant is the following expression associated with a matrix $A$:, Notice that the expression looks very similar to the one of determinant however we do not multiply

Full text and comments »

  • Vote: I like it
  • +353
  • Vote: I do not like it

22.
By Zlobober, 14 years ago, translation, In English
Anti-hash test. Hi everyone! I wan't to share some interesting fact about how we're going to challenge almost every solution, that uses polynomial hashes modulo 2^64. We'll hack any solution, regardless of it's base (!), the only thing we need, that it's using int64 with overflows --- like many coders write hashing. Keywords: Only today, only for you, ladies and gentlemen: we're gonna challenge [user:Petr,2012-07-19]'s solution in problem [problem:7D] from Codeforces Beta Round #7! Is it interesting? Welcome reading after the cut. [cut] Firstly, for the most impatient of you. Here's the source of the generator: ~~~~~ const int Q = 11; const int N = 1 << Q; char S[N]; for (int i = 0; i < N; i++) S[i] = 'A' + __builtin_popcount(i) % 2; // this function in g++ returns // number of ones in binary representation of number i ~~~~~ Let's try solutions of two CFBR #7 winners on this test: Petr Mitrichev's and Vlad Epifanov's. [user:vepifanov,2012-07-18] solution doe...
Let's consequentially take factors in this expression off the brackets:

Full text and comments »

  • Vote: I like it
  • +272
  • Vote: I do not like it

23.
By Sammarize, 11 years ago, translation, In English
Short instruction of formulas writing (translation) In this post I want to describe in short how to write a formulas on Codeforces. In fact it is short introduction to the markup language $\TeX$ used on Codeforces. Three important rules. ---------------------- Foremost rule: formula me place in dollars (`$`), as well as in parentheses. Another important rule: if you want to apply some operation to some group of symbols it is necessary to form the block using the curly braces. For instance, `2^x+y` = $2^x+y$, but `2^{x+y}` = $2^{x+y}$. Third rule &mdash; for perfectionists. For traffic economy Codeforces print simple formulas by usually text. Sometimes it is not very pretty: `C_{x_i+y_i-2}^{x_i-1}` = $C_{x_i+y_i-2}^{x_i-1}$. Is this case you can add command `\relax` at the beginning of the formula. Then the formula is guaranteed to be beautiful: `\relax C_{x_i+y_i-2}^{x_i-1}` = $\relax C_{x_i+y_i-2}^{x_i-1}$. Arithmetic operations. ---------------------- Addition and subtraction can be written ordinary symbols + and -. Mu...
brackets around a large expression small, you can make them suitable size, written before the left, \limits_{k = 0}^nx^k`. If the brackets around a large expression small, you can make them suitable

Full text and comments »

Tags tex
  • Vote: I like it
  • +380
  • Vote: I do not like it

24.
By adamant, history, 4 years ago, In English
Shift of polynomial sampling points Hi everyone! Previously, I had a [blog](https://codeforces.me/blog/entry/99646) on how, given $s$ and a polynomial $f(x)$, to compute coefficients of the polynomial $f(x+s)$. Today we do it in values space. Consider the problem **[Library Judge &mdash; Shift of Sampling Points of Polynomial](https://judge.yosupo.jp/problem/shift_of_sampling_points_of_polynomial)**. In this problem, you're given $s$ and the values $f(0), f(1), \dots, f(n)$ of a polynomial of degree at most $n$ and you need to find $f(s), f(s+1), \dots, f(s+n)$. In particular, I used this to generate test cases for [problem:1817C], there might be other applications too. [cut]<br> #### General linear recurrence shift _If you have further questions about something here, please refer to [this blog](https://codeforces.me/blog/entry/100158)_ Let's, for a moment, consider even more generic problem now. Let $f_0, f_1, \dots$ be a linear recurrence, such that $$ f_m = a_1 f_{m-1} + \dots + a_{n+1} f_{m...
In particular, it also gives a much simpler and more concise expression for $R(x)$ from above:, Thus, the full expression for $R(x)$ is

Full text and comments »

  • Vote: I like it
  • +179
  • Vote: I do not like it

25.
By arvindf232, 4 years ago, In English
Codeforces Round #822 (Div.2) Editorial Thank you for your participation! [1734A &mdash; Select Three Sticks](https://codeforces.me/contest/1734/problem/A) ------------------ We first sort the array $a$ in non-decreasing order. Denote the indices of the elements that we choose from $a$ to be $x$, $y$, and $z$, where $1 \le x < y < z \le n$, and the final value (after performing the operations) of the concerned elements to be $v$. The minimum required number of operations is then $|a_x-v|+|a_y-v|+|a_z-v|$. It is well-known that such expression attains its minimum value when $v$ is the median of $a_x$, $a_y$, and $a_z$. Since the array $a$ has already been sorted, it is best to assign $v$ to be $a_y$. Our expression then becomes $|a_x-a_y|+|a_y-a_y|+|a_z-a_y|=(a_y-a_x)+0+(a_z-a_y)=a_z-a_x$. We would like to minimize the value of $a_z$, which implies $z$ should be as small as possible since $a$ is sorted. It is clear that taking $z=y+1$ would minimize the value of the expression. Similarly, we can show that we ...
r_2$, $c_1 \neq c_2$, $b \not\equiv 0 \pmod n$, and $n$ is a prime, this expression must be nonzero, such expression attains its minimum value when $v$ is the median of $a_x$, $a_y$, and $a_z$. Since, Our expression then becomes $|a_x-a_y|+|a_y-a_y|+|a_z-a_y|=(a_y-a_x)+0+(a_z-a_y)=a_z-a_x$. We would, We have thus reworded the statement into evaluating the follow expression:

Full text and comments »

  • Vote: I like it
  • +169
  • Vote: I do not like it

26.
By adamant, history, 21 month(s) ago, In English
Geometric meaning of LP duality Hi everyone! Recently, linear programming (LP) duality was brought up in a Discord server, and it made me think again about how, whenever it is introduced, it's most often _very_ poorly motivated. Some examples that I've seen include: - Directly deriving it from general Lagrange duality (which I did myself in the past, and I like this method, but it's not best for LP); - Giving some vague economics-based explanation in terms of goods quantities and costs; - Making a very handwavy argument about approximating the target function with constraints; - Simply proving it symbolically without giving a good explanation to what and why we're doing. After some thinking, I would like to share a geometric interpretation to LP duality, that I think should very intuitively and directly explain what's the meaning of our actions, and why does it actually deliver the same result (and not just an upper bound) as the primal problem. **Tl;dr**. Both primal and dual LP problems find the **su...
Let's recall how the feasible set $S$ is defined. The expression $Ax \leq b$ is simply a short-hand

Full text and comments »

  • Vote: I like it
  • +164
  • Vote: I do not like it

27.
By adamant, history, 4 years ago, In English
Unlabeling combinatorial species (cycle index series) Hi everyone! In my [previous blog](https://codeforces.me/blog/entry/103979), I wrote about how generating functions can be used to enumerated labeled species. In this blog, I want to continue the topic by writing about how one can account for different kinds of symmetries when counting different combinatorial structures. Ultimately, we will end up deriving and hopefully understanding the analogue of [Pólya enumeration theorem](https://en.wikipedia.org/wiki/Pólya_enumeration_theorem) in species. Difficulty: ★★★★☆ Prerequisites: - Familiarity with combinatorial species (see my [prev. blog](https://codeforces.me/blog/entry/103979)), OR - Very good intuition with enumerative combinatorics, genfuncs and recap below. I will try to use plain language rather than formulas as much as possible, as it seems to be the preferred format for readers. ## Recap Below is a very brief recap of the most important things from the previous article. I tried to keep it as informal as p...
The results above also yield simplified expression for $Z(S_n)$:

Full text and comments »

  • Vote: I like it
  • +177
  • Vote: I do not like it

28.
By adamant, history, 4 years ago, In English
Combinatorial species: An intuition behind generating functions Hi everyone! The usage of generating functions is quite common in competitive programming these days. But it seems to happen so, that they're mostly presented as a way to simplify formal manipulation with polynomial coefficients, rather than something meaningful. But there actually is a meaning to all of this, and today I'm going to shed a light on it. Alongside the blog post we'll uncover the combinatorial meaning of - The addition $F(x)+G(x)$, - The multiplication $F(x)G(x)$, - The exponent $\exp F(x)$, - The logarithm $\log F(x)$, - The sum of the infinite geometric progression $\frac{1}{1-F(x)}=1+F(x)+F^2(x)+\dots$, - The general composition $F(G(x))$ for the generating functions $F(x)$ and $G(x)$ and the underlying structures they represent. ### Prerequisites - Basic notion of set theory (cardinality of sets, mappings, bijections, cartesian product, disjoint union, etc); - Polynomials and formal power series (representation, convolution formula, power seri...
The expression above provides the combinatorial meaning to $\exp F(x)$ and $\log F(x)$ operations

Full text and comments »

  • Vote: I like it
  • +380
  • Vote: I do not like it

29.
By cry, 2 years ago, In English
Codeforces Round 979 Editorial Below is a timeline of the changes made to the round from start to finish. I hope this can depict what setting a contest is actually like for aspiring problemsetters. Please give me feedback about this in the comments. What else about the round would you like to know? Was this helpful? <spoiler summary="Round Timeline"> To denote problems, I will use quotes to denote the number of problems proposed for that postion so far (e.g. A' represents the first A proposed for the round, A'' represents second A proposed, etc). If the problem is in the final set, then it will be **bolded**. For dates, I will use the american standard notation (mm/dd). Also, I will not go in detail about why problems were rejected/unused because they might appear in the future. 8/11: [contest:1998] has just concluded and [user:sum,2024-10-18] has shipped himself off to college and won't have time due to <s>attending frat parties</s> his studies. I invite [user:vgoofficial,2024-10-18] to problemset with m...
To compute $\text{ways}(x, y)$, we can use the Vandermonde identity to simplify theexpression:

Full text and comments »

  • Vote: I like it
  • +206
  • Vote: I do not like it

30.
By adamant, history, 3 years ago, In English
Useful substitutions with generating functions Hi everyone! Today I would like to write about some identities that might come handy when using generating functions to solve competitive programming problems. I will also try to include some useful examples about them. #### Some notation For brevity, we will sometimes skip the specific bounds in indexed sums, meaning that the summation happens among all _valid_ indices. Please also read the information below if you're not familiar with generating functions, or want to brush up on some aspects. <spoiler summary="Definitions and notation"> Let's briefly recall that, for a sequence $a_0, a_1, \dots$, it's **ordinary generating function** (OGF) is defined as a formal power series $$ F(x) = \sum\limits_k a_k x^k, $$ and its **exponential generating function** (EGF) is defined as $$ F(x) = \sum\limits_k a_k \frac{x^k}{k!}. $$ Generating functions are used because it's very simple to represent convolutions with them. For two sequences $a_0, a_1, \dots$ and $b_...
Similar to $F_m(x)$, it is possible to find the _exact_ expression for, $$ \frac{1}{1-x} = 1+x+x^2+\dots $$ This expression is also the consequence of the binomial, But the expression above assumes that the sequence is infinite. In our particular example, however, Here we used the identity $f_{m+1} - f_m = f_{m-1}$ to simplify the expression. Now, we can compute, This allows us, whenever we have a binomial coefficient in our expression, to substitute it with, expression exactly instead of truncating modulo $t^{d+1}$: $$ H(t+1) = \frac{1}{1-r}\frac{1-\frac

Full text and comments »

  • Vote: I like it
  • +182
  • Vote: I do not like it

31.
By maspy, history, 3 years ago, In English
FPS Composition and Compositional Inverse Hello. I am Japanese and have been publishing some articles within the Japanese-speaking community for some time now. This is my first attempt at translating one of my Japanese explanatory articles into English. (This is also the first CodeForces blog for me). The theme is the computation of formal power series composition and compositional inverse. - FPS Composition and Compositional Inverse - [(PART 1) Compositional Inverse and Power Projection](https://maspypy.com/fps-composition-and-compositional-inverse-part-1-compositional-inverse-and-power-projection) - [(PART 2) Composition Algorithm via Transposition Principle](https://maspypy.com/fps-composition-and-compositional-inverse-part-2) A method to improve the known computational complexity for this theme was introduced by [user:noshi91,2024-04-24] in March 2024. - https://noshi91.hatenablog.com/entry/2024/03/16/224034 - https://arxiv.org/abs/2404.05177 ([user:noshi91,2024-04-24] and [user:Elegia,2024-04-2...

Full text and comments »

  • Vote: I like it
  • +241
  • Vote: I do not like it

32.
By adamant, 11 months ago, In English
Caveats of using optimize("Ofast") with target("avx2") Hi everyone! As you may know, it is often recommended to put these lines in your header: ```cpp #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2") ``` And they're usually great!<sup>[1]</sup> Well, until they aren't. For last 2-3 days I was riddled with the issue that [CP-Algorithms Library](https://lib.cp-algorithms.com) would perform very well on Library Checker, but whenever I tried to also apply it on Codeforces, it will fail to speed up the code, and sometimes would even make it much slower. As I finally figured out the cause, I'd like to write a blog about it, so that other people don't waste as much time. Mitigating these issues improved my running time on [problem:1975G] from **1530 ms** in [submission:316602668] to **203 ms** in [submission:352602775]. ##### Tl'dr See the "Takeaway" section at the bottom. [cut]<br> ##### Example problem I will reproduce the issue on a simple example: <hr> **[problem:911G]**: You are given an...

Full text and comments »

  • Vote: I like it
  • +274
  • Vote: I do not like it

33.
By adamant, history, 3 years ago, In English
MacMahon's master theorem Hi everyone! Mandatory orz to ~Elegia,2023-12-04 whose [blog](https://blog.csdn.net/EI_Captain/article/details/108900963) introduced me to MMT as an elegant approach to prove Dixon's identity. Today, I would like to write about MacMahon's master theorem (MMT). It is a nice result on the intersection of combinatorics and linear algebra that provides an easy proof to some particularly obscure combinatorial identities, such as the **Dixon's identity**: $$ \sum\limits_k (-1)^k \binom{a+b}{a+k} \binom{b+c}{b+k} \binom{c+a}{c+k} = \binom{a+b+c}{a,b,c}. $$ Besides that, MMT has large implications in Quantum Physics, which we will hopefully discuss. For now, let's formulate MMT. <hr> **MMT**. Let $\mathbf A = [a_{ij}]_{n\times n}$, $\mathbf X = \operatorname{diag}(x_1,\dots,x_n)$, $\mathbf t = (t_1,\dots,t_n)$, $\mathbf x = (x_1,\dots,x_n)$ and $\mathbf k = (k_1,\dots,k_n) \geq 0$. Then, $$ \boxed{[\mathbf t^\mathbf k] \prod\limits_{i=1}^n \left(\sum\limits_{j=1}^n a_{ij} t_j...
Consider the expression $\det(\mathbf I - \mathbf B)$ without taking its inverse:, where the expression under the determinant is the $(i,j)$-th element of the matrix. For $G_i

Full text and comments »

  • Vote: I like it
  • +111
  • Vote: I do not like it

34.
By adamant, history, 5 years ago, In English
Moment-generating functions, inversions and q-analogs Hi everyone! Today I want to write about the inversions in permutations. The blog is mostly inspired by the problem С from [Day 3](http://karelia.snarknews.info/index.cgi?data=macros/day&menu=index&head=index&sbname=2022w&class=2022w&round=03) of 2022 winter Petrozavodsk programming camp. I will also try to shed some light on the relation between inversions and $q$-analogs. #### Key results Let $F(x)=a_0+a_1x+a_2x^2+\dots$, then $F(e^x)$ is the exponential generating function of $$b_i = \sum\limits_{k=0}^\infty a_k k^i.$$ In other words, it is a [moment-generating function](https://en.wikipedia.org/wiki/Moment-generating_function) of the parameter by which $F(x)$ enumerates objects of class $F$. **Motivational example**: The generating function of permutations of size $n$, enumerated by the number of inversions is $$F_n(x) = \prod\limits_{k=1}^n \frac{1-x^k}{1-x}.$$ The moment-generating function for the number of inversions in a permutation of size $n$ is ...
meaningful expression for OGF or EGF of $d_n(k)$ where powers of $x$ traverse through $n$ rather, some expression with the new parameter $q$ such that it is identical to the initialexpression as $q, this expression, we get, -Hadamard transform), while the second expression is the $q$-analog of or-convolution (Möbius transform, From this expression, we may derive the so-called $q$-factorial:, So, the explicit expression for $G_n(x)$ is, This expression should already be familiar to us, as with $q \to e^x$ it is the moment-generating

Full text and comments »

  • Vote: I like it
  • +156
  • Vote: I do not like it

35.
By adamant, history, 5 years ago, In English
Theoretical grounds of lambda optimization Hi everyone! This time I'd like to write about what's widely known as "Aliens trick" (as it got popularized after 2016 IOI problem called [Aliens](https://ioinformatics.org/files/ioi2016problem6.pdf)). There are already some articles about it here and there, and I'd like to summarize them, while also adding insights into the connection between this trick and generic Lagrange multipliers and Lagrangian duality which often occurs in e.g. linear programming problems. Familiarity with a [previous blog](https://codeforces.me/blog/entry/98524) about ternary search or, at the very least, definitions and propositions from it is expected. Great thanks to [user:mango_lassi,2022-01-01] and [user:300iq,2022-01-01] for useful discussions and some key insights on this. Note that although explanation here might be quite verbose and hard to comprehend at first, the algorithm itself is stunningly simple. Another point that I'd like to highlight for those already familiar with "Aliens tr...

Full text and comments »

  • Vote: I like it
  • +286
  • Vote: I do not like it

36.
By adamant, history, 5 years ago, In English
Fast polynomial composition Hi everyone! Today I want to describe an efficient solution of the following problem: <hr> **[Composition of Formal Power Series](https://judge.yosupo.jp/problem/composition_of_formal_power_series)**. Given $A(x)$ and $B(x)$ of degree $n-1$ such that $B(0) = 0$, compute $A(B(x)) \pmod{x^n}$. <hr> The condition $B(0)=0$ doesn't decrease the generality of the problem, as $A(B(x)) = P(Q(x))$, where $P(x) = A(x+B(0))$ and $Q(x) = B(x) - B(0)$. Hence you could replace $A(x)$ and $B(x)$ with $P(x)$ and $Q(x)$ when the condition is not satisfied. Solutions that I'm going to describe were published in Joris van der Hoeven's [article](https://www.sciencedirect.com/science/article/pii/S0747717102905626) about operations on formal power series. The article also describes a lot of other common algorithms on polynomials. It is worth noting that Joris van der Hoeven and David Harvey are the inventors of the breakthrough $O(n \log n)$ [integer multiplication algorithm](https://hal.archi...
For this expression, it generally holds that

Full text and comments »

  • Vote: I like it
  • +133
  • Vote: I do not like it

37.
By adamant, history, 5 years ago, In English
Lagrange interpolation and partial fraction decomposition Hi everyone! Today I'd like to write yet another blog about polynomials. Specifically, I will cover the relationship between polynomial interpolation and Chinese remainder theorem, and I will also highlight how it is useful when one needs an explicit meaningful solution for partial fraction decomposition. [cut]<br> #### Lagrange interpolation It's quite well-known that the system $$\begin{cases}P(x_0) = y_0, \\ P(x_1) = y_1, \\ \dots \\ P(x_n) = y_n\end{cases}$$ has a unique solution $P(x)$ among polynomials of degree at most $n$. A direct way to prove that $P(x)$ exists is through Lagrange's interpolation. To have a better grasp of it, let's recall that $P(x) \equiv P(x_0) \pmod{x-x_0}$, thus system becomes $$\begin{cases}P(x) \equiv y_0 \pmod{x-x_0}, \\ P(x) \equiv y_1 \pmod{x-x_1}, \\ \dots \\ P(x) \equiv y_n \pmod{x-x_n}.\end{cases}$$ From the Chinese remainder theorem follows that $P(x)$ is unique modulo $Q(x) = (x-x_0)\dots(x-x_n)$ and is explicitly given ...
their connection to Lagrange interpolation. To begin with, let's look on this expression in the case, It is strikingly similar to the Lagrange interpolation expression, from which we may derive that

Full text and comments »

  • Vote: I like it
  • +171
  • Vote: I do not like it

38.
By adamant, history, 4 years ago, In English
Solving AGC 058 D with multivariate generating functions Hi everyone! Today, I participate in AtCoder contest, which I quite rarely do. Of course, my performance was quite poor, but I stumbled with quite nice idea along the way. To those who didn't read it, the problem goes as follows: **[AGC 058 &mdash; Yet Another ABC String](https://atcoder.jp/contests/agc058/tasks/agc058_d)**. How many ternary strings are there such that they contain exactly $A$ characters `a`, exactly $B$ characters `b` and exactly $C$ characters `c`, and do not have any sub-string that is a cyclic shift of `abc`? My approach is very different from the one in the editorial, and seems insightful to me, so I decided to share it in detail. Besides, I can't reject the [request](https://codeforces.me/blog/entry/105924?#comment-943163) by [user:Um_nik,2022-08-15] to explain it further :D [cut]<br> ### Walks on finite automata We may construct a directed graph, such that each edge is marked by `a`, `b` or `c`, and so that the string is valid if and only i...
_Note that this is also one of common approaches to construct a regular expression for given DFA._

Full text and comments »

  • Vote: I like it
  • +163
  • Vote: I do not like it

39.
By ashmelev, history, 8 years ago, translation, In English
Codeforces Round #491 (Div.2), Editorial [problem:991A] <spoiler summary="Editorial"> There are 4 groups of students &mdash; those who visited only the first restaurant, who visited only the second, who visited both places and who stayed at home. One of the easiest ways to detect all the incorrect situations is to calculate number of students in each group. For the first group it is $A-C$, for the second: $B-C$, for the third: $C$ and for the fourth: $N-A-B+C$. Now we must just to check that there are non-negative numbers in the first three groups and the positive number for the last group. If such conditions are met the answer is the number of students in the fourth group. ~~~~~ int n1 = a - c; int n2 = b - c; int n3 = c; int n4 = n - n1 - n2 - n3; if (n1 >= 0 && n2 >= 0 && n3 >= 0 && n4 > 0) cout << n4; else cout << -1; ~~~~~ In general you are recommended to view [inclusion–exclusion principle](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle). Moreover the limitatio...
length of expression of $x$ is not greater than 4. Now lets iterate through $x$ among found, of integers $s[d]$ which can be represented by an expression of length $d$. The standard containers, other terms are expressions containing `*` and/or `^`. Each expression (not a number) contains at, such representation at most one multiplier is a number. Including that the expression can contain

Full text and comments »

  • Vote: I like it
  • +91
  • Vote: I do not like it

40.
By adamant, history, 3 years ago, In English
Solving the "simple math problem" with generating functions Hi everyone! Some time ago the following "simple math problem" was shared in a Discord chat: ![ ](/predownloaded/30/8c/308c36b754707a330621953da962c687755ad3f2.png) As a lover of simple math problems, I couldn't just pass by this problem. It turned out much harder than any other genfunc problem that I solved before, as the structure of the answer depends on the parity of $n$ and $m$, and it's not very natural to track it through genfuncs. It took me few months, I even called for help from higher powers (i.e. sent a pm to [user:Elegia,2023-06-11]) but I finally have a solution that I somewhat like. [cut]<hr> #### Finding a closed-form genfunc First of all, it's really inconvenient to sum up from $0$ to $\lfloor m/2 \rfloor$ or $\lfloor n/2 \rfloor$. What we can do is to introduce variables $a=n-2j$ and $b=m-2i$, after which the expression under the sum changes to $$ \binom{i+j}{j}^2 \binom{a+b}{a}. $$ As we want to sum it up over all $i,j,a,b$ such that $a + 2j = n...
the same expression in the denominator., -y)(1+x-y)(1-x+y)(1+x+y) = 1-2(y^2+x^2)+(y^2-x^2)^2, $$ meaning that it is exactly theexpression, Since the second function in the product only depends on $x^2$ and $y^2$, we have anexpression of, expression should be $$ (1-x-y)(1+x-y)(1-x+y)(1+x+y), $$ meaning that the numerator must be $$ (1+x-y

Full text and comments »

  • Vote: I like it
  • +205
  • Vote: I do not like it

41.
By wuhudsm, history, 16 months ago, In English
Codeforces Round 1040 (Div. 1, Div. 2) Editorial Thank you for participation and we hope you enjoy this round :) <spoiler summary="How did you find the contest?"> - Great: - Good: - Average: - Bad: - Trash: </spoiler> <spoiler summary="Which problem is your most favourite?"> - D2A: - D2B: - D1A: - D1B: - D1C1: - D1C2: - D1C3: - D1D: - D1E: - D1F1: - D1F2: </spoiler> <spoiler summary="Which problem you hate the most?"> - D2A: - D2B: - D1A: - D1B: - D1C1: - D1C2: - D1C3: [likes:favorite,2039E3_...
### 3) Exact expression

Full text and comments »

  • Vote: I like it
  • +118
  • Vote: I do not like it

42.
By Qwerty1232, 19 months ago, In English
Making NTT convolution 10x faster with avx2 > Text is also available on [github pages](https://piskareviv.github.io/blog_aux_ntt_1/) (formatting may look a bit cleaner there) > Thanks [user:alexxela12345,2025-05-05] for reviewing this blog Hello everyone! I want to share some of my thoughts and experiments on vectorizing NTT. I prefer NTT to real-valued FFT because of the imprecision of the latter. I use `avx2` because it is the most advanced vector extension supported by the majority of modern online judges (including Codeforces), as of 2024. And I have no idea how many bugs (already found two) and how much UB my code contains, at least it passes some kind of tests. ### Benchmark info All the benchmarks are performed on my `Ubuntu 22` `Intel i5-1135g7` laptop. I execute `cpupower frequency-set -d 3.0ghz -u 3.0ghz` before benchmarks to (attempt to) fix CPU frequency for better accuracy. Code is available at [github](https://github.com/piskareviv/blog_aux_ntt_1). You can try running all the benchmarks o...
$, we will focus on computing $A(x)B(x) \bmod (x^n - 1)$ for a given $n$. Such expression is also

Full text and comments »

  • Vote: I like it
  • +366
  • Vote: I do not like it

43.
By sidhant, 7 years ago, In English
Tutorial on Zeta Transform, Mobius Transform and Subset Sum Convolution **Pre-requisite**: Go through the Zeta/SOS DP/Yate's DP blog [here](https://codeforces.me/blog/entry/45223) **Source**: This blog post is an aggregation of the explanation done by [user:arjunarul,2019-12-26] in this [video](https://youtu.be/UOTCTbm1NrQ?list=PLi0ZM-RCX5nsTc2Z6woHr5qoF6n3b-thO), a comment by [user:rajat1603,2019-12-26] [here](https://codeforces.me/blog/entry/57250?#comment-409117) and the paper on [Fast Subset Convolution](http://people.csail.mit.edu/rrw/presentations/subset-conv.pdf) **Notation**: 1. set $s$ and mask $s$ are used interchangeably meaning the same thing. 2. $a \setminus b$ would mean set subtraction, i.e subtracting set $b$ from set $a$. 3. $|s|$ refers to the cardinality, i.e the size of the set $s$. 4. $\sum_{s' \subseteq s} f(s')$ refers to summing function $f$ over all possible subsets (aka submasks) $s'$ of $s$. **Aim**: Given functions $f$ and $g$ both from $[0, 2^n)$ to integers. Can be represented as arrays $f[]$ and $g[]$ r...
**Intuition**: The expression

Full text and comments »

  • Vote: I like it
  • +168
  • Vote: I do not like it

44.
By adamant, history, 4 years ago, In English
Lagrange inversion theorem Hi everyone! There is a concept that is sometimes mentioned [here](https://codeforces.me/blog/entry/77284?#comment-622525) and [there](https://codeforces.me/blog/entry/77551). The [Lagrange inversion theorem](https://en.wikipedia.org/wiki/Lagrange_inversion_theorem). Let $x = f(y)$. We want to solve this equation for $y$. In other words, we want to find a function $g$ such that $y = g(x)$. The Lagrange inversion theorem gives an explicit formula for the coefficients of $g(x)$ as a formal power series over $\mathbb K$: $$ \large k[x^k] g(x) = [x^{-1}] f^{-k} $$ In a special case $y = x \phi(y)$, that is $f(y) = \frac{y}{\phi(y)}$, which is common in combinatorics, it can also be formulated as $$ \large k[x^k] g(x) = [x^{k-1}] \phi^k $$ Finally, to avoid division by $k$ one may use (see the [comment](https://codeforces.me/blog/entry/104184?#comment-925505) by [user:Elegia,2022-06-25]) the following formula: $$ \large [x^k]g(x) = [x^{-2}] f' f^{-(k+1)}, $...
As it stands with generating functions, we're more interested in finding some expression for $g(x, It is possible to get a simpler expression for such cases., The expression on the right only has coefficient near $T^{n-1}$ when $k$ divides $n-1$, in which

Full text and comments »

  • Vote: I like it
  • +101
  • Vote: I do not like it

45.
By box, history, 6 years ago, In English
[Tutorial] Square root decomposition and applications A brief introduction into the applications of square root decomposition ================== Square root decomposition is the process of separating a structure of size $O(N)$ into $O(\sqrt{N})$ "blocks" of size $O(\sqrt{N})$ each, in a way that aids manipulation of the entire structure. Square root decomposition is extremely versatile. Some of its most well-known use cases are: - answering queries on a static array, with methods such as Mo's algorithm or block precomputation - "lazy" brute force modifications, where it is easy to query an entire block, but tag pushing isn't obvious - separating objects based on a threshold, when there exists both an $O(x)$ algorithm and an $O(n/x)$ algorithm In this tutorial we will walk through multiple types of square root decomposition. Answering queries on a static array, offline (Mo's algorithm) --- Consider a problem where we are asked to find the answer for certain intervals $[l,r]$. We can't quickly compute the answer for an ar...
but $p(x,y)$ takes $O(n^2)$ time to calculate. Consider transforming the $A$ expression to

Full text and comments »

  • Vote: I like it
  • +272
  • Vote: I do not like it

46.
By EnDeRBeaT, 2 years ago, In English
Tutorial: Stealing the coolest debug feature from Rust # Introduction Rust is a quite popular programming language with a lot of different takes on how to write good code. Some people use it in competitive programming with varying success, but in general, C++ is the king. That doesn't mean that we can't take great ideas from this language, and one of Rust's shining jewels is it's macro system. Describing why it is better than "find and replace" thing we have in C++ is not the topic of this blog. We are here to steal from Rust, and today we will steal one of the coolest utilities for a competitive programmer: `dbg!` macro! # dbg! The `dbg!` macro in Rust has simple functionality: it evaluates the expression, prints it's to `stderr` and **returns it**. Last part is very, **very** useful, and you will see why. Example: ~~~~~ let a = 2; let b = dbg!(a * 2) + 1; // ^-- prints: [src/main.rs:2:9] a * 2 = 4 assert_eq!(b, 5); ~~~~~ Look, we evaluated `a * 2` mid expression and `b` still became `5`. Isn't that cool? ...
assert_eq!(b, 5); ~~~~~ Look, we evaluated `a * 2` mid expression and `b` still became `5`. Isn't, feature? We can print an expression, an expression in another expression, hell, we can even inject, this expression will be returned. If something like `dbg(x, y)` is called, `__VA_OPT__` will be, # dbg! The `dbg!` macro in Rust has simple functionality: it evaluates the expression, prints it's, It is very easy to obtain expression as a string literal in C++:, On the basic level this function just prints the expression and its value (well it also prints

Full text and comments »

  • Vote: I like it
  • +184
  • Vote: I do not like it

47.
By qwexd, 2 months ago, In English
Codeforces Round 1121 (Div. 2) Editorial # Codeforces Round 1121 — Editorial Thanks for participating! ### [problem:2264A] Problem by [user:qwexd,2026-09-13]. <spoiler summary="Hint"> Look at the elements that are not in the right position. Which of them must be selected? Can selecting any other element help? </spoiler> <spoiler summary="Solution"> Every element that is not in the right position has to be selected; otherwise, it never moves. Selecting an element that is already in the right position cannot help. For it to stay correct after the reversal, it has to be paired with itself, because its value occurs nowhere else in the permutation. Thus it can only be the middle selected element, and removing it changes nothing. So, if the array is already sorted, choose any one element. Otherwise, select exactly the misplaced elements and reverse them. The answer is `YES` if this sorts the array, and `NO` otherwise. If the misplaced positions are listed from left to right, the reversal pairs the...
Try to make an expression for $n!$ as a warm-up , Try to use round and division to make an expression which is $0$ or $1, of the expression are well optimized, even writing constants naively in the form $(n+n+\dots+n)/n, which we replace with $1$. Here `[n>=2]` is an indicator expression that should output $1$ if the, - Use a bigger DP table $DP_{i,j}$, for $0\leq j<4$, which calculates a small-lengthexpression for, Note that $10\,000$ looks like a lot of characters for an expression, but for $n$ up to $50$, due, So now our goal has shifted to building an indicator expression `[n>=x]` for a given constant $x

Full text and comments »

  • Vote: I like it
  • +149
  • Vote: I do not like it

48.
By adamant, history, 5 years ago, In English
Polynomials and roots of unity Hi everyone! Today I'd like to write a bit on the amazing things you can get out of a power series by putting roots of unity into its arguments. It will be another short story without any particular application in competitive programming (at least I don't know of them yet, but there could be). But I find the facts below amazing, hence I wanted to share them. You're expected to know some basic stuff about the discrete Fourier transform and a bit of linear algebra to understand the article. [cut]<br> #### Bisections To begin with, let's start with the most simple non-trivial system of roots of unity. That is, with $\\{1, -1\\}$. Let $f(x)$ be a formal power series of $x$. If you represent it as $f(x)=f_0(x^2)+x f_1(x^2)$, you might note that $$ \begin{matrix} f_0(x^2) = \frac{f(x)+f(-x)}{2},& f_1(x^2) = \frac{f(x)-f(-x)}{2x}. \end{matrix} $$ The functions $f_0(x^2)$ and $xf_1(x^2)$ are called the **bisections** of $f(x)$. As you see, they're closely related to ...
Putting it in the expression above, we get, expression for the multisections knowing only $f(x)$. And it turns out, it is possible to do so.

Full text and comments »

  • Vote: I like it
  • +72
  • Vote: I do not like it

49.
By Wild_Hamster, history, 11 years ago, translation, In English
Codeforces #308 (Div. 2) Editorial [problem:552A] In this problem we can get AC with many solutions: 1) With every new rectangle we will add his area to the result, so for each line $x_1,y_1,x_2,y_2$ we will add to answer $(x_2-x_1+1)*(y_2-y_1+1)$ Time complexity $O(n)$. 2) We can just do all, that is written in the statement: create an array and with each new rectangle we can just increment every element inside rectangle. In the end we can just add all elements inside this array. Time complexity $O(n*x*y)$ [C++ code](http://ideone.com/uFAzzC) [user:Wild_Hamster,2015-06-19] [Java code](http://ideone.com/9FPeh9) [user:Wild_Hamster,2015-06-19] [Python code](http://ideone.com/kIXn7c) [user:Zlobober,2015-06-19] [problem:552B] We can find out a formula for this problem: for $n < 10$ answer will be $n = n - 1 + 1 = 1*(n+1)-1$; for $n < 100$ answer will be $2*(n-9) + 9 = 2*n - 9 = 2*n - 10 - 1 + 2 = 2*(n+1)-11$; for $n < 1000$ answer will be $3*(n-99) + 2*(99-9) + 9 = 3*n - 99 - 9 = 3*n...
between one sign $*$ and the end of expression. For convenience we will add in the begin ofexpression, After that we can iterate all possible pairs of signs $*$ and count the expression with putting, We can use two variables $x$ and $y$ to count the value of expression, in the begin $x=0,y

Full text and comments »

  • Vote: I like it
  • +67
  • Vote: I do not like it

50.
By dmkozyrev, history, 8 years ago, translation, In English
[Tutorial] Rolling hash and 8 interesting problems [Editorial] **UPD**: while I was translating this post from Russian to English, [user:dacin21,2018-07-06] wrote his post, more advanced, [link](http://codeforces.me/blog/entry/60442). I hope that my post will help beginners, but in my post more rough estimates. And in Russia we call **rolling hashes** as a **polynomial hashes**. Hello, codeforces! This blogpost is written for all those who want to understand and use polynomial hashes and learn how to apply them in solving various problems. I will briefly write the theoretical material, consider the features of the implementation and consider some problems, among them: 1. Searching all occurrences of one string of length $n$ in another string length $m$ in $O(n + m)$ time 2. Searching for the largest common substring of two strings of lengths $ n $ and $ m $ $(n \ge m) $ in $O((n+m \cdot log(n)) \cdot log(m))$ and $O(n \cdot log(m))$ time 3. Finding the lexicographically minimal cyclic shift of a string of length $ n $ in $ O(n \cdo...
length $len$ by **equality**, including **substrings of another string**, since theexpression $p, this sequence, we have in mind the result of calculating the following expression:, _Note_. If you think about interpreting the expression, then we match the sequences ${a_0, a_1

Full text and comments »

  • Vote: I like it
  • +239
  • Vote: I do not like it

51.
By Zhtluo, history, 2 years ago, In English
Guessforces Bestforces — How I Guessed My Way to GM ![Screenshot](https://zhtluo.com/cp/img/guessforces-bestforces/screenshot.png) *It turns out that randomly guessing works in Div. 1 too...* I have reached GM thanks to **randomly guessing**. **Ask me anything!** Since I have already argued in theory [how randomly guessing helps CF rating](https://codeforces.me/blog/entry/12687), I figured that I might as well compile a list of problems I guessed on my way to GM, to give some empirical evidence to all esteemed grandmasters before my rating falls off. So let us get started! ## [1975D &mdash; Paint the Tree](https://codeforces.me/contest/1975/problem/D) *Just solve the problem manually and claim it is the best solution.* Surely *it is.* <spoiler summary="Spoiler"> After playing a bit with the two pieces I found that I always make them collide. Fortunately, it suffices to randomly guess that the red piece and the blue piece will first travel to meet each other and then traverse the tree. I still have no idea why ...
After writing out the expression for a few terms, just randomly guess

Full text and comments »

  • Vote: I like it
  • +163
  • Vote: I do not like it

52.
By Geothermal, history, 7 years ago, In English
AtCoder Beginner Contest 144 English Solutions #A &mdash; 9x9 We can simply directly implement the procedure given in the problem. Print $AB$ if $A$ and $B$ are less than $10$ and $-1$ otherwise. One particularly fast way to do this is to use the ternary operator, which takes a boolean expression and two values as inputs and returns the first value if the expression is true and the second value otherwise. In C++, this looks like $\texttt{A < 10 && B < 10 ? A*B : -1}$. Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc144/submissions/8146605) --- #B &mdash; 81 Since we're only considering pairs of numbers from one through nine, we can simply iterate over every pair of numbers from one to nine and check if each pair multiplies to $N$. As soon as we find such a pair, we output Yes and exit the program. If we reach the end of the loop, we can then print No, since we've checked every possible pair and found that none of them work. Notice that we could also iterate over all number...
operator, which takes a boolean expression and two values as inputs and returns the first value if the

Full text and comments »

  • Vote: I like it
  • +95
  • Vote: I do not like it

53.
By Dardy, history, 6 years ago, In English
[Tutorial] Catalan Numbers and Catalan Convolution Catalan Numbers is a well known sequence of integers that appear in combinatorics, there is a chance that you might have run into such counting problems and you might have even solved them with DP without realizing that they are a known sequence. Here is a problem to get us started. ### Binary Trees Count Find the count of different binary trees with $n$ nodes, we'll denote to that by $C_n$. This can be solved by observing the substructure of the problem: ![binary tree](/predownloaded/db/de/dbde9fa6024b3b59c37bbc1fa9e8a76c0f12fd21.png) From the root, the left subtree $a$ can be _any_ binary tree of size $x$, the right subtree $b$ can be _any_ binary tree of size $y$, such that $x+y=n-1$ (as we took one node as the root). With the base case at $C_0=1$ as the empty tree is a valid tree of size $0$. This directly gives us the answer by the following recurrence relation: (Segner's recurrence relation) $$ C_{n+1} = \displaystyle\sum_{i=0}^{n}{C_i C_{n-i}}, n \geq 0; C_0=1 $$ ...
free to derive it using combination expansion, hint: expand the expression $\frac{C_n}{C_{n-1}}$)

Full text and comments »

  • Vote: I like it
  • +347
  • Vote: I do not like it

54.
By adamant, history, 4 years ago, In English
Unexpected application of cosines Hi everyone! This blog is inspired by some contestant solutions to [problem:104234F]. In short, problem asks you to find a polynomial such that $A(x_i) = y_i$ for several given pairs $(x_i, y_i)$, and the coefficients of $A(x)$ read the same left-to-right and right-to-left (i.e., they form a palindrome). The intended solution utilizes the fact that for such polynomial, it always holds that $$ A(x) = x^n A(x^{-1}), $$ as $x^n A(x^{-1})$ is exactly the polynomial $A(x)$ with reversed coefficients (assuming the degree is $n$). #### Representing palindromic polynomials with polynomials in $x+\frac{1}{x}$ Several solutions from contestants, however, relied on a different criterion for $A(x)$. Rather than using the identity above, participants found out that palindromic polynomials can always be represented as $$ A(x) = x^{d} B\left(x+\frac{1}{x}\right), $$ when its degree $2d$ is even, or as $$ A(x) = x^{d} (1+x) B\left(x+\frac{1}{x}\right), $$ when its degr...
Now, we're only interested in the real part of the said expression, hence the one with even $j

Full text and comments »

  • Vote: I like it
  • +111
  • Vote: I do not like it

55.
By adamant, history, 4 years ago, In English
Fourier transform on groups. Part 2: Characters Hi everyone! Consider the following problem. You're given two arrays $a_1, a_2, \dots, a_{n!}$ and $b_1, b_2, \dots, b_{n!}$. You need to compute the array $c_1, c_2, \dots, c_{n!}$, such that $$ c_k = \sum\limits_{i \circ j = k} a_i b_j, $$ where $i \circ j$ denotes the composition of the $i$-th and the $j$-th lexicographically smallest permutations of $n$ elements. Generally, typical approach to such things would be to escape into space in which the convolution corresponds to the component-wise product of two vectors, and then to transform back into initial space. For example, with the summation rule being $i + j \equiv k \pmod n$, it is well known that the corresponding transform is exactly the discrete Fourier transform of vectors $a_i$ and $b_j$. But with more generic groups, things may be much more complicated. This is the second blog in a series of blog posts explaining it. * **[Fourier transform on groups. Part 1: Irreducible representations](https://code...
For this, denoting $f_g = f(g)$, consider the formal expression, The expression above can be treated as an inner product $\langle \theta, \chi \rangle$ on the, The right hand side of the expression above can be perceived as a linear transform $z^g$ defined on

Full text and comments »

  • Vote: I like it
  • +29
  • Vote: I do not like it

56.
By adamant, history, 4 years ago, In English
Partitions and pentagonal number theorem Hi everyone! In today's blog I'd like to write about the theorem that allows to efficiently solve the following problems: - What is the number of partitions of a non-negative number $n$ for $n \leq 10^5$? - What is the number of partitions of a non-negative number $n$ for $n \leq 10^5$, so that no summand repeats $d$ or more times? - What is the number of partitions of a non-negative number $n$ for $n \leq 10^5$, so that no summand is divisible by $d$? - **[HackerEarth &mdash; Perfect Permutations](https://www.hackerearth.com/de/problem/algorithm/perfect-permutations-september-clash/)**: What is the number of permutations of length $n$ with $k$ inversions for $k \leq n \leq 10^5$? - **[problem:102354E]**: Let $\phi = \frac{9}{10} \cdot \frac{99}{100} \cdot \frac{999}{1000} \cdot \dots$, what is the $k$-th digit of $\phi$ for $k \leq 10^{18}$? - **[SNSS-2018 Round 5 &mdash; Investment Portfolio](https://contest.yandex.ru/contest/8703/problems/C/)**: You have $2n$ dollars and ...
Indeed, after expanding the expression into a sum of monomials, $k$-th multiplier will contribute

Full text and comments »

  • Vote: I like it
  • +172
  • Vote: I do not like it

57.
By reirugan, 12 months ago, In English
Codeforces Round 1065 (Div. 3) Editorial I hope you all enjoyed the contest! Special thanks to - [user:djm03178,2025-11-18] for suggesting the inclusion of C1, and for helping with test writing on all problems, especially F - [user:satyam343,2025-11-18] for helping me solve H - [user:Dominater069,2025-11-18] for providing the idea for one of the solutions to E - [user:Intellegent,2025-11-18] for providing one of the proofs for the solution to D, and for providing the idea for one of the solutions to F <spoiler summary="Rate the contest!"> <spoiler summary="Quality"> - Excellent contest - Good contest - Average contest - Bad contest - Horrible contest </spoiler> <spoiler summary="Difficulty"> - Trivial contest - Easy contest - Average contest - Hard contest - Impossible contest </spoiler> </spoiler> #### [...
The given expression is equal to $|(a_2 - a_1) + (a_3 - a_2) + \dots, , the remaining blank elements do not affect the given expression, so we can set them all to be zero

Full text and comments »

  • Vote: I like it
  • +129
  • Vote: I do not like it

58.
By wuhudsm, history, 22 months ago, In English
[Plan] Rewrite of Some Editorial Due to my poor understanding ability, I can't totally understand official editorials of some problems, even after got AC. So I plan to rewrite some of the editorials. Some principles: 1. Divide and conquer. Divide a large, hard problem into several smaller, easier problems. 2. For ease of understanding, use visual expressions as much as possible. 3. The shorter the better. If you have any other problems you'd like me to rewrite the editorial for, feel free to let me know in the comments. Also, I believe writing an editorial with your own understanding is a great way to make progress. Let's go. [1.CF #749 F](https://codeforces.me/contest/1586/problem/F) Rating: $2500$ <spoiler summary="Attempt and Insight"> Assume that the number of colors $c$ is fixed. Let $mx[i][j]$ represent the length of the continuous path ending at node $i$ with color $j$. How do we construct $mx$? Let's try some approaches. For the connected component formed by the first $k$ ...

Full text and comments »

  • Vote: I like it
  • +97
  • Vote: I do not like it

59.
By Endagorion, 12 years ago, In English
Codeforces Round #300 Editorial (+challenges) As usual, a challenge comes with every problem. I tried not to repeat the mistakes of my previous editorials and made sure that all challenges have a solution =) (except for the _italics_ parts that are open questions, at least for me). Go ahead and discuss them in the comments! General questions about problems and clarification requests are welcomed too. **UPD**: I added codes of my solutions for all the problems. I didn't try to make them readable, but I believe most part of them should be clear. Feel free to ask questions. [problem:538A] Let me first clarify the statement (I really wish I didn't have to do that but it seems many participants had trouble with the correct understanding). You had to erase exactly one substring from the given string so that the rest part would form the word `CODEFORCES`. The (somewhat vague) wording `some substring` in the English translation may be the case many people thought that many substrings can be erased; still, it is beyond my understa...

Full text and comments »

Tutorial of Codeforces Round 300
  • Vote: I like it
  • +312
  • Vote: I do not like it

60.
By awang11, 22 months ago, In English
Codeforces Round 996 (Div. 2) Editorial Hope you enjoyed the problems! **UPD 1:** Added implementations! **UPD 2:** It seems my wording for the solution to C is not the best, and it is causing some confusion. I've updated it to be better! **UPD 3:** Implementation links didn't work for some reason, so I've just added the code directly. [problem:2055A] <spoiler summary="Hint 1"> Look at the distance between the frogs. </spoiler> <spoiler summary="Solution"> Notice that regardless of how the players move, the difference between the numbers of the lilypads the two players are standing on always alternates even and odd, depending on the starting configuration. Then, the key observation is that exactly one player has the following winning strategy: * Walk towards the other player, and do not stop until they are forced onto lilypad $1$ or $n$. For instance, if Alice and Bob start on lilypads with the same parity, Bob cannot stop Alice from advancing towards him. This is because at the start of Alice's ...
Write the expression for the number of moves for a given order, efficiently compute the expression in Hint 2?

Full text and comments »

  • Vote: I like it
  • +142
  • Vote: I do not like it

61.
By adamant, history, 4 years ago, In English
How to sum up all natural numbers (and their non-negative powers) Hi everyone! _This is the blog for infinite sums. For finite sums of power, see [here](https://codeforces.me/blog/entry/60756)._ As everybody knows, [it is true](https://en.wikipedia.org/wiki/1_+_2_+_3_+_4_+_...) that $$ \boxed{1+2+3+4+\dots = -\frac{1}{12}} $$ Moreover, [it is widely known](https://en.wikipedia.org/wiki/1_+_1_+_1_+_1_+_...) that $$ \boxed{1+1+1+1+\dots = -\frac{1}{2}} $$ Historically, it seems that the result was first discovered by Ramanujan, who described it in one of his letters to G. Hardy as $$ \text{``If I tell you this you will at once point out to me the lunatic asylum as my goal''} $$ In this blog, I want to explain how this summation could be easily done with the competitive programmer's favorite tool: generating functions. Moreover, I will explain how to compute the infinite sums of form $1^k + 2^k + 3^k + 4^k + \dots = S_k$ for any non-negative integer $k$. [cut]<br> ##### All your problems will go away with this si...
expression expands as a Laurent series

Full text and comments »

  • Vote: I like it
  • +68
  • Vote: I do not like it

62.
By s-sireneva, history, 2 years ago, In English
Bypassing Cloudflare's "bot fight mode", or how I wrote a working JS interpreter in a weekend... ...for fun and absolutely no profit. # Part 0. Introduction It so happened that I haven't written any Codeforces contest in a few months. When I was logging into my account to leave a comment under some post (I ended up not doing that), I noticed something weird:[cut]&#32; `Please wait. Your browser is being checked. It may take a few seconds...` After about half a second, this screen disappeared, and the normal login page showed up. But since I'm maintaining a CLI client for Codeforces, this immediately caught my attention with an intrusive question: did Mike break my client once again? After firing up a shell and trying to login, the answer was clear: yes, he did. # Part 1. "What the heck?" At the first glance, this screen looked suspiciously like the Cloudflare "Checking your browser" screen. This would have been a dead end, as even "professional" scrapers prefer using headless browsers and such instead of relying on "Cloudflare bypasses". The idea of the CLI tool ...
these, the function `parse_postfix_expression` first tries to parse a "simple" expression (which is, ** than what's requested should not be part of the expression. This way, when parsing operators of, This expression concatenates 5 32-bit hex numbers, so the result is a 160-bit hash, I assumed, `e /f/g` is "e divided by f, then by g". `/f/g` is a regular expression literal.

Full text and comments »

  • Vote: I like it
  • +214
  • Vote: I do not like it

63.
By Endagorion, 12 years ago, In English
Codeforces Round #295 Editorial (now with bonuses!) We would like to thank the testers of this round's and Winter Computer Camp olympiad's problems: [user:alger95,2015-03-02], [user:thefacetakt,2015-03-02], [user:adamant,2015-03-02], [user:dragonic,2015-03-02], [user:Who179,2015-03-02], [user:ASverdlov,2015-03-02]. Make sure to comment if you find any mistakes. **UPD**: I've just remembered to put up the usual challenges for the problems. So, here they go. [problem:520A] Idea: [user:Endagorion,2015-03-02] Preparation: [user:Endagorion,2015-03-02] To check that every letter is present in the string we can just make a boolean array of size 26 and for every letter set the corresponding variable to TRUE. In the end check that there are 26 TRUEs. That is an $O(n)$ solution. Also don't forget to change all letters to lowercase (or all to uppercase). To make all the letters lowercase, one could use standard functions, like `tolower` in Python. Also, it is known that the letters from `a` to `z` have consecutive ASCII numbe...

Full text and comments »

  • Vote: I like it
  • +151
  • Vote: I do not like it

64.
By pwned, 4 years ago, In English
A purple's message to Mike (About Problem Coincidences) Dear [user:MikeMirzayanov,2023-02-12], Although you want the round to be rated, I, [user:pwned,2023-02-12], believe the contest should remain unrated. Making the round rated would be unfair. For instance, participants who blatantly copied the code for F would have a massive advantage. Problem F was worth a staggering 3250 points at the beginning of the round, outweighing the entirety of ABC! Meanwhile, participants who got the first four problems would have their positive delta stolen. At the extreme end, the users who focused on problem F, thinking it is simple, will have an even more pronounced disadvantage. Consider those who skipped D to look at F. These users hastily scribbled on their scratch papers, trying to find a swift solution. They would soon discover that they were attempting a 3100-rated monstrosity! Codeforces should not use an author's intentions to decide whether a round must be rated. Instead, we must view the situation from a participant's perspective. An un...

Full text and comments »

  • Vote: I like it
  • +395
  • Vote: I do not like it

65.
By tokitsukaze, 5 years ago, In English
Codeforces Round #789 Editorial [problem:1678A] Idea: [user:tokitsukaze,2022-05-08] <br /> Prepare: [user:tokitsukaze,2022-05-08] <spoiler summary="Tutorial"> We observe that when there is $0$ in the sequence, it is optimal to choose $0$ and any number other than $0$ for each operation. Therefore, when there is $0$ in the sequence, let $cnt$ be the number of $0$s, the answer is $n - cnt$. Otherwise, when $0$ does not exist in the sequence, there are two situations: 1. When there exist two equal numbers in the sequence, we can perform the operation $1$ time to convert it into the situation of having $0$ in the sequence. So the answer must be $n$. 2. When all numbers in the sequence are distinct, we can perform the operation $2$ times to convert it into the situation of having $0$ in the sequence. So the answer must be $n + 1$. </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main(){ int t; scanf("%i",&t); while(t--){ int n; scan...
So the expression of the final answer can be derived from the summation formula of the arithmetic

Full text and comments »

  • Vote: I like it
  • +115
  • Vote: I do not like it

66.
By lior5654, 5 years ago, In English
[Tutorial] Solving a 3300 | Codeforces Round #773 (Div. 1) Problem E — Special Positions Hello Codeforces! (Long Post!) Introduction ------------------ As I've recently solved my first ever $\ge$ 3000 rated problem (3300) on Codeforces &mdash; [Codeforces Round #773 (Div. 1) Problem E &mdash; Special Positions](https://codeforces.me/problemset/problem/1641/E) and the solution that I came up with is different than the one presented in the official editorial, I thought that it will be valuable to the community if I share my approach. ![ ](https://i.imgur.com/toIoJG4.jpeg) Note that problem solving is a complicated & creative process. In the editorial, I show clean steps to reach the final solution, but the jump between each step is not always trivial (and sometimes hard!). Reaching this solution involved a large amount of drawings, observations, calculations & mistakes. There's no magic trick (at least to my knowledge :) ). Alright, enough introduction, let's get started! (click "The Editorial" below this line in order to be able to view the editorial) ...
$\mathbb{E}[\text{the expression}] = \displaystyle\sum\limits_{i=0}^{m-1}{(\displaystyle\sum, **This expression feels like polynomial multiplication!**, Notice that the coefficient of $a_i$ in the expression, is the distance of it's index to the, Recall the expression of interest: $\displaystyle\sum\limits_{i=0}^{n-1}{(a_i \cdot \min\limits_{j, So, simply multiplying $Y(x)$ & $K(x)$ gives us exactly the expression we need, but with $0 \le i,j, The expression we desire to find the expected value of can simply expressed as the sum of all of, The idea is that the expected value of the expression should be equal to the sum for each pcost, This expression seems much more friendly! Note that $A(x)$, $B(x)$ & $W(x)$ values for all valid $x, We can recover the answer to the original problem using the fact that E[the expression] = E[the, expression dependent on $T$, where we randomly select $T$ out of all non-empty subsets of $P$ (with

Full text and comments »

  • Vote: I like it
  • +123
  • Vote: I do not like it

67.
By awang11, history, 8 months ago, In English
Codeforces Round 1085 (Div. 1 + Div. 2) Editorial <center> <table class="tex-tabular bordertable" style="border-left: none; border-right: none; border-top: 1px solid; border-bottom: 1px solid; border-collapse: collapse;"> <tbody> <tr> <td class="tex-tabular-text-align-center" style="border-left: none; border-right: none; border-top: none; border-bottom: none;"> <span class="tex-font-size-small"> <span class="tex-font-style-it"> <a href="https://www.youtube.com/watch?v=HCYKLnT0UNU">Trophy Presentations — Asuka Ota, Ryo Nagamatsu, Mario Kart Wii</a> </span> </span> </td> </tr> </tbody> </table> </center> **UPD 1:** added hints, problem credits, more specific acknowledgements and some remarks. Implementations are on the way, sorry for making y'all wait! **UPD 2:** Implementations are finally here. [problem:2207A] Author: [user:awang11,2026-03-09] Preparers: [user:awang11,2026-03-09], [user:IceSerpent,2026-03-09] Anal...
Write an expression for the ending danger level in terms of the night

Full text and comments »

  • Vote: I like it
  • +146
  • Vote: I do not like it

68.
By NetSpeed1, 23 months ago, In English
Codeforces Global Round 28 Editorial [problem:2048A] Author: [user:Little09,2024-12-19] <spoiler summary="Hint 1"> How much does the number decrease when we remove two consecutive $3$ s? </spoiler> <spoiler summary="Tutorial"> ### [problem:2048A] When we transform $\overline{x33y}$ into $\overline{xy}$ (where $x$ and $y$ are decimal numbers), the actual value changes from $10^{p+2} \cdot x + 33 \cdot 10^p + y$ to $10^p \cdot x + y$. The decrease is $99 \cdot 10^p \cdot x + 33 \cdot 10^p$. It is easy to see that $33 \mid (99 \cdot 10^p \cdot x + 33 \cdot 10^p)$. Therefore, we can replace the operation of removing two consecutive $3$ s with a series of $-33$ operations. Hence, we only need to determine whether $x$ can be reduced to $0$ using a series of $-33$ operations, which is equivalent to checking whether $x \bmod 33$ equals zero. </spoiler> [problem:2048B] Author: [user:wsyear,2024-12-19] <spoiler summary="Hint 1"> If the permutation is sufficiently long, what is the maximum number of leng...
Consider the positions where the extremes are reached in the expression

Full text and comments »

  • Vote: I like it
  • +128
  • Vote: I do not like it

69.
By -is-this-fft-, history, 5 years ago, In English
[Math note] On the relationship between gf and me Today, I want to talk a bit about the relationship between two well-known methods for calculating the $n$-th term of a linear recurrence: **g**enerating **f**unctions and **m**atrix **e**xponentiation. More specifically, I want to explore how these two things are related to one another or how they can be thought of as variants of one another. This blog shouldn't be treated as a tutorial. If you know these algorithms, I doubt that I can teach you to solve some new problem in this blog. Rather, I'm kind of thinking out loud. I think it is a good idea to try to reflect and find connections between different things we have learned. This kind of thinking tends to strengthen the understanding of both methods and makes it easier to improve upon them to solve problems. And I'm sure that what I'm about to present is already quite well-known to some people ;). But when I realized this it was cool to me, so I want to share it. **Problem.** You have two sequences $b_1, b_2, \l...
function method pretty closely mirrors this matrix expression, with the caveat that instead of calculating, The expression $U^{-1} \Lambda^n U$ heavily reminds of similar matrices and diagonalization

Full text and comments »

  • Vote: I like it
  • +313
  • Vote: I do not like it

70.
By Elegia, history, 22 months ago, In English
More on D-Finite Functions I: Theories Hello everyone. Several years ago [user:jqdai0815,2025-01-03] released a [blog](https://codeforces.me/blog/entry/76447) on the topic of D-Finite functions. In this blog, I will introduce some more theories, and show the relation between some CP problems. Also, I found out that what I show is like opening Pandora's box: it provides some new ways to solve problems, but they also somehow prevent us from really understanding them. Therefore, I'll also talk about some of my personal critiques on this topic. Since this blog is quite long, I'll divide it into several parts. This is the first part. ## Appetizer We start with this toy problem. **$n$-King Problem.** Given $n$, count the number of permutations $\sigma$ of $[n]$ such that for any $i$, $|\sigma(i) - \sigma(i+1)| \neq 1$. Of course, this sequence has already been studied before, it is the [A002464](https://oeis.org/A002464) in OEIS. You can find its recurrence relation $$ a_n = (n+1)a_{n-1} - (n-2)a_{n-2} - (n-5...
simplification of the expression doesn't help reducing the time complexity in this sense., We are often concerned with a summation involving binomials, and we want to simplify theexpression

Full text and comments »

  • Vote: I like it
  • +123
  • Vote: I do not like it

71.
By Black_Fate, 4 years ago, In English
[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...
$C_k^n$, there are many versions of the expression.), This expression looks like combination, but it's not!, Then it's easy to write out this expression: $dp[i][j]=dp[i-1][j]+dp[i][j-1]$. , Wow, this seems just the combination expression!

Full text and comments »

  • Vote: I like it
  • +139
  • Vote: I do not like it

72.
By Swistakk, history, 8 years ago, In English
Ultimate guide to TopCoder plugins Hi, I wanted to present to you guide on how you should set up TopCoder Arena in order to make competing in TC much more pleasant experience. Or at least guide how to do the same thing as I did which seem very comfortable to me compared to this big pain of competing in bare default Arena. In case you want to grab easy upvotes please leave here some joke about how I am jealous about ~Radewoosh,2018-08-16 getting insane boost in his contribution by writing his blogs, but the real reason is that I screwed my setup recently and needed to go through this painful and magical setup once again and it seems this information is very nontrivial and not available publicly in a known place (which I believe is one of reasons TopCoder is losing its popularity, but I hope thanks to this post I can give slight boost to it by settling up Arena problems once and for all for many people), so I wanted to share it with others. I want to express my sincere thanks to [user:tomasz.kociumaka,2018-08-16] for guid...

Full text and comments »

  • Vote: I like it
  • +302
  • Vote: I do not like it

73.
By adamant, history, 5 years ago, In English
Randomized general matching with Tutte matrix Hi everyone! Some time ago [user:1-gon,2021-07-01] wrote an [article](https://codeforces.me/blog/entry/92339) about Edmonds blossom algorithm to find the maximum matching in an arbitrary graph. Since the problem has a very nice algebraic approach, I wanted to share it as well. I'll start with something very short and elaborate later on. **[Library Checker &mdash; Matching on General Graph](https://judge.yosupo.jp/problem/general_matching)**. Given a simple undirected graph on $N \leq 500$ vertices, find the maximum matching. <hr> **tl;dr**. The Tutte matrix of the graph $G=(V, E)$ is \begin{equation} T(x_{12}, \dots, x_{(n-1)n}) = \begin{pmatrix} 0 & x_{12} e_{12} & x_{13} e_{13} & \dots & x_{1n} e_{1n} \newline -x_{12} e_{12} & 0 & x_{23} e_{23} & \dots & x_{2n} e_{2n} \newline -x_{13} e_{13} & -x_{23} e_{23} & 0 & \dots & x_{3n} e_{3n} \newline \vdots & \vdots & \vdots & \ddots & \vdots \newline -x_{1n} e_{1n} & -x_{2n} e_{2n} & -x_{3n} e_{3n} & \dots & 0 \end{...
Thus $B^{-1} = \hat B - \hat u \hat v^T / \hat a_{11}$. In more generic terms, thisexpression is

Full text and comments »

  • Vote: I like it
  • +223
  • Vote: I do not like it

74.
By Mindeveloped, history, 2 years ago, In English
I made (Not Yet Another) problem filter script I made my own script to filter problems in CF problemset. If such script with same function already exists you can ignore my post or downvote it. This is a python 3 script that fetches all problems from CF problemset and allows custom filtering. It supports custom filter criteria in python expression format. After you input the filter function, it filters the problems and choose a random one. More details can be found in spoilers below. <spoiler summary="Filter Expression"> In your filter expression, you are given variables `problem` and `contest`, and it's supposed to returns `1` if the problem matches your search, `0` otherwise. Example: `problem.rating == 2400 and "geometry" not in problem.tags and contest.divison == "Div. 1"` The variable `problem` contains such properties: ``` id - The ID of the problem, in the format e.g. 1234H, 2024A. rating - The CF rating tag. Can be absent. contest - The contest id of this problem. Equals to contest.id. index - The problem...
In your filter expression, you are given variables `problem, ("Enter filter expression ") for problem in problems: try: if eval(schema,None,{'problem, . It supports custom filter criteria in python expression format. After you input the filter function, expression format. After you input the filter function, it filters the problems and choose a random one

Full text and comments »

  • Vote: I like it
  • +15
  • Vote: I do not like it

75.
By Keshi, 5 years ago, In English
Codeforces Global Round 17 Editorial ###[problem:1610A] Idea: [user:Anti-Light,2021-11-24], Preparation: [user:DeadlyCritic,2021-11-24] <spoiler summary="Hints"> <spoiler summary="Hint 1"> $ans \le 2$ </spoiler> <spoiler summary="Hint 2"> If $n = 1$ and $m = 1$ then $ans = 0$. <a href="https://emoji.gg/emoji/5500-thosewhoknow"><img src="https://emoji.gg/assets/emoji/5500-thosewhoknow.png" width="20px" height="20px" alt="ThoseWhoKnow"></a> </spoiler> </spoiler> <spoiler summary="Solution"> [tutorial:1610A] </spoiler> <spoiler summary="Implementation"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(); cout.tie(); int t; cin >> t; while(t--){ int n, m; cin >> n >> m; if(n == 1 && m == 1){ cout << "0\n"; } else if(min(n, m) == 1){ cout << "1\n"; } else cout << "2\n"; } } ~~~~~ </spoiler> ###[p...
turn it into a valid math expression by adding characters "+" and "1".)

Full text and comments »

  • Vote: I like it
  • +175
  • Vote: I do not like it

76.
By omsincoconut, 20 months ago, In English
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...
Find a closed-form expression for the score of a binary string, The closed-form expression for the score of a binary string is, The expression for counting subsequences might be simpler than you, , the expression above reduces to, Alternatively, you can do more algebra to arrive at a closed-form expression., So the desired sum of the score over all subsequences (see expression of score of a single string

Full text and comments »

  • Vote: I like it
  • +96
  • Vote: I do not like it

77.
By HubRis504, history, 3 months ago, In English
Unusual Style Changes in plagues' Submissions Some time ago, [user:plagues,2026-08-31] published [The most outrageous cheating in the history of Huawei Challenge](https://codeforces.me/blog/entry/156293), questioning whether several highly ranked accounts in the Huawei Challenge might have collaborated with each other. The original post was written with considerable confidence in labeling those accounts as cheaters. While some of the cases it discussed may have had relatively strong supporting evidence, many of the other connections were based on weaker correlations or incidents that, as far as I know, have not been independently substantiated. This post does not attempt to evaluate or revisit those allegations. However, that post drew my attention to this account. I noticed an unusual period in [user:plagues,2026-08-31]'s rating trajectory, so I reviewed 59 of his `CONTESTANT` submissions from the following six contests. There are several differences in coding style and apparent origin among these submissions that I believe d...

Full text and comments »

  • Vote: I like it
  • +138
  • Vote: I do not like it

78.
By errorgorn, 4 years ago, In English
Catalan Numbers and Generating Uniform Balanced Bracket Sequences Hi everyone! Today [user:nor,2022-05-27] sir and I would like to talk about generating uniform bracket sequences. Over the past few years when preparing test cases, I have had to generate a uniform bracket sequence a few times. Unfortunately I could not figure out how, so I would like to write a blog about this now. Hopefully this blog would be useful to future problem setters :) Scroll down to the end of the blog to copy our generators. First, let's define some things. A bracket sequence is a string with $n$ $\texttt{(}$ s and $n$ $\texttt{)}$ s. A **balanced** brackets sequence is a bracket sequence with the additional constraint that it becomes a valid arithmetic expression when we add some $\texttt{1}$ s and $\texttt{+}$ s. Let $p$ be the prefix sum array of a bracket sequence (we assign $1$ to $\texttt{(}$ and $-1$ to $\texttt{)}$ and take the prefix sum). For example, if our bracket sequence is $\texttt{())()((())}$, then $p=[1,0,-1,0,-1,0,1,2,1,0]$. An alternate way to thi...
that it becomes a valid arithmetic expression when we add some $\texttt{1}$ s and $\texttt{+}$ s. Let

Full text and comments »

  • Vote: I like it
  • +205
  • Vote: I do not like it

79.
By yeputons, 16 years ago, translation, In English
Codeforces Beta Round #54 (Div.2) - разбор A-D <div align="center"><b>Problem A. Chat room<br></b><div align="left">Solution is greedy algorithm. The first thing we do is find in our string the first letter 'h'. Then we find letter 'e' which is righter that found 'h'. If we find the whole word 'hello' in such way, obliviously, answer is YES.<br>Now let's prove that if answer exists, we find it. Let see on position of the 'h' in right answer. If we move it to the first 'h' in our string, nothing changes. But now we can say that our greedy algorithm correctly Now let's do such with the second letter, and so on.<br>We have greedy algorithm with work time O(n), where n - length of the input.<br></div><br><div align="left"><div align="center"><b>Problem B. Coins<br></b><div align="left">This problem also have greedy solution: we run down all number from 2 and greater and while denomination of the last added to answer coin is divisible by current number, we divide and increase answer.<br>You can prove correctness, if you take a look at p...
Problem E. Expression Under

Full text and comments »

  • Vote: I like it
  • +25
  • Vote: I do not like it

80.
By meret, 14 years ago, In English
Editorial for Codeforces Round #134 #### A. Ice Skating Notice that the existence of a snow drift at the point $(x, y)$ implies that "if I'm on the horizontal line at $y$ then I am certainly able to get to the vertical line at $x$, and vice versa". Thus, the snow drifts are the edges of a bipartite graph between x- and y- coordinates. The number of snow drifts that need to be added to make this (as well as the original) graph connected is the number of its connected components reduced by one. #### B. Blackboard Fibonacci If you look at the described process backwards, it resembles the Euclidean algorithm a lot. Indeed, if you rewinded a recording of Bajtek's actions, he always takes the larger out of two numbers (say $a \geq \b$) and replaces them by $a - b, b$. Since we know one of the final numbers ($r$) we can simply check all numbers between $1$ and $r$ and run a faster version of Euclid's algorithm (one that replaces $a, b$ by $a \mod b, b$) for all possibilities for a total runtime of $O(r \log r)$. This w...
substitute them for $0$ and $1$ in the expression. If the two expressions evaluate to different values, we, To determine whether such a sequence $s$ exists, dynamic programming over the expression tree of

Full text and comments »

  • Vote: I like it
  • +82
  • Vote: I do not like it

81.
By arvindf232, history, 12 months ago, In English
Quadratic binary energy function minimisations by Flow ## Motivations I tried to read [https://codeforces.me/blog/entry/148438](https://codeforces.me/blog/entry/148438) and failed. It contains a lot of extra explanations and intuition that I either already knew or could reconstruct immediately. That is not inherently bad, but for me personally it made the key ideas harder to see. (I think most contestants would not struggle with visualising binary logical relations...) As I asked around (and with help from LLMs), it became clear that the underlying structure is the Kolmogorov–Zabih characterization of which quadratic binary energies are solvable via a single max-flow. This blog is essentially a reweighting of that material: shorter, more “algebraic”, and aimed at people who are already comfortable with max-flow / min-cut and with abstracting away implementation details. This blog is also just essentially an extremely long comment that is too long to fit in comment section. ## Declarations While writing this, I did **not**...
if we interpret each logical expression as its indicator (0/1). Thus, a term involving $x_i \land

Full text and comments »

  • Vote: I like it
  • +95
  • Vote: I do not like it

82.
By usernameson, history, 10 years ago, In English
lambda expressions and pairs #### Introduction In this entry I will show how to use lambda expressions to deal with a fairly common situation that arises in problems. Also this post is specific to C++ 11 and beyond where lambda expressions were introduced to the language. #### The Situation Sometimes in problems it is natural to store inputs in pairs. For example it may be important to keep track of both the size of an element and where it occurs in the input; or when an element has two important attributes. This usually results in a vector of pairs. Next it can be useful to apply an algorithm to this vector of pairs and this where lambda expressions shine. #### An Example For an example problem I will use the codeforces problem The Meeting Place Cannot Be Changed http://codeforces.me/problemset/problem/780/B. The idea of the problem is you have people at n points who each have a maximum speed and who want to meet. You have to figure out the minimum time they can meet. My solution is interesting for thre...
three reasons. Firstly and most importantly it uses a lambda expression to sort a vector of pairs, uses a lambda expression to sort a vector of pairs. Secondly the approach differs from the editorial, . At this point I used a lambda expression to sort the pairs in order of increasing starting points, //the lambda expression sort(xv.begin(), xv.end(), [](pair vp, pair

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it

83.
By Sharon, history, 7 years ago, In English
AI Tech Poorly Prepared Contest (Aritifical Intelligence Generated Problems) We got an AI to generate programming problems, after being trained for hundreds of hours on problem 4A. (This is what we used to train it: https://colab.research.google.com/drive/1gWn1uN4cULoDnBJTSGqrUxxao5q3xHeI) We omitted samples, time limits, and memory limits because they don't make much sense. Here are the funniest results: ------------------ ~~~~~ <|title|> E. Back to the Future <|time-limit|> 4 seconds <|memory-limit|> 256 megabytes <|problem-text|> After escaping from the crashed time machine, Marty McFly was transported to present-time! He landed on the lawn where his damaged car was parked. He was given the coordinates of the car's location x y. Marty quickly recognized that this car park is located at a distance of 1 meter from the starting position x, and its maximum speed is v. He also noticed that the car's navigation system is malfunctioning. For some inexplicable reason the system tells Marty that the distance between a pair of stationary objects is...
). After each query you need to calculate the maximum value of an expression which can be found in

Full text and comments »

  • Vote: I like it
  • +250
  • Vote: I do not like it

84.
By Proofy, 2 years ago, In English
LaTeX tips in Editorials and Statements: Make Your Equations Pretty Can you spot any difference between $max$ and $\text{max}$ or $dp$ and $\text{dp}$? How about $\lfloor \frac{max(a, b, c)}{b} \rfloor$ and $\left \lfloor \frac{\max(a, b, c)}{b} \right \rfloor$? Or even $\displaystyle \left \lfloor \frac{\max(a, b, c)}{b} \right \rfloor$! While appreciating the efforts and the careful elaborate writing of the authors, I have faced many issues with latex writing in editorials that have frustrated me while reading over the years, so I thought of writing this blog to settle many of such issues and making our equations in editorials the prettiest possible. I'm going to use [this editorial](https://codeforces.me/blog/entry/127195) in problem F div 1 an example and refer to it in things that can be improved. Of course, that doesn't mean any offence to [user:satyam343,2024-07-22]'s beautiful and careful writing of the editorial nor his/her LaTeX writing/skills, he/she has done it beautifully. Also, note that any code that is quoted in this blog `...
, exponentation, ...etc. The parenthesis or brackets are enlarged to enclose yourexpression.

Full text and comments »

  • Vote: I like it
  • +220
  • Vote: I do not like it

85.
By adamant, history, 4 years ago, In English
p-adic exponent or why there is a primitive root modulo powers of prime numbers (except 2) Hi everyone! You probably know that the primitive root modulo $m$ exists if and only if one of the following is true: - $m=2$ or $m=4$; - $m = p^k$ is a power of an odd prime number $p$; - $m = 2p^k$ is twice a power of an odd prime number $p$. Today I'd like to write about an interesting rationale about it through $p$-adic numbers. Hopefully, this will allow us to develop a deeper understanding of the multiplicative group modulo $p^k$. ### Tl;dr. For a prime number $p>2$ and $r \equiv 0 \pmod p$ one can uniquely define $$ \exp r = \sum\limits_{k=0}^\infty \frac{r^k}{k!} \pmod{p^n}. $$ In this notion, if $g$ is a primitive root of remainders modulo $p$ lifted to have order $p-1$ modulo $p^n$ as well, then $g \exp p$ is a primitive root of remainders modulo $p^n$. Finally, for $p=2$ and $n>2$ the multiplicative group is generated by two numbers, namely $-1$ and $\exp 4$. [cut]<br> ### $p$-adic numbers We define a $p$-adic number $r$ as a formal po...

Full text and comments »

  • Vote: I like it
  • +155
  • Vote: I do not like it

86.
By Nisiyama_Suzune, 9 years ago, In English
[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...
1. $[P]$ refers to the boolean expression, i.e. $[P]=1$ when $P$ is true, and $0$ otherwise. 2

Full text and comments »

  • Vote: I like it
  • +202
  • Vote: I do not like it

87.
By jinhan814, 3 years ago, In English
[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...
remove the condition $s ≤ t$ from the summation expression., Now, let's look at the expression $(a_1 + a_2 + a_3) * (b_1 + b_2 + b_3)$. When we expand the, }}$. Using the binomial theorem and simplifying the expression, we obtain $μ(s, t) = (-1)^{|t

Full text and comments »

  • Vote: I like it
  • +160
  • Vote: I do not like it

88.
By llaki, 12 years ago, In English
Rockethon 2015 Editorial (This is a beta version of editorial. It will be changed later) I hope everybody enjoyed the contest. Here we'll present some of the author's solutions to the problems together with some other approaches that we came up with. The editorial is prepared by Lasha Lakirbaia, Anton Lomonos, and Ievgen Soboliev. A &mdash; Game ================== (developed by Ievgen Soboliev & Eldar Bogdanov, editorial written by Lasha Lakirbaia) The problem can be solved with dynamic programming technique. Let $winner[a][b][move]$ denote who wins if both players play optimally and the first has a balls left in his box, the second has $b$ balls left in his box and move defines who is to move next. To determine the value of $winner[a][b][move]$, we should consider all the possible moves the next player can make and see whether any of them lead into the position $winner[x][y][move2]$ in which this player can win with optimal play. Thus, values of winner can be defined recursively. Ok it was a jok...
For a given array $p_1, p_2,..., p_k$ let’s call the value of that expression the _value_ of that, In general case we are trying to calculate this expression:

Full text and comments »

  • Vote: I like it
  • +172
  • Vote: I do not like it

89.
By YipChip, history, 20 months ago, In English
How to calculate floor sum? The floor sum is an algorithm that solves for the value of a function approximating $f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor$ in $O(\log n)$ time complexity. Maybe you haven't heard of it, but you can get the algorithm by simple mathematical derivation. **Notice: If you want to master it, you'd better derive it on your own after reading the editorial.(prepare a draft paper)** ### To calculate the sum of the functions, $n \le 10^{9}$. $$f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor$$ $$g(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2$$ $$h(a,b,c,n)=\sum\limits_{i=0}^ni\left\lfloor\frac{ai+b}{c}\right\rfloor$$ (I) when $a < c$ and $b < c$. First simplify $f(a,b,c,n)$. $$\begin{aligned} f(a,b,c,n)&=\sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\\&=\sum_{i=0}^n\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}\bigg[j\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg]\\&=\sum_{i=0}^n\sum_{j=1}^{\...
Since $j$ in the expression for $t$ is related to summation, we present $t$ separately.

Full text and comments »

  • Vote: I like it
  • +129
  • Vote: I do not like it

90.
By ATSTNG, history, 20 months ago, In English
Undesired -fpermissive behaviour of CF GCC compilers Apparently $24$ hours without sleep and months of coding in scripting languages had the effect on me... During the contest I submitted this [submission:310073998] _Quick challenge: pause reading and find the bug in my solution_ ![ ](/predownloaded/0e/26/0e2631ab99e8f926b267a2b88710962ea2cf0f7e.png) [Link to original art](https://www.artstation.com/artwork/8elamx) When I found out that I failed a div3D on not properly using `int64_t` I was quite surprised, because I double checked that I did it right. I felt very stupid at first, but then I got surprised even more when I figured how exactly this happened. Take a look at the line $25$ ~~~~~ const& r = cr[i]; ~~~~~ It appears that GCC allows to declare variable references omitting type declaration completely when cv-qualifier is present. Yes, without invoking type deduction using `auto`. To be precise expression in form ~~~~~ <cv-qualifier> &<variable-name> = <value>; ~~~~~ appears to be well-formed an...
expression in form

Full text and comments »

  • Vote: I like it
  • +116
  • Vote: I do not like it

91.
By -1e11, 20 months ago, In English
April Fools Day Contest 2025 Editorial ### [2095A &mdash; Piecing It Together](https://codeforces.me/contest/2095/problem/A) Credits: [user:flamestorm,2025-04-01] <spoiler summary="Solution"> If you complete the puzzle, you will get a line of Python code reading $\texttt{print("puzzling")}$. To solve the problem, you just need to print $\texttt{puzzling}$. </spoiler> <spoiler summary="Code (C++)"> ~~~~~ #include <bits/stdc++.h> using namespace std; void solve() { cout << "puzzling\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); } ~~~~~ </spoiler> <spoiler summary="Code (Python)"> ~~~~~ print("puzzling") ~~~~~ </spoiler> ### [2095B &mdash; Plinko](https://codeforces.me/contest/2095/problem/B) Credits: [user:AlperenT,2025-04-01] <spoiler summary="Solution"> In this problem you need to drop a ball from a column of your choosing and get it to the green area. With simple analysis (similar to Pascal's triangle), one can notice that best chanc...
Combining them, noting that the Russian part should go first to make sense, gives theexpression

Full text and comments »

  • Vote: I like it
  • +169
  • Vote: I do not like it

92.
By K1o0n, 6 weeks ago, translation, In English
Codeforces Round #1125 (Div. 3) Editoral Thank you all for participating! [problem:2275A] <spoiler summary="Solution"> The point $(x_0 - R, y_0)$ always lies on the circle because $(x_0 - (x_0 - R))^2 + (y_0 - y_0)^2 = R^2$ holds for every $R$: after expanding the parentheses, we get $R^2 = R^2$. </spoiler> <spoiler summary="Code"> ~~~~~ #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() signed main() { int tt; cin >> tt; while (tt --> 0) { int x, y, R; cin >> x >> y >> R; cout << x - R << " " << y << endl; } } ~~~~~ </spoiler> [problem:2275B] <spoiler summary="Solution"> Let us create a boolean array $\text{used}$ and use it to mark which documents have been printed. For an operation of type 3, we simply set $\text{used}_i = 1$. Operations of types 1 and 2 are essentially the push and pop operations of a stack. Let us also create a stack $\operatorname{memory}$. For an operation of type 1, we push the document number ont...
the expression, we obtain, Since only the parity of the exponent matters, this expression is equal to

Full text and comments »

  • Vote: I like it
  • +51
  • Vote: I do not like it

93.
By adamant, history, 3 years ago, In English
Dirichlet convolution. Part 2: Dirichlet series and prime counting Hi everyone! Recently I've published a [blog](https://codeforces.me/blog/entry/117635) about how one can multiply and divide sequences with Dirichlet convolution. In this blog, we will learn about a convenient framework to reason about them in a "coordinate-free" notation, similar to how generating functions are used to analyze sequences under the regular convolution. - **[Part 1: Fast prefix sum computation](https://codeforces.me/blog/entry/117635)** - **Part 2: Dirichlet series and prime counting** We will learn how to deal with Dirichlet multiplication and division in the framework of Dirichlet series, and derive a number of well known number theoretic results from this perspective. While doing so, we will learn about Riemann zeta function and will have a glimpse into why it is so important in analyzing behavior of prime numbers. We will also learn how Dirichlet series framework helps us to, given $g(1), \dots, g(n)$, to compute $f(1), \dots, f(n)$ in $O(n \log n)$ s...
evaluates to $1$ if the expression inside is true and to $0$ otherwise. In this case, $t$ is a non, expression above as $$ \sum\limits_k c_k \rho_k = \sum\limits_k \sum\limits_{i \circ j = k} a_i

Full text and comments »

  • Vote: I like it
  • +113
  • Vote: I do not like it

94.
By Ripatti, 17 years ago, translation, In English
A little bit of classics: dynamic programming over subsets and paths in graphs <i>Author thanks </i><a href="../../../profile/adamax" title="Капитан adamax" class="rated-user user-yellow">adamax</a><i> <span class="short_text" id="result_box"><span style="" title="">for translation this article into English.</span></span></i><br><br><b>Introduction</b><br>After <a href="http://codeforces.me/blog/entry/331">Codeforces Beta Round #11</a> several participants expressed a wish to read something about problems similar to <a href="http://codeforces.me/contest/11/problem/D">problem D</a> of that round. The author of this article, for the purpose of helping them, tried searching for such information, but to his surprise couldn't find anything on the Internet. It is not known whether the search was not thorough or there's really nothing out there, but (just in case) the author decided to write his own article on this topic.<br><br>In some sense this article may be regarded as a tutorial for the <a href="http://codeforces.me/contest/11/problem/D">problem D</a> from Beta R...
Pay special attention to the expression $dp[mask \text{ xor } 2^i] \text{ and } M_i$. The first

Full text and comments »

  • Vote: I like it
  • +22
  • Vote: I do not like it

95.
By hyforces, history, 3 years ago, In English
Teamscode Summer 2023 Editorial This is the editorial for the recent Teamscode Summer 2023 contest, and the problems are open for upsolving on this [gym](https://codeforces.me/gym/104520). Problems were prepared by [user:oursaco,2023-08-22], [user:dutin,2023-08-22], [user:thehunterjames,2023-08-22], [user:Bossologist,2023-08-22], [user:Esomer,2023-08-22], [user:danx,2023-08-22], [user:codicon,2023-08-22], [user:willy108,2023-08-22], and [user:hyforces,2023-08-22]. The problems were tested by [user:omeganot,2023-08-22], [user:codicon,2023-08-22], [user:cry,2023-08-22], [user:skye_,2023-08-22], [user:Litusiano_,2023-08-22], and [user:apple_method,2023-08-22]. ### [A. Who is cooking?](https://codeforces.me/gym/104520/problem/A) <spoiler summary="Solution"> danx </spoiler> <spoiler summary="Code"> ~~~~~ print("Esomer") ~~~~~ </spoiler> ### [B. Restaurant Sorting](https://codeforces.me/gym/104520/problem/B) <spoiler summary="Solution"> The answer is $n - $ the longest prefix of the array where a...
Expanding the binomial coefficients and simplifying, we get the expression

Full text and comments »

  • Vote: I like it
  • +84
  • Vote: I do not like it

96.
By Wanderkind, history, 2 years ago, In English
Automating reduction on algebraic expressions I recently stumbled upon a problem from Stanford Local ACM Programming Contest (SLPC) 2011. <br> [(contest info)](https://cs.stanford.edu/group/acm/oldsite/SLPC2011/) <br> [(try the problem yourself here)](https://www.acmicpc.net/problem/7636) <br> So the problem is, in short, given algebraic expressions of trigonometry like $x(sin^2x + cos^2x) − x$, you have to determine whether each expression equates to zero. <br> The intended solution, I am assuming, is to <br> 1) convert the input string into a function of $x$ that returns the value, under the same process the expression is described, <br> 2) input multiple values of $x$ into that function, and <br> 3) confirm the identity if the function always returns zero &mdash; within the bounds of float precision error. <br> Unaware of this idea, I initially tried to solve this problem by building a recursive reduction algorithm. <br> Using the F# language, I made a custom algebraic data type, with a set of rules, such as $s...
$ that returns the value, under the same process the expression is described, 2) input, ) − x$, you have to determine whether each expression equates to zero. , expression equates to zero. The intended solution, I am assuming, is to 1) convert the

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

97.
By FieryPhoenix, 7 years ago, In English
Codeforces Round #621 (Div. 1 + Div. 2) Editorial [problem:1307A] Idea: [user:FieryPhoenix,2020-02-16] <spoiler summary="Tutorial"> [tutorial:1307A] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <iostream> using namespace std; int N,D,a[105]; int main(){ int T; cin>>T; while (T--){ cin>>N>>D; for (int i=1;i<=N;i++) cin>>a[i]; while (D--){ //loop over D days for (int i=2;i<=N;i++) if (a[i]>0){ //move closest haybale over a[i]--; a[i-1]++; break; } } cout<<a[1]<<endl; } } ~~~~~ </spoiler> <spoiler summary="Alternative O(n) Solution:"> ~~~~~ #include <iostream> using namespace std; int N,D,a[105],ans; int main(){ int T; cin>>T; while (T--){ cin>>N>>D; for (int i=1;i<=N;i++) cin>>a[i]; for (int i=2;i<=N;i++){ int move=min(a[i],D/(i-1)); //number of haybales we can move from pile i to pile 1 a[1]+=move; //update pile 1 D-=move*(i-1); //update remaining days } cout<<...
; else cout<expression as explained in tutorial a.clear(); } } ~~~~~

Full text and comments »

  • Vote: I like it
  • +159
  • Vote: I do not like it

98.
By Zlobober, history, 11 years ago, In English
Checkers with testlib.h Introduction ------------ Checker is a program that should be written when task allows more than one correct solution. Although it seems that it is very easy to write checker, there are lots of important technical details that are easy to forget if you don't use a special library like testlib.h. A common convention is that a checker should be a program taking three command-line arguments: the testdata filename, the participant output filename and the jury answer filename. Checker should read the contents of the input, output and answer, decide whether participant answer is correct (and optimal being compared to the jury's answer if there can be unoptimal answer in this task) and return one of several pre-defined verdicts: | Verdict | testlib macro | meaning | |---------|---------------|---------| | Ok | `_ok` | The output is correct, follows the output format and represents an optimal answer (if applicable in this problem). | | Wrong Answer | `_wa` | The output is wrong or...
checker all those system-dependent ways are combined in a single expression `quitf(VERDICT, "comment", ...)`.

Full text and comments »

  • Vote: I like it
  • +33
  • Vote: I do not like it

99.
By ADJA, history, 11 years ago, In English
Codeforces Round #306 (Div. 2) Editorial [problem:550A] -------------------------------------------------------------------------- There are many ways to solve this problem. Author solution does the following: check if substring "AB" goes before "BA", and then vice versa, if "BA" goes before "AB". You can do it in the following way: find the first occurence of "AB" then check all substrings of length two to the right of it to check if substring "BA" also exists. Then do it vice versa. Complexity of the solution is $O(n)$, where $n$ is the length of the given string. [problem:550B] -------------------------------------------------------------------------- Because of the low constraints, this problem can be solved by complete search over all problem sets (there are $2^n$ of them). For every potential problem set (which can be conviniently expressed as bit mask) we need to check if it satisfies all needed criteria. We can simply find the sum of problem complexities and also the difference between the most diffi...
value of this expression is always, 3) Expression in the form $\cdots \rightarrow 0 \rightarrow \cdots \rightarrow 0 \rightarrow 0

Full text and comments »

  • Vote: I like it
  • +93
  • Vote: I do not like it

100.
By Furioso_Slient, history, 11 months ago, In English
Some thinking about randomization. ## Introduction Chinese Version:[Link](https://www.luogu.com.cn/article/gt9xd9oo) **UPD#1 18.12.25: Fixed relevant typos and rigorousness errors; added the randomization concept in Treap.** Mention "randomization" and most people's first reaction is probably flipping a coin to bet on `YES` or `NO`. Randomization itself, often seen as an "unorthodox method" (or "dark art"), is generally discarded by teachers in standard educational institutions and is rarely explained in depth. However, in reality, the power of randomization is beyond your imagination. ## Magical Randomization Randomization essentially means shuffling a set of data to make it lose some of its original properties, or to grant it new properties. So, what’s the use of these so-called new properties? Let’s taste a few problems: ### Example 1: Countering Extreme Data Suppose you need to implement a sorting algorithm, but you choose the unstable Quick Sort. Suddenly, a mysterious hacker from Code...
rigorousness in expression.

Full text and comments »

  • Vote: I like it
  • +107
  • Vote: I do not like it

101.
By JaySharma1048576, 5 years ago, In English
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 ...
this segment will not be affected by the rest of the expression. Moreover, out of all the

Full text and comments »

  • Vote: I like it
  • +93
  • Vote: I do not like it

102.
By PraveenDhinwa, 12 years ago, In English
Codeforces Round #258 Editorial **[problem:451A]** From a grid of size $n * m$, if we remove an intersection point, then the grid after removing the sticks passing through it, will of size $n - 1$, $m - 1$. Notice when the grid consists of a single horizontal stick and m vertical sticks, If we pick any intersection point, then the updated grid will be only made of vertical sticks. You can see that there is no intersection point in the grid now. So $ans(n, m) = ans(n - 1, m - 1)$ ^ $1.$ $ans(1, *) = 1$ $ans(*, 1) = 1$ So we can notice that answer will depend on the parity of $minimum(m, n)$. You can prove it using the previous equations. You can also check this by seeing the pattern. So finally if $min(n, m)$ is odd, then Akshat will win. Otherwise Malvika will win. You can also observe that "players will play optimally" is useless in this case. Complexity : $O$(1) **Solution codes** - [my solution](http://codeforces.me/contest/451/submission/7233706) **[problem:...
Substituting in the expression, we get $(1 - x^{(f_1 + 1))} / (1 - x) * * * (1 - x^{(f_n + 1

Full text and comments »

  • Vote: I like it
  • +39
  • Vote: I do not like it

103.
By spike1236, history, 20 months ago, In English
Alternative Solution to 2077C Using Probability Hello, Codeforces community! Today, I want to share my solution to a problem from recent contest: [Binary Subsequence Value Sum](https://codeforces.me/contest/2077/problem/C). Rather than using polynomials and FFT, I tried to approach this problem from a different viewpoint &mdash; probability! Now, let's get started with the solution itself. --- ## 1. Deterministic definition of the score Suppose you have a binary string $v$ of length $m$. Interpret each character as a “contribution”: assign $+1$ for a ‘1’ and $-1$ for a ‘0’. Define $$ d = \text{(number of 1's)} - \text{(number of 0's)} $$ so that $d$ is the overall “imbalance” of $v$. The score of $v$ is defined as $$ \text{score}(v) = \max_{1 \le i < m} \Bigl( F(v,1,i) \cdot F(v,i+1, m) \Bigr), $$ where $F(v,1,i)$ is imbalance of prefix and $F(v,i+1,m)$ is imbalance of suffix; if the prefix imbalance is $S$, then the suffix is $d-S$, and the product is $$ P(S) = S\cdot (d-S). $$ For fixed $d$, th...
So in one compact expression, the score of $v$ can be written as $$ \text{score}(v) = \frac{d^2, }, $$ which means that whenever $d'$ is odd, our naive expression $\frac{(d')^2}{4}$ is an overestimate by

Full text and comments »

  • Vote: I like it
  • +112
  • Vote: I do not like it

104.
By I_Love_Tina, history, 10 years ago, In English
Codeforces Round #361 (Div. 2) Editorial [A.Mike and Cellphone](http://codeforces.me/contest/689/problem/A) Author:[user:dans,2016-07-06]. Developed:[user:reality,2016-07-06],[user:ThatMathGuy,2016-07-06] We can try out all of the possible starting digits, seeing if we will go out of bounds by repeating the same movements. If it is valid and different from the correct one, we output "NO", otherwise we just output "YES". <spoiler summary="C++ code"> ~~~~~ pair < int , int > s[55][55]; int v[55][55]; pair < int , int > where[55]; int main(void) { for (int i = 1;i <= 10;++i) for (int j = 1;j <= 10;++j) v[i][j] = -1; v[1][1] = 1; v[1][2] = 2; v[1][3] = 3; v[2][1] = 4; v[2][2] = 5; v[2][3] = 6; v[3][1] = 7; v[3][2] = 8; v[3][3] = 9; v[4][2] = 0; for (int k = 0;k <= 9;++k) for (int i = 1;i <= 4;++i) for (int j = 1;j <= 4;++j) if (v[i][j] == k) where[k] = {i,j}; for (int i = 0;i <= 9;++i...
Notice that this expression is non-decreasing as $n$ grows, so we can run a binary search for $n$.

Full text and comments »

  • Vote: I like it
  • +113
  • Vote: I do not like it

105.
By dolphinigle, 15 years ago, In English
Codeforces Beta #87 Editorial <p><b><u>Time Capsule Remarks (planted before the contest)</u></b></p><p>Due to popular demand, today's problem statements are made to be as short as possible without too many (but existing!) embellishment. All of them are thinking-based problems (i.e., implementation is the easier of the two) - so I'm generally happy with the problems :). I hope nobody found them to be too easy :S</p><p>As you may have noticed, we decided not to give devastatingly weak pretests. I guess it's just really evil to give weak pretests for my first match.</p><p>And so, the editorial begins...</p><p><u>Remarks</u></p><p>I'm sorry - but I don't have access to my usual graphic editing tool and so, the graphics are fairly limited :) (Example: Lawnmower's pictures must be the ugliest lawnmower I have ever seen! (Is it even a lawnmower?) Not to mention I don't look like the actor at all...)</p><p><b><u><a href="http://codeforces.me/contest/116/problem/A">D2-A: Tram</a></u></b></p><p>If we know the number of peop...
1) Create a unary expression. In the example above, , 2) Create a binary expression. In the example above, , For our example, we suppose we read another unary expression , How does this tells that we will need to create a binary expression? The second open bracket , arithmetic expression on the substring of the input starting at start_pos and ending at end_pos. This, arithmetic expression, close it with some number of brackets that we don't care (to be explained, is actually easy - for every open bracket we have, if it's for a unary expression, we simply close, operand of a binary expression, and we have ourself a possible answer., the unambiguous arithmetic expression by scanning it left to right and making some choices., unprocessed input. braces indicates the number of open brackets that belongs to a binaryexpression. So, Expression

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

106.
By Elegia, history, 3 years ago, In English
How to composite (some) polynomials faster? Hi everyone, today I'd like to elaborate something more on the [problem I](https://codeforces.me/contest/1930/problem/I) on the recently ended div 1 contest. As described in the [official solution](https://codeforces.me/blog/satyam343), a bottleneck of the problem is the following: Given a sequence $\{c_j\}_{-n \leq j \leq n}$, compute $$ g_k = \sum_{-k\leq j\leq k} ([x^j] (x + 1/x)^k) c_j $$ for all $0 \leq k \leq n$. In the official solution, an $O(n\log^2 n)$ time algorithm is presented, and we also claimed that it is possible to compute $g_k$ in $O(n\log n)$ time. In this post, I'd like to elaborate on how to do that. By the way, another bottleneck of the problem is the relaxed convolution problem, where the usual implementation also takes $O(n\log^2 n)$ time. I mentioned in [comment](https://codeforces.me/blog/entry/111399#comment-996712) that the relaxed convolution has a somehow practical solution that has time complexity $$ O\left(\frac{n\log^2 n}{\log \log n...
equation $P(x) = 0$ by solving the composition chain step by step, this will result in anexpression

Full text and comments »

Discussion of think-cell Round 1
  • Vote: I like it
  • +269
  • Vote: I do not like it

107.
By wuhudsm, history, 12 months ago, In English
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...
Observe that $x \oplus (x + 1) = 1$ when $x$ is even. This expression can be used to reduce $f(x)$.

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it

108.
By Proof_by_QED, 19 months ago, In English
Codeforces Round 1017 (Div. 4) Editorial <spoiler summary="Rating Predictions"> | Predictor | A | B | C | D | E | F | G | H | |----------------------------------|-----|-----|-----|------|------|------|------|------| | [user:Proof_By_QED,2025-04-12] | 800 | 800 | 800 | 1000 | 1200 | 1300 | 1600 | 1800 | | [user:Dominater069,2025-04-12] | 800 | 800 | 800 | 900 | 1200 | 1200 | 1600 | 1600 | | [user:reirugan,2025-04-12] | 800 | 800 | 800 | 900 | 1500 | 1500 | 1700 | 1700 | | [user:macaquedev,2025-04-12] | 800 | 800 | 800 | 900 | 1600 | 900 | 1800 | &mdash; | | [user:Filikec,2025-04-12] | 800 | 800 | 800 | 900 | 1300 | 1500 | 1700 | 1800 | | [user:edeeva,2025-04-12] | 800 | 800 | 800 | 1000 | 1300 | 1600 | 1700 | 1900 | | [user:yoru_sacri,2025-04-12] | 800 | 800 | 800 | 900 | 1400 | 1700 | 1900 | 1900 | | [user:kevlu8,2025-04-12] | 800 | 800 | 800 | 900 | 1600 | 1400 | 1700 | &mdash; | | [user:AG-88301,2025-04-12] ...
expression: $(n+1)\sum_{i=1}^na_i-score$. This is because $score + rscore = (n+1)\sum_{i=1}^na_i$ since

Full text and comments »

  • Vote: I like it
  • +90
  • Vote: I do not like it

109.
By balalaika, history, 22 months ago, In English
[C++ Editorial] Some things about mixing increments/decrements Inspired by [this blog](https://codeforces.me/blog/entry/138166) I already gave answer [there](https://codeforces.me/blog/entry/138166?#comment-1235619) but it struck me that it can be nice educational blog. Though main reason I write this is training English-writing. I will refer to [this document](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/n4950.pdf) which is the closest I know to C++23 standard. _Disclaimer: Never mix several increments/decrements in single expression (even if each operation performed on different variables) &mdash; it is just looks ugly almost always and it is harder to read._ ### Why exactly expression `++x + ++x` is UB? https://godbolt.org/z/qWbKfP9Gj. clang/gcc gives 13, msvc gives 14. Let's explore how standard requires to calculate expressions. 6.9.1 is all about that. In particular, 6.9.5 introduces term _full-expression_ with examples. For simplification let's say that every code between `;` (but not only they) is full-expre...
code between `;` (but not only they) is full-expression:, ### Why exactly expression `++x + ++x` is UB?, - 6.9.9 All computations and side-effects of full-expression are sequenced before any computation, If you think that it is `(a++)+(++b)` because this is only well-defined expression then you wrong, Yep, but it is not about order of evaluation of operands. It is about evaluation of full-expression, _Disclaimer: Never mix several increments/decrements in single expression (even if each operation, expression (even if each operation performed on different variables) — it is just looks ugly almost, int main() { std::cout << 2 + 2 << std::endl; // Whole line is full-expression

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

110.
By Nickolas, 12 years ago, translation, In English
VK Cup 2015 Wild Card Round 1: editorial In this contest we aimed to show that declarative approach to problemsolving can be more convenient than the traditional imperative. However, the first several problems were supposed to aquaint the competitor with the basic language syntax and its libraries. All reference solutions are written by [user:kit1980,2015-03-28]. #### [problem:530A] To solve a quadratic equation, one has to use a library function `sqrt` and an if-then-else construct. Besides, this problem was supposed to show that Picat has foating-point numbers. :-) ~~~ main => A = read_real(), B = read_real(), C = read_real(), D = B * B - 4 * A * C, X1 = (-B - sqrt(D)) / (2 * A), X2 = (-B + sqrt(D)) / (2 * A), if D == 0 then println(X1) else printf("%w %w%n", min(X1, X2), max(X1, X2)) end. ~~~ #### [problem:530B] A string manipulation problem: library function `slice` allows to get a substring of the given string, `reverse`, well, reverses it, and `++` is...
of maximum: expression `table(+, +, +, max)` means that the first three parameters of the predicate, Expression `A * X + B * Y #= C` sets variable constraint. At this stage the system can understand

Full text and comments »

  • Vote: I like it
  • +45
  • Vote: I do not like it

111.
By skywalkert, history, 7 years ago, In English
2018 CMUT BeihangU Contest, Editorial This editorial corresponds to [contest:102114] (stage 5), which was held on Aug 6th, 2018. Moreover, this problem set was also used as Jingzhe Tang Contest 1 in Petrozavodsk Winter Camp on Jan 30th, 2019. **This post is now finished**, in which I try to elaborate on notes, solutions and maybe some data generating. Alternatively, you can refer to [an old published material](https://drive.google.com/file/d/1CFumWbNLTUEywkVDNF-LKT3SzYd1r15L/view), though I think the old English version did not explain something clearly. --- [problem:102114A] This problem requires to calculate $s$-$t$ min cut between any two vertices on a weighted cactus graph having $n$ vertices, denoted by $\mathrm{flow}(s, t)$. You need to report $\sum_{s < t}{(s \oplus t \oplus \mathrm{flow}(s, t))}$. $n \leq 10^5$, $\sum{n} \leq 10^6$, weights are $\leq 10^9$. Try to find some features of this graph. <spoiler summary="solution"> By contradiction, we can prove that for an undirected graph, each ed...
if they can be simplified as the same rational expression., them twice. It's not difficult to observe that if we regard an expression and its opposite (i.e. the, , the minus operator must not be involved in the expression, and how to count that has already been, In this case, parentheses cannot be expanded easily, but we can split the expression into

Full text and comments »

  • Vote: I like it
  • +79
  • Vote: I do not like it

112.
By cry, 2 years ago, In English
Codeforces Round 962 (Div. 3) Editorial [problem:1996A] Problem Credits: [user:cry,2024-07-19] <br> Analysis: [user:cry,2024-07-19] <spoiler summary="Solution "> If $n$ is a multiple of $4$, then you can have $\frac{n}{4}$ cows. Otherwise, you must have at least one chicken, so you can have $\frac{n-2}{4}$ cows and $1$ chicken. </spoiler> <spoiler summary="Code (C++)"> ```cpp #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int tc; cin >> tc; while (tc--){ int n; cin >> n; cout << (n + 2) / 4 << "\n"; } } ``` </spoiler> [problem:1996B] Problem Credits: [user:sum,2024-07-19] <br> Analysis: [user:cry,2024-07-19] <spoiler summary="Solution "> Let's define every $k$ by $k$ block of cells by its value in the top left corner, since all cells in the block must have the same value. So, we can just print out the value of the cell in every $k$'th row and every $k$'th column. </spoiler> <spoil...
expression for all potential $y$ now. Let's denote the all possible $y$ as $y_1, y_2, ... y_k$. We

Full text and comments »

  • Vote: I like it
  • +110
  • Vote: I do not like it

113.
By Spheniscine, history, 7 years ago, In English
Modular Arithmetic for Beginners Introduction ------------------ If you're new to the world of competitive programming, you may have noticed that some tasks, typically combinatorial and probability tasks, have this funny habit of asking you to calculate a huge number, then tell you that "because this number can be huge, please output it modulo $10^9 + 7$". Like, it's not enough that they ask you to calculate a number they know will overflow basic integer data types, but now you need to apply the modulo operation after that? Even worse are those that say you need to calculate a fraction $\frac pq$ and ask you to output $r$ where $r \cdot q \equiv p \pmod m$... not only do you have to calculate a fraction with huge numbers, how in the *world* are you going to find $r$? Actually, the modulo is there to make the calculation *easier*, not *harder*. This may sound counterintuitive, but once you know how modular arithmetic works, you'll see why too. Soon you'll be solving these problems like second nature. Terminol...
The value $m$ after the modulo operator is known as the *modulus*. The result of theexpression $n

Full text and comments »

  • Vote: I like it
  • +46
  • Vote: I do not like it

114.
By gen, 13 years ago, In English
Codeforces Round #238 Tutorial #### [problem:405A] Observe that in the final configuration the heights of the columns are in non-decreasing order. Also, the number of columns of each height remains the same. This means that the answer to the problem is the sorted sequence of the given column heights. Solution complexity: $O(n)$, since we can sort by counting. #### [problem:405B] If the first pushed domino from the left was pushed to the left at position $l$, all dominoes at prefix $[1;l]$ fall down, otherwise let $l$ be 0. Similarly, if the first pushed domino from the right was pushed to the right at position $r$, all dominoes at suffix $[r;n]$ also fall down, otherwise let $r$ be $n+1$. Now, in the segment $(l;r)$ there will remain vertical dominoes and blocks of dominoes supported by the equal forces from both sides. When does a domino at position $p$ in segment $(l,r)$ remains standing vertically? One way is that it is not pushed by any other domino. This could be easily checked by looking at the ...
the sum is taken modulo 2, these summands together give 0 to the sum. It follows that theexpression

Full text and comments »

  • Vote: I like it
  • +80
  • Vote: I do not like it

115.
By adamant, 7 years ago, In English
On continued fractions. Part 1: Introduction Hi everyone! After writing [this](https://codeforces.me/blog/entry/73629) article I've decided to write another one being comprehensive introduction into continued fractions for competitive programmers. I'm not really familiar with the topic, so I hope writing this entry will be sufficient way to familiarize myself with it :) **Part 1: Introduction**<br> [Part 2: Properties and interpretation](https://codeforces.me/blog/entry/73687) <br> [cut] <br> **Definitions.** To begin with, any _rational_ number $r=\frac{p}{q}$ may be _uniquely_ represented as a _finite_ nested fraction of the following kind: <br><br> $$ r = a_0 + \frac{1}{a_1 + \frac{1}{a_2+\dots}} $$ Where $a_0$ is integer number and $a_1, a_2, \dots, a_n$ are _positive_ integer numbers and either $n=0$ or $a_n \neq 1$. It may be written shortly as $r = [a_0, a_1, \dots, a_n]$. Let's investigate it a bit. In the given constraints, $[a_1, a_2, \dots, a_n]$ is either absent or it is greater than $1$, which mean...
, a_{k-2}) + P_{k-4}(a_2, a_3, \dots, a_{k-2})]$$ - Use recurrent formula to fold theexpression

Full text and comments »

  • Vote: I like it
  • +201
  • Vote: I do not like it

116.
By box, history, 6 years ago, In English
[Tutorial] Generalized Chirp Z-Transform <s>My last blog was a bit too esoteric</s> This blog assumes that you can do a basic convolution (e.g. FFT). After I saw that many people did not know how to do Chirp Z-Transform with arbitrary exponents fast from [my blog 9 weeks ago](https://codeforces.me/blog/entry/82165) I decided to <s>shitpost</s> write a short tutorial on it. Let's say we have a polynomial $P(x)$, such that $$\begin{align}P(x)=\sum_{i=0}^{n-1}a_ix^i\end{align}$$ Now, let's say we have $c$ and $m$, and we want to find $P(c^0),P(c^1),P(c^2),\dots,P(c^m)$. Let $b_j=P(c^j)$. Consider the implications of having $x$ as such a form: $$\begin{align}b_j=\sum_{i=0}^{n-1}a_ic^{ij}\end{align}$$ Tinkering around with different expressions for $ij$, one finds that $ij=\frac{(i+j)^2}{2}-\frac{i^2}{2}-\frac{j^2}{2}$. This means that $$\begin{align}b_j=\sum_{i=0}^{n-1}a_ic^{\frac{(i+j)^2}{2}-\frac{i^2}{2}-\frac{j^2}{2}}\end{align}$$ $$\begin{align}b_jc^{\frac{j^2}{2}}=\sum_{i=0}^{n-1}(a_ic^{-\frac{i^2}{2...

Full text and comments »

  • Vote: I like it
  • +146
  • Vote: I do not like it

117.
By rama_pang, 4 years ago, In English
NUS CS3233 Final Team Contest 2023 Editorial The contest announcement and invitation link is [here](https://codeforces.me/blog/entry/114880). The contest link is [here](https://codeforces.me/gym/104296). ## [A. Artistic Masterpiece](https://codeforces.me/gym/104296/problem/A) <spoiler summary="Tutorial"> Since $(x,y)$ is covered by the brush iff $(x - x_c)^2 + (y - y_c)^4 \leq r$, that means we can decompose the area of the brush into $O(\sqrt[4]{r})$ independent 1-dimensional intervals (a contiguous block with the same $y$-coordinate). For each center $(x_c,y_c)$ traversed by the brush, add the 1-dimensional intervals for $y \in [y_c - \sqrt[4]{r}, y_c + \sqrt[4]{r}]$. After adding these intervals, the problem is now reduced to computing the area union of 1-dimensional intervals for each separate $y$-coordinate. </spoiler> ## [B. Broken Calculator](https://codeforces.me/gym/104296/problem/B) <spoiler summary="Tutorial"> First, we consider the minimum cost to get from an integer $X$ to another integer $Y$ us...
structure of $F_Y$ (also with the alternative recursive expression of $F_i$):, expression as the sum of currently assigned variables. For the root node, since we initialized it with

Full text and comments »

  • Vote: I like it
  • +45
  • Vote: I do not like it

118.
By wuhudsm, history, 2 years ago, In English
TheForces Round #31 (Div2.9-Forces) Editorial [A](https://mirror.codeforces.com/gym/105245/problem/A) Idea:[user:yugandhar_master,2024-03-14] <spoiler summary="solution"> Let's handle each two lines separately. We greedily place kings in all the white squares in the first row. Then, we cannot place kings in the second row. Overall, the answer is $\lfloor \frac{n+1}{2} \rfloor \cdot \lfloor \frac{m+1}{2} \rfloor$. </spoiler> <spoiler summary="code(C++)"> ~~~~~ #include <bits/stdc++.h> using namespace std; #define ll long long #define fast \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); int main(){ fast; ll t; cin>>t; while(t--){ int n,m; cin>>n>>m; cout<<((n+1)/2)*((m+1)/2)<<"\n"; } } ~~~~~ </spoiler> [B](https://mirror.codeforces.com/gym/105245/problem/B) Idea:[user:beyondpluto,2024-06-14] <spoiler summary="solution"> First let's assign a number...
= pdp_{i-1} + \sum_{x=0}^{i-1} (pb_x \oplus pb_i)$. Notice that the second expression is still $O(n

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it

119.
By THE_FOOL_ON_THE_GREY_FOG, history, 9 months ago, In English
Bahnasy Tree [cut] ** بسم الله والحمدلله والصلاة والسلام على رسول الله ** Bahnasy Tree ================== **GitHub Repository:** [Bahnasy-Tree](https://github.com/Mostafa-Bahnasy/Bahnasy-Tree) Bahnasy Tree is a dynamic tree that represents a **sequence of length $N$** (positions $1..N$). It is controlled by two parameters: - $T$ ( **threshold** ): the maximum fanout a node is allowed to have before we consider it "too wide". - $S$ ( **split factor** ): used when splitting; computed from the node size using the smallest prime factor (SPF). If $S > T$, we fallback to $S = 2$. The tree supports the usual sequence operations (find by index, insert, delete) and can be extended to support range query / range update by storing aggregates (sum, min, etc.) and optionally using lazy propagation. --- ## 1) Node meaning and the main invariant Each node represents a contiguous block of the sequence. If a node represents a block of length `sz`, then its children partition this block into...
So a direct expression is:

Full text and comments »

120.
By PinkRabbitAFO, history, 7 years ago, In English
Codeforces Round #635 Problem "Mahjong Set" Ununofficial Editorial Hello there, here's an unofficial editorial for [1136D. Yui and Mahjong Set](https://codeforces.me/contest/1336/problem/D) by a tester [user:PinkRabbit,2020-04-16]. Observation: Focus on the differential of triplets/straights before and after an operation. By doing an operation on $a_i$, you'll find that the differential of triplets equals $x (x - 1) / 2$, where $x$ equals $a_i$ before the operation. So if we did a single operation on $a_i$, we can get the exact value of initial $a_i$ iff initial $a_i \ge 2$, otherwise initial $a_i$ must be equal to $0$ or $1$. If we did two (or more, but unnecessary?) operation on $a_i$, we can now get the exact value of initial $a_i$ no matter whether $a_i$ is less than $2$ or not. One of the most natural ideas is to perform operation in the order of $1, 2, \ldots, n$, it works like this: - Now, assume we get the exact value of $a_1 \sim a_i$, and we want to determine $a_{i + 1}$. - If $a_{i + 1} \ge 2$, done. Just consider the ...
Said too much. Sorry for bad English expression (didn't check) (hopefully [user:ouuan,2020-04-16

Full text and comments »

  • Vote: I like it
  • +141
  • Vote: I do not like it

121.
By Wielomian, history, 5 years ago, In English
[Tutorial] Sorting with lambda Hello, Codeforces! Today I want to share with you something that often gets brushed off because it's a very basic concept &mdash; sorting. I think that this topic is often overlooked even though it can be very useful. This blog (my first on Codeforces, yaay) is thus rather intended for beginners in C++. I'll describe a technique that makes sorting fast to implement &mdash; lambdas. For simplicity, arrays will always mean `vector` in this blog. There are two main usages of sorting I want to describe: #### 1. Sorting an auxiliary array to keep the original array unchanged. This is often the case when our data is splitted into several separate arrays, that are somehow connected together. This may occur when each type of data is given in separate rows. For example, one array could contain a value of a cell and the other one &mdash; it's color. Say that we want to simultaneously sort both those arrays by value (increasing). In order to do that, we may rather introduce a new a...
Let's break down the lambda expression. It contains three types of brakets:

Full text and comments »

  • Vote: I like it
  • +65
  • Vote: I do not like it

122.
By Osama_Alkhodairy, history, 7 years ago, In English
[Insight] Number of Topological Orderings of a Directed Tree I was checking [this](https://csacademy.com/contest/round-11/task/connected-tree-subgraphs/statement/) problem on csacademy, and I came up with the dp combinatorics solution to calculate the number of topological orderings of a directed tree with a fixed root. First, let me explain this solution. Let's root the tree at node $1$ and calculate $sz_v$ = size of the subtree rooted at $v$. Let $dp_v$ be the number of possible topological orderings of the subtree rooted at $v$. To calculate $dp_v$, let's imagine $v$ has only two children: $x$ and $y$. We can see quite easily that $dp_v = dp_x * dp_y * {sz_x+sz_y \choose sz_x}$. That's because any valid topological ordering of the subtree of $v$ will begin with $v$ itself and then $sz_x+sz_y$ nodes, and because the nodes of $x$'s and $y$'s subtrees are independent, all possible combinations between them are possible. So, we will choose $sz_x$ spots of the $sz_x+sz_y$ spots and put in them all the nodes form $x$'s subtree and put on the res...
I felt really unsatisfied after all these reductions because the final expression didn't make sense

Full text and comments »

  • Vote: I like it
  • +88
  • Vote: I do not like it

123.
By eatmore, history, 6 years ago, In English
My experience with Microsoft Q# Coding Contest Here I want to tell my personal opinion of the [Microsoft Q# coding contest](/blog/entry/77614). First, I'd like to thank Microsoft Quantum team for making a great contest in an unusual format. All the problems were interesting (except D problems ‒ more about them below), and I'm looking forward to similar contests in the future. However, there is a number of issues that I'd like to see discussed and hopefully fixed. The tools --------- The first problem with Q# compiler that everyone trying to use it will see is that it is SLOW. On my machine, compiling a trivial Hello World program takes about 45 seconds. This is a well known problem, reported both on [GitHub](https://github.com/microsoft/qsharp-compiler/issues/436) and even [here on Codeforces](/blog/entry/77614?#comment-642186), and frankly it's a PITA to wait so much after every fix to know if your code still compiles (or still doesn't). But this is only a tip of the iceberg. Before the contest, I decided to read the sou...
parsing an expression, they at some point try to parse it as a function call (which would first parse

Full text and comments »

  • Vote: I like it
  • +264
  • Vote: I do not like it

124.
By adamant, history, 4 years ago, In English
Fourier transform on groups. Part 1: Irreducible representations Hi everyone! Consider the following problem. You're given two arrays $a_1, a_2, \dots, a_{n!}$ and $b_1, b_2, \dots, b_{n!}$. You need to compute the array $c_1, c_2, \dots, c_{n!}$, such that $$ c_k = \sum\limits_{i \circ j = k} a_i b_j, $$ where $i \circ j$ denotes the composition of the $i$-th and the $j$-th lexicographically smallest permutations of $n$ elements. Generally, typical approach to such things would be to escape into space in which the convolution corresponds to the component-wise product of two vectors, and then to transform back into initial space. For example, with the summation rule being $i + j \equiv k \pmod n$, it is well known that the corresponding transform is exactly the discrete Fourier transform of vectors $a_i$ and $b_j$. But with more generic groups, things may be much more complicated, and I will write a series of blog posts explaining it. * **Fourier transform on groups. Part 1: Irreducible representations** * **[Fourier transfor...
, \dots$, then we compute $A(x_t)$ and $B(x_t)$ for each $t$, from which we get theexpression for

Full text and comments »

  • Vote: I like it
  • +98
  • Vote: I do not like it

125.
By danilka.pro, history, 11 years ago, In English
Codeforces Round #323 Editorial **Adiv2** To solve the problem one could just store two arrays $hused[j]$ and $vused[j]$ sized $n$ and filled with false initially. Then process intersections one by one from $1$ to $n$, and if for $i$-th intersections both $hused[h_i]$ and $vused[v_i]$ are false, add $i$ to answer and set both $hused[h_i]$ and $vused[v_i]$ with true meaning that $h_i$-th horizontal and $v_i$-th vertical roads are now asphalted, and skip asphalting the intersection roads otherwise. Such solution has $O(n^2)$ complexity. Jury's solution: [submission:13390628] **Bdiv2** It is always optimal to pass all the computers in the row, starting from $1$-st to $n$-th, then from $n$-th to first, then again from first to $n$-th, etc. and collecting the information parts as possible, while not all of them are collected. Such way gives robot maximal use of every direction change. $O(n^2)$ solution using this approach must have been passed system tests. Jury's solution: [submission:13390612] *...
Now, we could parse expression given input into binary tree. I should notice that the number of non

Full text and comments »

  • Vote: I like it
  • +106
  • Vote: I do not like it

126.
By 0t0infinity, history, 6 months ago, In English
(Intermediate Part) — Bits That Changed My CP Thinking ! This is the **Part-2** of my Bitwise Operations Blog. In this part, I focused more on intermediate-level bitwise tricks, Common CP Patterns and a few slightly advanced techniques that appear frequently in contest. &mdash; [**Part-1 &mdash; Click Here**](https://codeforces.me/blog/entry/153600) I tried to explain the intuition and thinking process behind each trick as clearly and simple as possible. And as always, Heartfelt thanks to `Raha Ahmed` for her endless encouragement, strongest support and constant belief in me ! --- # Core Concepts You Must Understand First :- --- Intermediate level Bitwise Problems in CP rarely ask you to just "check" or "set" a bit. Instead, they require you to use the Mathematical Properties of bits to optimize your code. Before we jump into the 8 Master Pattern, you need to firmly understand these 5 core concepts. If you understand these the upcoming patterns will feels like magic ! --- <spoiler summary="Core Explan...
Let's look at the expression: `sub = (sub - 1) & mask`.

Full text and comments »

  • Vote: I like it
  • +75
  • Vote: I do not like it

127.
By mohammedehab2002, history, 9 years ago, In English
Codeforces round #435 editorial [problem:862A] One can see that in the final set all the elements less than $x$ should exist, $x$ shouldn't exist and any element greater than $x$ doesn't matter, so we will count the number of elements less than $x$ that don't exist in the initial set and add this to the answer, If $x$ exists we'll add 1 to the answer because $x$ should be removed . Time complexity : $O(n+x)$ . Solution link (me) : https://pastebin.com/ALfcu8Ab . Solution link ([user:mahmoudbadawy,2017-09-17]) : https://pastebin.com/yXLkmA5F . [problem:862B] The tree itself is bipartite so we can run a dfs to partition the tree into the 2 sets (called bicoloring), We can't add an edge between any 2 nodes in the same set and we can add an edge between every 2 nodes in different sets, so let the number of nodes in the left set be $l$ and the number of nodes in the right set be $r$, The maximum number of edges that can exist is $l*r$, but $n-1$ edges already exist so the maximum number of edges to be ad...
**observation:** We don't have to try all the possible values of $f(j)$ to minimize theexpression, Now we have a data-structure that can get us the minimum value of the expression once given the

Full text and comments »

  • Vote: I like it
  • +88
  • Vote: I do not like it

128.
By fatalerror, history, 15 months ago, In English
Python Optimization Tricks in Competitive Programming > For better reading experience in Chinese, please refer to: [LeetCode](https://leetcode.cn/discuss/post/3746464). # Preface This article introduces techniques to reduce runtime in competitive programming using Python, under the premise that the complexity remains **correct** and **unchanged**. Each technique is accompanied by a Speedup on CPython 3.11.5 / PyPy 3.10.13. # I/O ### Use fast input Replace the built-in `input` with `sys.stdin.readline`. Each `input()` call incurs prompt handling and a `sys.stdin` lookup, while `readline()` reads a line directly. The more input lines, the larger the gap. Speedup: CPython ~×4.2; PyPy ~×16.4. ~~~~~ import sys input = lambda: sys.stdin.readline().rstrip() # strip the trailing newline II = lambda: int(input()) LII = lambda: list(map(int, input().split())) ~~~~~ ### Read all input at once Use `sys.stdin.read().split()` to read everything into memory once, then consume as needed. This avoids calling the read fun...
For functions accepting an iterable, pass a generator expression directly instead of building a

Full text and comments »

  • Vote: I like it
  • +94
  • Vote: I do not like it

129.
By adamant, history, 5 years ago, In English
Some rotational invariants in geometry Hi everyone! Today I'd like to write about some polynomials which are invariant under the rotation and relabeling in euclidean spaces. Model problems work with points in the 3D space, however both ideas, to some extent, might be generalized for higher number of dimensions. They might be useful to solve some geometric problems under the right conditions. I used some ideas around them in two problems that I set earlier. #### Congruence check in random points You're given two set of lines in 3D space. The second set of lines was obtained from the first one by the rotation and relabeling. You're guaranteed that the first set of lines was generated uniformly at random on the sphere, find the corresponding label permutation. Actual problem: [problem:102354F]. ##### Solution Let $P_4(x, y, z) = \sum\limits_{l=1}^n \left((x-x_l)^2+(y-y_l)^2 + (z-z_l)^2\right)^2$. It is a fourth degree polynomial, which geometric meaning is the sum of distances from $(x, y, z)$ to all points i...
expression is invariant under rotation transform. On the other hand it may be rewritten as

Full text and comments »

  • Vote: I like it
  • +107
  • Vote: I do not like it

130.
By mohammedehab2002, 8 years ago, In English
Codeforces round #525 editorial [problem:1088A] --------------- Well, the constraints allow a brute-force solution, but here's an $O(1)$ solution: If $x=1$, there's no solution. Otherwise, just print $x-x\%2$ and 2. Code link: https://pastebin.com/LXvuX8Ez Time complexity: $O(1)$. [problem:1088B] --------------- Let $s$ be the set of numbers in input (sorted and distinct). In the $i^{th}$ step, $s_i$ is subtracted from all bigger or equal elements, and all smaller elements are 0. Thus, the answer in the $i^{th}$ step is $s_i-s_{i-1}$ ($s_0=0$). Code link: https://pastebin.com/bpz1YxBe Time complexity: $O(nlog(n))$. [problem:1088C] --------------- The editorial uses 0-indexing. Both solutions make $a_i=i$. #### First solution, n adds and 1 mod First, let's make $a_i=x*n+i$ (for some $x$). Then, let's mod the whole array with $n$ (making $a_i=i$). If the "add update" changed one index, we can just add $i+n-a_i\%n$ to index $i$. The problem is, if we make $a_i=x*n+i$, then updat...
$. Then, the expression in the problem is equivalent to $average(b_1,b_2,\ldots,b_k)$. Assume we only

Full text and comments »

  • Vote: I like it
  • +116
  • Vote: I do not like it

131.
By accord, history, 8 months ago, In English
Codequest 2.0 — Editorial ### [Problem A &mdash; A "tiny" love story](https://codeforces.me/gym/680185/problem/A) Problem Idea by: [user:notalone008,2026-03-25] <br> Problem Preparation by: [user:notalone008,2026-03-25] <br> <spoiler summary="Solution"> The clock only shows values from **0 to 59** and wraps around (modulo 60). The only thing to be checked here was if the call duration was a multiple of 60 seconds or not. - If s % 60 == 0 → print "NO" - Else → print "YES" </spoiler> <spoiler summary="Code"> ~~~~~ #include <bits/stdc++.h> using namespace std; //--------code begins here-------- void solve() { int s; cin >> s; if(s % 60) cout << "YES"; else cout << "NO"; } int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int T = 1; cin >> T; while (T--) { solve(); cout << endl; } return 0; } ~~~~~ </spoiler> ### [Problem B &mdash; God is 1 and his name is 1](https://codeforces.me/gym/680185/problem/B) Problem Ide...
We are given the expression:

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it

132.
By AlexLuchianov, 5 years ago, In English
How NOT to use macros *"I used to be a competitive programmer like you, but then I took a macro to the knee."* First I want to say that I recognize the fact that not all macros are bad, there are even some ingenious macros that are really useful such as the `all(x)` macro from the post [C++ tips and tricks](https://codeforces.me/blog/entry/74684) by [user:Golovanov399,2022-03-16] . Another useful macro is `NDEBUG`. This macro is used to disable all assertion checks inside the code. It can be used like this: ~~~~~ #define NDEBUG #include <cassert> ~~~~~ Note that `NDEBUG` has to be defined before including `cassert` to have an effect. Other useful macros are the debug macros, a little more information about them can be found in the following blog, [Compilation and debugging tutorial](https://codeforces.me/blog/entry/79024) by [user:ramchandra,2022-03-16]. However, for every one such great macro there exist another countless macros that are, let's just say, not that great. Here are some reaso...
]$. Then since $f(n - 1)$ was bigger and the expression `f(n - 1)) < (v[n])` is true it decides to

Full text and comments »

  • Vote: I like it
  • +280
  • Vote: I do not like it

133.
By craus, 11 years ago, In English
Codeforces Round #335 Problem Analysis [problem:606A]. Let’s count how many spheres of each type are lacking to the goal. We must do at least that many transformations. Let’s count how many spheres of each type are extra relative to the goal. Each two extra spheres give us an opportunity to do one transformation. So to find out how many transformations can be done from the given type of spheres, one must look how many extra spheres there are, divide this number by 2 and round down. Let’s sum all the opportunities of transformations from each type of spheres and all the lacks. If there are at least that many opportunities of transformations as the lacks, the answer is positive. Otherwise, it’s negative. [problem:606B]. Let’s prepare a matrix, where for each cell we will hold, at which moment the robot visits it for the first time while moving through its route. To find these values, let’s follow all the route. Each time we move to a cell we never visited before, we must save to the corresponding matrix’ cell, how many a...
We will keep estimating expression for each vertex in the form of m(x) = A[x] * m(x) + B[x]., ] (this is just the same as coefficient before m(x) in the expression).

Full text and comments »

  • Vote: I like it
  • +75
  • Vote: I do not like it

134.
By Egor, history, 5 years ago, In English
Rust 1.58 Rust 1.58 was just released (rust releases new version every 6 weeks). The only feature relevant to competitive programming is this: #### Captured identifiers in format strings Format strings can now capture arguments simply by writing `{ident}` in the string. Formats have long accepted positional arguments (optionally by index) and named arguments, for example: ~~~~~ println!("Hello, {}!", get_person()); // implicit position println!("Hello, {0}!", get_person()); // explicit index println!("Hello, {person}!", person = get_person()); // named ~~~~~ Now named arguments can also be captured from the surrounding scope, like: ~~~~~ let person = get_person(); // ... println!("Hello, {person}!"); // captures the local `person` ~~~~~ This may also be used in formatting parameters: ~~~~~ let (width, precision) = get_format(); for (name, score) in get_scores() { println!("{name}: {score:width$.precision$}"); } ~~...
complicated arguments, either assign them to a local name first, or use the older name =expression

Full text and comments »

  • Vote: I like it
  • +107
  • Vote: I do not like it

135.
By BrayanD, history, 5 years ago, In English
Editorial of Codeforces Round #768 ### [problem:1631A] Author: [user:humbertoyusta,2022-01-27] <spoiler summary="Hint 1"> Think about how $max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$ will contribute to the answer. </spoiler> <spoiler summary="Hint 2"> The maximum of one array is always $max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$. How should you minimize then? </spoiler> <spoiler summary="Solution"> Let $m_1 = \max(a_1, a_2, ..., a_n, b_1, b_2, ..., b_n)$. The answer will always be $m_1 \cdot m_2$ where $m_2$ is the maximum of the array that does not contain $m_1$. Since $m_1$ is fixed, the problem can be reduced to minimize $m_2$, that is, minimize the maximum of the array that does not contain the global maximum. WLOG assume that the global maximum will be in the array $b$, we can swap elements at each index $x$ such that $a_x > b_x$, ending with $a_i \leq b_i$ for all $i$. It can be shown that the maximum of array $a$ is minimized in this way. Time complexity: $O(n)$ <spoiler ...
factor $tot_{n/x} \cdot \frac{1}{(n/x)\cdot(n/x-1)}$ in the previous expression it only remains to find

Full text and comments »

  • Vote: I like it
  • +246
  • Vote: I do not like it

136.
By wuhudsm, history, 19 months ago, In English
TheForces Round #42 (Ultimate-Answer-Forces) Editorial [A](https://codeforces.me/gym/105846/problem/A) Idea:[user:wuhudsm,2025-01-23] <spoiler summary="solution"> There are $n$ valid $x=n+k(0\le k<n)$. So the answer is $n$. </spoiler> <spoiler summary="code(C++)"> ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef pair<double, double> pdd; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<double> vd; typedef vector<string> vs; typedef vector<vi> vvi; typedef vector<vvi> vvvi; typedef vector<vll> vvll; typedef vector<vvll> vvvll; typedef vector<pii> vpii; typedef vector<vpii> vvpii; typedef vector<pll> vpll; typedef vector<vpll> vvpll; typedef vector<pdd> vpdd; typedef vector<vd> vvd; #define yn(ans) printf("%s\n", (ans)?"Yes":"No"); #define YN(ans) printf("%s\n", (ans)?"YES":"NO"); template<class T> bool chmax(T &a, T b) { if (a >= b) return false; a = b; return true; } template<class T> bool ch...
$. This expression is a product of $8$ binomial terms and when expanded, it will have $2^8 = 256

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

137.
By Al.Cash, 10 years ago, In English
Geometry: 2D points and lines [Tutorial] I get an impression that a lot of coders struggle with geometric problems and prefer to avoid them. That's not much of a surprise, considering that I couldn't find a good writing explaining the basics and giving useful advice how to proceed. Moreover, some resources obfuscate this beautiful area to the point it's despised by the readers. I'll try to change that, but first I'll mention some of the better resources: [geomalgorithms.com](http://geomalgorithms.com/points_and_vectors.html) This is where you can start if you don't have a basic notion of a vector. Also there are more detailed explanations for some examples I'll list, but I dislike the implementations. [This post in Russian](http://codeforces.me/blog/entry/6642) has a link to the code that's most similar to mine, with some comments (unfortunately, also is Russian)[cut]. ### Point structure and operations Without further ado, I'll start with my code for the `Point` structure. Explanations are below, so don't rush t...

Full text and comments »

  • Vote: I like it
  • +222
  • Vote: I do not like it

138.
By potatoArmy, history, 6 months ago, In English
Cheaters in Round 1100 ### [user:thegscrypto.bot,2026-05-24] Evidence ------------------ 1. Lots of WA1/RE1/Compilation Error submissions 2. AI commented codes: [submission: 375834481] [submission: 375825486] [submission:375825486]. Mostly all of his submission are like this **Do you think its a cheater?** Yes! No, (comment why you think this) ### [user:Harshaii,2026-05-24] Evidence ------------------ AI commented codes: [submission: 375846083 ] [submission: 375846083] **Do you think its a cheater?** Yes! No, (comment why you think this) ### [user:gopal.thecoder,2026-05-24] Evidence ------------------ [submission:375836893]... bruh (if you can't view this submission, here's the code) <spoiler summary="Spoiler"> ~~~~~ I completely understand how frustrating that is! My previous fix strictly resolved the C# compilation error (the variable naming conflict) so your code could finall...
For the right side (`tr1`), you want to maximize the score. Mathematically, the expression you are, expression is:

Full text and comments »

  • Vote: I like it
  • +83
  • Vote: I do not like it

139.
By Egor, 14 years ago, In English
CHelper 3.9 I would really appreciate any new ideas of what new features to add I would also appreciate [donations](https://money.yandex.ru/embed/shop.xml?account=410011732687384&quickpay=shop&payment-type-choice=on&writer=seller&targets=CHelper&targets-hint=&default-sum=100&button-text=03&successURL=) ----- 3.99 Kattis support for both Chrome and Contest parsers. You'd need to accept new permissions for Chrome extension. Good luck at ACM ICPC World Finals online contest! ----- 3.98 Codechef fix ----- 3.97 Fixed issue with template selection and Chrome plugin interaction ----- 3.96 Smallish update &mdash; you can now select task template per task. You can have several templates for general tasks, one where you need to output with Case #, GCJ where you need to integrate parallelization and similar ----- 3.95 Support for Idea 14.1+ Parsers for RCC and USACO fixed You can now parse other Codeforces contests when live contest is ongoing Sorry fo...
GCJ support finally! With it comes new type of input — local regular expression . Main classes

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

140.
By hitman623, 8 years ago, In English
Editorial — Mathmania, Codefest' 18 ### Shooting Game Let $P_{A}$ and $P_{B}$ be the probability of Alice and Bob hitting the target respectively. Then the chances of Alice winning the game are: <br></br> <br></br> <center> $P_{A} + (1-P_{A})(1-P_{B})P_{A} + (1-P_{A})^{2}(1-P_{B})^{2}P_{A} + ...$ </center> which equals $\frac{P_{A}}{1-(1-P_{A})(1-P_{B})}$ using GP formula. Similarly, for Bob it would be $\frac{(1-P_{A})P_{B}}{1-(1-P_{A})(1-P_{B})}$. Equating both we get, $P_{B} = \frac{P_{A}}{1-P_{A}}$. Return -1 in case you get $P_{B}$ greater than 1. ### SolveForTrisha Let $x$ be an $n^{th}$ root of unity. Then, $x^{n} = 1$. So, $x^{n}-1 = 0 $ has roots $1,\alpha_{1},\alpha_{2} . . . . \alpha_{n-1}$. We can write this as follows : <br></br> <br></br> <center> $\frac{(x^{n}-1)}{(x-1)} = (x-\alpha_{1})(x-\alpha_{2})(x-\alpha_{3}) . . . . (x-\alpha_{n-1}) $ </center> Placing $x = 1,-1$ in the above equation and multiplying them, one can get the desired result. <br></br> If $n$ is even the expres...
> If $n$ is even the expression evaluates to $0$ otherwise $n$.

Full text and comments »

  • Vote: I like it
  • +66
  • Vote: I do not like it

141.
By tantam75, history, 7 years ago, In English
Debugging in C++ Hi everyone. This is my template for debugging in C++. I was inspired by Tourist's [source code](https://codeforces.me/contest/1110/submission/49588803) and modified it to my style. Here is it: <spoiler summary="Template"> ~~~~~ #include <bits/stdc++.h> using namespace std; void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.seco...

Full text and comments »

  • Vote: I like it
  • +39
  • Vote: I do not like it

142.
By object022, 15 years ago, In English
Codeforces Round #111 (Div. 2) Solution UPD:Minor mistakes in grammar and expression fixed. Disclaimer: This is not an official editorial. If you have better or easy-to-understand solutions and thoughts, feel free to share your idea. Also welcome to point out mistakes so I can fix it. ### [problem:160A] It's obvious that you should take the most valueable coins. so sort values in non-decreasing order, then take coins from the most valueable to the least, until you get **strictly** more than half of total value. Time complexity depends on the sorting algorithm you use. O(n^2) is also acceptable, but if you use bogosort which runs in O(n!)... ### [problem:160B] Deal with the situation that "first half is strictly less than second half" first. the other one can be solved accordingly. You can use greedy here: sort digits in first and second half seperately. then if the i-th digit in first half is always less than i-th in second half for 1<=i<=n, answer is YES. Time complexity is as same as problem A. Count...
UPD:Minor mistakes in grammar and expression fixed.

Full text and comments »

  • Vote: I like it
  • +51
  • Vote: I do not like it

143.
By Siyah, history, 12 months ago, In English
Euler to AVX: Hi, I'm AmirMohammad (commonly known as **Danet**). I was inspired to write this article after completing my Calculus 1 course to bridge the gap between theory and implementation. Naturally, as a non-native speaker, the translation and editing process involved some assistance. If you spot any technical or linguistic errors, I would be grateful if you pointed them out! ## 1. Mathematical Foundations and Definitions The trigonometric and hyperbolic function families are intrinsically linked through complex analysis, specifically via Euler's formula: $$ e^{ix} = \cos x + i \sin x $$ ### 1.1 Trigonometric Functions (Circular Functions) These functions are defined geometrically based on a point $(x, y)$ on a unit circle of radius 1, where the angle subtended at the origin is $\theta$ (or $x$ radians): $$ \begin{align} \sin x &= y \\ \cos x &= x \\ \tan x &= \frac{\sin x}{\cos x} = \frac{y}{x} \\ \csc x &= \frac{1}{\sin x} \\ \sec x &= \frac{1}{\cos x} \\ \cot x...

Full text and comments »

  • Vote: I like it
  • +21
  • Vote: I do not like it

144.
By JuicyGrape, 2 years ago, In English
Stunning Identity Recently, while working on some combinatorics, I stumbled upon an interesting identity. I haven't seen it mentioned before, so I decided to share it here (with the hope that someone will find it fascinating). The identity $$\displaystyle \sum_{k=0}^{n}(-1)^k\binom{n}{k}(2^{n-k}-1)^m=\sum_{k=0}^{m}(-1)^k\binom{m}{k}(2^{m-k}-1)^n$$ holds for $n, m \geq 1$. We may apply it for specific $(n,m)$ and get interesting results. For example, $\displaystyle \sum_{k=0}^{n}(-1)^k\binom{n}{k}(2^{n-k}-1)=1$ holds because we use the original identity for $m=1$. I encourage everyone to try to prove it by themselves before reading my proof. <spoiler summary="Proof"> The goal is to count the same objects with both left and write parts of the expression. The thing is that the formula is symmetric with respect to $(n,m)$ so the objects should be symmetric as well. I propose to count the following objects: grids of size $n\times m$ which cells are colored into black and white while each row...
. Moreover, I found two more types of objects counted by that expression:

Full text and comments »

  • Vote: I like it
  • +54
  • Vote: I do not like it

145.
By dinohaur, history, 16 months ago, In English
CEOI 2025 discussion Since CEOI 2025 is over and the tasks and test data have been published, can we discuss the solutions here? Here are the [tasks](https://ceoi2025.utcluj.ro/category/13). Upd: you can find the tasks [here](https://codeforces.me/blog/entry/144670?#comment-1293960) (for now) Upd: https://github.com/asociatia-sepi/archive/tree/main/CEOI-2025 Upd: I was upsolving this CEOI now for practice and I decided to write some solutions because I couldn't find them. ## Boardgames ### Solution 1 This is the approach from the official editorial. The core idea relies on a **divide and conquer** strategy: 1. Initially, we invoke the function $f(1, n)$. 2. Find the position $i$ closest to the border such that $i$ and $i+1$ are not in the same connected component. 3. If the subgraph from $L$ to $R$ is connected, we can just return $1$. 4. Otherwise, we split the problem and return $f(L, i) + f(i+1, R)$. The main implementation challenge here is to efficiently maintain graph con...
Since it always holds that this expression is $\ge 1$, it naturally inspires us to use a **segment

Full text and comments »

  • Vote: I like it
  • +70
  • Vote: I do not like it

146.
By __Dangcoder__, history, 2 months ago, In English
Fast I/O in C++ # Fast I/O in C++: A Practical Guide In Competitive Programming, Fast I/O is one of those things that people either use everywhere or completely ignore. Usually, `ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);` is already enough, but when the input and output become really large, a custom implementation can make a noticeable difference. The main idea is simple: avoid doing expensive I/O work more often than necessary. A common approach is to read a large block with `fread`, keep it in memory, and parse the characters directly. For output, we do the opposite: write into a buffer and flush it with `fwrite` when the buffer is full. Here is the Fast I/O implementation I currently use: ```cpp typedef long long ll; typedef unsigned long long ull; #define fast #ifdef fast struct FastIO { int prec = 6; char ib[1 << 21], ob[1 << 21], *p1 = ib, *p2 = ib, *p3 = ob; ~FastIO() { flush(); } inline int gc() { return (p1 == p2 && (p2 = ib + fread(ib, 1, 1 << 21, ...
One edge case worth knowing about is signed integer output. The expression, The character expression

Full text and comments »

  • Vote: I like it
  • -13
  • Vote: I do not like it

147.
By JuicyGrape, 3 years ago, In English
CSES Additional problems tutorial Many thanks to [user:miaowtin,2023-10-01] and [user:FBI,2023-10-01] for their invaluable help and support in the preperation of this blog. Unfortunately, this blog is not currently completed, but we encourage everybody to share their solutions to these and other problems of the section in comments. And last but not least thanks to [user:pllk,2023-10-01] for maintaining CSES. [Shortest Subsequence](https://cses.fi/problemset/task/1087/) <spoiler summary="Prerequisites"> Greedy </spoiler> <spoiler summary="Tutorial"> Consider the string $s=s_1,\dots,s_n$. Suppose $s_i$ is the first occurence of a letter $c$ (the string looks $s_1,\dots,s_i,\dots,s_n$). If we output $c$, the problem reduces to $s=s_{i+1},\dots,s_n$. The number of such outputs must be minimalized. Observation: the largest $i$ we choose, the smallest string we obtain. Greedy solution is always to take the largest $i$ such that $s_i$ is the first occurence. But after this traversal, the string we output is ...
, this expression is impossible. , Consider the following expression $$\displaystyle P_{aux}(x) = (x^{p_0} + x^{p_1} + \dots + x

Full text and comments »

  • Vote: I like it
  • +32
  • Vote: I do not like it

148.
By sidhant, history, 11 years ago, In English
Tutorial on FFT/NTT — The tough made simple. ( Part 1 ) <h4>Aim &mdash; To multiply $2$ $n$-degree polynomials in $O(n*\log n)$ instead of the trivial $O(n^2)$</h4> <i>I have poked around a lot of resources to understand FFT (fast fourier transform), but the math behind it would intimidate me and I would never really try to learn it. Finally last week I learned it from some pdfs and CLRS by building up an intuition of what is actually happening in the algorithm. Using this article I intend to clarify the concept to myself and bring all that I read under one article which would be simple to understand and help others struggling with fft. </i> Let’s get started $\rightarrow$ <br> $\displaystyle A(x) = \sum_{i = 0}^{n - 1} a_i*x^i, B(x) = \sum_{i = 0}^{n - 1} b_i*x^i, C(x) = A(x) * B(x)$ <br> Here $A(x)$ and $B(x)$ are polynomials of degree $n-1$. Now we want to retrieve $C(x)$ in $O(n*\log n)$ So our methodology would be this $\rightarrow$ <br> <ol> <li>Convert $A(x)$ and $B(x)$ from coefficient form to point value form. (FFT) ...
unit, that satisfies the equation $i^2 = -1 $. In this expression, $a$ is the real part and $b$ is the

Full text and comments »

  • Vote: I like it
  • +394
  • Vote: I do not like it

149.
By mfv, history, 11 years ago, In English
Experimental Educational Round: VolBIT Formulas Blitz Editorial #### [A. Again Twenty Five!](http://codeforces.me/problemset/problem/630/A) The problem of getting the last two digits is equivalent to the problem of getting the number modulo $100$. So we need to calculate $5^{n} \mod 100$. According to [cut] the rules of modular arithmetic $(a \cdot b) \mod c = ( (a \mod c) \cdot (b \mod c) ) \mod c$ So $5^{n} \mod 100 = ((5^{n-1} \mod 100) \cdot 5) \mod 100$ Let's note that $5^2=25$. Then $5^3 \mod 100 = ((5^2 \mod 100) \cdot 5) \mod 100 = (25 \cdot 5) \mod 100 = 25$ $5^4 \mod 100 = ((5^3 \mod 100) \cdot 5) \mod 100 = (25 \cdot 5) \mod 100 = 25$ And so on. All $5^n \mod 100$ are equal to $25$ for all $n \ge 2$. So to solve the problem one need to just output `25`. There is no need to read $n$. #### [B. Moore's Law](http://codeforces.me/problemset/problem/630/B) Every second the number is multiplied by $1.000000011$. Multiplication several times to the same number is equivalent to exponentiation. So the formula i...
`L` and `LL` correspondingly are required so that result of the shift expression have 64-bit integer

Full text and comments »

  • Vote: I like it
  • +96
  • Vote: I do not like it

150.
By Sersawy, history, 11 months ago, In English
[Tutorial] Monotonic Stack Optimization for "Last-Segment" DP I recently encountered several problems that looked like standard $O(N^2)$ Dynamic Programming but required a faster solution. I noticed a recurring theme: using **Monotonic Stack** to optimize transitions dependent on range statistics (like min/max/GCD). Sometimes these problems can also be solved using the convex hull trick, but the stack-based approach is often much simpler. However, not all "Monotone Stack DPs" are the same. Sometimes we use the stack to optimize the **transition loop**, and other times we use it to optimize the **input array itself**. In this post, I will explain the intuition behind these two distinct patterns. ----- ## Pattern 1: Optimizing the Transition **Target:** Problems where the cost function behaves like a "Step Function." ### The Problem We are dealing with a 1D DP recurrence of the form: $$dp[i] = \min_{0 \le j < i} \{ dp[j] + \text{cost}(j+1 \dots i) \}$$ Where $\text{cost}(j+1 \dots i)$ depends on a range statistic (e.g., ...
**. For any integer $A$, the expression $\lceil A / V \rceil$ can only take on approximately $2\sqrt

Full text and comments »

  • Vote: I like it
  • +197
  • Vote: I do not like it

151.
By jay_jayjay, history, 15 months ago, In English
Teamscode Summer 2025 Contest Official Editorial Thanks for participating in TeamsCode, and I hope you enjoyed the problems! All problems were written and prepared by [user:hyforces,2025-08-20], [user:Yam,2025-08-20], [user:culver0412,2025-08-20], [user:alexlikemath007,2025-08-20], [user:Jasonwei08,2025-08-20], [user:n685,2025-08-20], [user:HaccerKat,2025-08-20], [user:jay_jayjay,2025-08-20], [user:feining_for_gm,2025-08-20], [user:Mustela_Erminea,2025-08-20], [user:eysbutno,2025-08-20], [user:furyna,2025-08-20], [user:iframe_,2025-08-20], [user:Nyctivoe,2025-08-20], [user:TheYashB,2025-08-20], [user:gggg0,2025-08-20], [user:training4usaco,2025-08-20], [user:ThatRowletOwlet,2025-08-20], and [user:superhelen,2025-08-20]. Also thanks to our testers for valuable feedback, and the Teamscode web and logistics teams for making this contest possible! Also thanks to [user:omeganot,2025-08-24] for writing an unofficial editorial [here](https://codeforces.me/blog/entry/145620). [Novice A/](https://codeforces.me/gym/106042/proble...
expression to the segment tree at index $y_i$. For all blue nodes, we query the segment tree for the

Full text and comments »

  • Vote: I like it
  • +27
  • Vote: I do not like it

152.
By Noureldin, 12 years ago, In English
C++14 from the point of view of a competitive programmer for a competitive programmer the most important features are what C++11 has already introduced namely (range based loops ,lambda expressions ,brace initialization of aggregates, unordered containers ,..... etc) which can be found [here](http://www.quora.com/As-a-competitive-programmer-what-C++11-features-should-I-be-aware-of-and-what-are-some-examples-that-illustrate-their-usage/answer/Brian-Bi) . in addition to: 1) numeric literals now you can separate digits of a number with single quotes ( ' ) to improve readability `auto num = 10'000'000; // num = 10^7` this works for floating numbers as well `auto fnum = 0.000'015'3; // fnum = 1.53 * 10^-5` now you can initialize numbers using their binary form this feature was experimentally included in C++0x (the prototype of C++11) however it didn't become official until the announcement of the new standard `auto bnum = 0b0100'1100'0110; // bnum = (010011000110)2 = (4C6)16 = 1222` //note that the spacing of the quotes...
in C++11 you had to specify the type of the inputs to the lambda expression

Full text and comments »

  • Vote: I like it
  • +57
  • Vote: I do not like it

153.
By UshanGhosh, 2 years ago, In English
Editorial of ShellBeeHaken Presents Intra SUST Programming Contest 2024 — Replay Kindly click the invitation link to access the problems. Contest Invitation : **[ShellBeeHaken Presents Intra SUST Programming Contest 2024 &mdash; Replay](https://codeforces.me/gym/105198)** **[problem:105198A]** Ideas : [user:Youkn0wwho,2024-06-11], [user:Raiden,2024-06-11], [user:UshanGhosh,2024-06-11] <br>Prepared : [user:UshanGhosh,2024-06-11] <spoiler summary="Hint1"> Think about the contribution of each bit to the answer. </spoiler> <spoiler summary="Hint2"> Does all bit contributes equally? </spoiler> <spoiler summary="Solution"> Each bit of $x$ contributes equally to the answer. When does a bit contribute? A bit contributes to the answer if and only if the bit remains set till reaching $0$ depth, *i.e.* $f(0, x)$. If you reset a bit in any depth, it won't contribute to the answer anymore. So for each bit, you have a total $k + 1$ option, reset the bit in any depth from $k - 1$ and $0$, for which it has $0$ contributions, or keep it set till the end,...
Break down the expression that is used to calculate the value of a good

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it

154.
By Noobish_Monk, 2 years ago, translation, In English
Codeforces Round 957 Editorial Thanks [user:K1o0n,2024-07-12] for being the mvp of this round. [problem:1992A] Idea: [user:Vladosiya,2024-07-12] Preparation: [user:K1o0n,2024-07-12] <spoiler summary="Tutorial"> Let's prove why it's always better to add to the smallest number, let $a \le b \le c$, then compare the three expressions: $(a+1)\times b \times c$, $a \times (b+1) \times c$, and $a \times b \times (c+1)$. Remove the common part $a \times b \times c$, and we get: $b \times c$, $a \times c$, $a \times b$. $b \times c \ge a \times c$, since $a \le b$, similarly, $b \times c \ge a \times b$, since $a \le c$. Therefore, we can simply find the minimum $5$ times and add one to it. And thus, obtain the answer. Another, primitive approach is to simply iterate through what we will add to $a$, $b$, and $c$ with three loops. Since we can only add $5$ times, the time complexity of the solution is $O(1)$. </spoiler> <spoiler summary="Solution (Python)"> ~~~~~ for _ in range(int(input())): ...

Full text and comments »

  • Vote: I like it
  • +45
  • Vote: I do not like it

155.
By ACGN, history, 2 years ago, In English
About 2031C (Penchick and BBQ Buns, problem C of CF Round 987), and extra challenges Author of the problem [problem:2031C] here, hope you enjoyed the contest yesterday (Almost exactly 24 hours ago...)! Looking at the votes on [the editorial](https://codeforces.me/blog/entry/136260), it's obvious that it's a very polarizing problem: an hour or so after the contest, the problem had roughly equal numbers of "likes" and "dislikes", and now (as of writing) there are around 320 likes to 200 dislikes. Of course, this is completely predictable: the opinions on this problem were quite polarized for a few reasons: 1. Troll and WA trap: it's **very** easy to fall into the trap of thinking that there is no solution for all odd $n$; thus, **over 12,900** (!) WA on pretest 2 solutions were received, as compared to only 4,700ish Accepted solutions. This ratio seems a bit extreme for a problem C; in the previous Div.2's problem C ([problem:2028C]), there were 3,500ish Rejected solutions to 2,500ish Accepted ones. 2. The construction: hard-coding the case $n=27$ seems weird an...
$n-2m^2=O(\sqrt{n})$. Thus, the expression is $F(n)\le \frac{2m^2}{3}+9+O(\sqrt{n})=\frac{n}{3}+O

Full text and comments »

  • Vote: I like it
  • +103
  • Vote: I do not like it

156.
By PraveenDhinwa, 13 years ago, In English
Sieve Methods : Prime, Divisor, Euler Phi etc. **The blog is not yet complete. I just **mistakenly** clicked post button. So it is still in writing, I have to add formatting to it. Sorry for inconvience** Structure of the article. First I will explain what does sieve mean. Then I will give you some examples with corresponding java codes and finally some exercises :) According to http://www.thefreedictionary.com/sieve , "sieve" means A utensil of wire mesh or closely perforated metal, used for straining, sifting, ricing, or puréeing. Similar to this definition sieve is a method of doing stuff, where you keep rejecting the things that are useless and reducing the space that you are currently looking at. So much of thing in air, Let us now take an example. 1. **Finding primes upto N.** You have to print all primes upto N. _Method1_ : For all the numbers i from 1 to N, check if i is prime or not. If it is a prime, then print it. _Subproblem_ : Checking whether a number K is prime...
multiples of i upto n are n / i. Hence Expression for the complexity will be written as n / 2 + n, Now as the expression is definitely greater than n. So adding an n to the expression won't have any

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it

157.
By Michael, 13 years ago, translation, In English
Yandex.Algorithm Qualification Round Analysis Qualification Round and its analysis were prepared by [user:Chmel_Tolstiy,2013-07-11], [user:aropan,2013-07-11], [user:Romka,2013-07-11], [user:SobolS,2013-07-11], [user:Ra16bit,2013-07-11], [user:snarknews,2013-07-11] and [user:Gassa,2013-07-11]. 1732 participants have started in the Qualification Round of Yandex.Algorithm, 1606 of them have made at least one attempt, 1558 have solved at least one problem. Interestingly, the number of registered participants was 3397 which is almost twice as much as the number of participants who have started the round. We don't know why is that. As the qualification round was a virtual contest, participants could choose the most convenient time to compete. The maximum number of participants online (around 280) was at the start, the minimum number &mdash; between 3 a.m. and 4 a.m. Moscow time (around 20 participants). First one chronologically who solved all 6 problems was **Scott.Ai** from China; all problems were submitted "open". Soon **i.met...
Let us make several transformations of the expression:

Full text and comments »

  • Vote: I like it
  • +75
  • Vote: I do not like it

158.
By robinyqc, history, 3 years ago, In English
Generate a Sequence With No Duplicate Uniformly at Random Given a continuous range &mdash; $V$, and the length of the sequence &mdash; $n$, how can a sequence with no duplicates be generated uniformly at random? For a sequence $S$, we say it has no duplicate if and only if $\forall i\neq j, S_i\neq S_j$. This is very useful for sampling. For example, you have an array $a$, and you want to select some samples to calculate their variance. The general way is to generate an index sequence and select the element with the generated indices. For example, in Python we use `random.sample` to do this. Here I will show some ways to generate such a sequence. ### Method 1 Let's consider the simplest algorithm. We can put the entire value range directly into an array and then shuffle it. If we take the first $n$ elements, we get a generation complexity of $O(|V|)$. However, shuffling has a high constant factor, so the whole process can be seen as $O(|V|w)$, where $w$ is a constant factor. Is there a better approach? Actually, there's an ev...
Thanks to ChatGPT and DeepL. They helped me to improve the English expression of this blog.

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it

159.
By XDEv11, 6 years ago, In English
"Efficient and easy segment trees" proof Hey, codeforces community, this is my first blog, so your suggestions are very welcome. Also, I am not a native speaker. Please excuse language errors and let me know. I recently found this blog entry, [Efficient and easy segment trees](https://codeforces.me/blog/entry/18051). It's an old post from six years ago, so there might be a proof about this. However, I don't see one by far. That's why I try to write it. Hope it will help someone who wants to know this a little bit more. ### Definition We call a node legal if 1. It's between `n` and `n + (n - 1)`. (an array element) 2. Both its children are legal and represent subarrays of same size. (a combined value from two children) Otherwise, it's called illegal. ### No overlaps Let $[L_i:R_i)$ be the left-closed right-open interval of the i-th layer from bottom (a continuous sequence of legal nodes that represent subarrays of same size.). We know that $L_0=n$ and $R_0=2n$, and we have $L_{i+1}={\Large\lceil}\frac...

Full text and comments »

  • Vote: I like it
  • +109
  • Vote: I do not like it

160.
By Nickolas, 10 years ago, translation, In English
April Fools Day Contest 2017: editorial Incredibly, 34 people managed to solve all problems! 1032 participants solved at least one problem, and it wasn't always A :-) #### [problem:784A] Traditionally the first problem of April Fools Day contest asks to recognize a sequence of integers by problem title and (this time) a single data point. OEIS search for just the given number isn't going to give a result &mdash; or rather is going to give too many to be useful. However, if you look for the problem title, the first result for "numbers joke" query will give you https://oeis.org/A006753 "Smith (or joke) numbers", which has 27 as its 3rd element. #### [problem:784B] This problem is a variation on a [kid's riddle](http://codeforces.me/predownloaded/31/a2/31a26647d3b860e3a6e9cb82acf532d1059b1da0.jpg) in which you have to count closed loops in digits of the number &mdash; one in 4, 6, 9 and 0 and two in 8. [cut] Since we're programmers here, we had to count loops in digits in hexadecimal notation of the number (writi...
evaluate the given expression. One could take a long way: generate commands to write numbers to

Full text and comments »

  • Vote: I like it
  • +87
  • Vote: I do not like it

161.
By Geothermal, history, 7 years ago, In English
AtCoder Beginner Contest 139 English Solutions #A &mdash; Tenki This is a fairly simple task--just iterate over all positions in the strings and count the ones where S[i] = T[i]. Runtime: $O(|S|)$. [Click here for my submission.](https://atcoder.jp/contests/abc139/submissions/7247680) --- #B &mdash; Power Socket Note that we already have one socket, so we need to fill $B-1$ more sockets. Additionally, each new outlet we add will take up one socket and add $A$ sockets, resulting in a net addition of $A-1$ sockets. We thus need to create at least $B-1$ sockets where each outlet gives us $A-1$ sockets, making our answer $\lceil \frac{B-1}{A-1} \rceil$. Since most programming languages use floor division, we can also express this as $\lfloor \frac{A+B-3}{A-1} \rfloor$. Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc139/submissions/7249379) --- #C &mdash; Lower We essentially use two pointers. Maintain the starting position at zero. Then, while the next position isn't hi...
the big-O expression (though this made it somewhat faster in practice--I sorted the candidate points

Full text and comments »

  • Vote: I like it
  • +116
  • Vote: I do not like it

162.
By polyhistor13, 15 months ago, In English
Using Lambda's for CP First of all, for whom this blog is (Ideally). -> Someone interested in learning and at least have a good knowledge of programming in c++. -> Want's to increase speed and code cleaner. Regardless everyone is Welcome!!!! What is Lambda? ------------------ Well lambda are so called **anonymous functions** which can sometimes really help for **faster coding** and **ease of writing**. ### Basic structure of Lambda First let's see how does a **lambda** look like, " [] () {} ; ". The first part, " [] " The **Capture Clause**: This is the **most powerful** part of a lambda. It defines what the lambda can "see" from its surrounding scope. -> []: Captures _nothing_. The lambda can only use its own parameters or global variables. -> [=]: Captures all _outside variables by value_ (makes a copy). -> [&]: Captures all _outside variables by reference_ (can modify the originals if '**const**' not used). -> [var1, &var2]: Captures var1 by value and var2...

Full text and comments »

  • Vote: I like it
  • +70
  • Vote: I do not like it

163.
By literalchild, history, 6 months ago, In English
Congratulations ChatGPT 5.5 Plus for getting 602/600 in SEATST Congratulations ChatGPT for obtaining a total score of $602$ out of $600$ in SEATST! Here is its distribution: Day 1: $100 + 100 + 100 = 300$ Day 2: $102 + 100 + 100 = 302$ # Explanation ChatGPT managed to solve [Problem 2A: Triple Circuit](https://tlx.toki.id/problems/seatst-2026/2A) using just $213$ logic gates (you needed to use $\leq 215$ logic gates to obtain full score). If we use the scoring function $f(K) = 1 - 0.40 \times \frac{K - 215}{41}$ (since no one expected $K < 215$ to be within the domain of $f$), this gives $f(213) = 1.0195$, which is a score of $102$ (TLX rounds scores to the nearest integer). <spoiler summary="ChatGPT's solution"> First pair the $128$ bits into $64$ pairs and calculate the OR of each pair. If there is an anomaly, at least $2$ pairs will have an OR of $1$. Construct a tripartite graph, where the three parts have sizes $4$, $5$ and $5$ respectively. Call the parts $A$, $B$, $C$. This graph has a total of $4 \times 5 + 4 \times 5 + ...
same for $B$ and $C$ - $5$ gates for the expression $g_A \bigvee g_B \bigvee g_C \bigvee (f_A

Full text and comments »

  • Vote: I like it
  • +101
  • Vote: I do not like it

164.
By SHaF3Y, history, 6 months ago, In English
A Sneaky C++ Bug: AC on Clang, WA on GCC **I used Ai to format the Blog** While solving the problem [TTM on SPOJ](https://www.spoj.com/problems/TTM/) using a Persistent Segment Tree, I ran into a very frustrating bug My code was logically correct, yet I was getting completely different verdicts depending on the compiler: * **Accepted** on `C++14 (Clang)` * **Wrong Answer** on `C++14 (GCC)` After a long debugging, the issue turned out to be caused by **unspecified evaluation order** [Code](https://ideone.com/uXMeOB) Here is the problematic line: ```cpp // 't' is the current version number of the Persistent Segment Tree if (op == 'C') { int l, r, d; cin >> l >> r >> d; --l, --r; // The fatal line: pst.roots[++t] = pst.update(t, l, r, d); } ``` ## What’s the Problem? In **C++14 and older**, the C++ standard does **not specify** the evaluation order of the operands of the assignment operator (`=`) That means the compiler is free to evaluate either: * the left-hand s...

Full text and comments »

  • Vote: I like it
  • +83
  • Vote: I do not like it

165.
By Spheniscine, history, 7 years ago, In English
Addendum: Optimized variant of Barrett reduction + proof re: ultimate NTT article This is an extension of [my article proposing the "ultimate" NTT](https://codeforces.me/blog/entry/75326). Here I will present a simplified and optimized variant of the Barrett reduction algorithm on that page. As it relaxes certain bounds of the standard parameters of the algorithm, I will also present a proof of the correctness of the variant, at least for this specific case. First, the algorithm: ~~~~~ function mulMod(a: Long, b: Long): Long { xh = multiplyHighUnsigned(a, b) // high word of product xl = a * b // low word of product g = multiplyHighUnsigned( (xh << 2) | (xl >>> 62) , BARR_R) t = xl - g * MOD - MOD t += (t >> 63) & MOD return t } ~~~~~ Notice that the middle routine has been greatly simplified; instead of computing the high and middle words of $xr$, we simply take the top 64 bits of $x$, in effect computing $\displaystyle \left\lfloor \left\lfloor \frac{x}{2^{62}} \right\rfloor \frac{r}{2^{64}} \right\rfloor$ in place o...
Recompose the leftmost expression: $\displaystyle \frac x n - \left(\frac {\varepsilon x} {4^k

Full text and comments »

  • Vote: I like it
  • +47
  • Vote: I do not like it

166.
By alexlikemath007, 4 years ago, In English
A proper tutorial for one of the craziest 3D-geometry problems Warning: This problem is like the warden of competitive programming. It is a force of nature &mdash; like a hurricane, and when you see a hurricane you don't fight it, you run. It is a big bad boss with a bunch of hitpoints, and deals big damage to your sanity. But when you kill it, it doesn't drop much loot, experience, or educational value compared to other problems. It would be wiser to go and solve some problems and learn how to use binary search. The problem: https://codeforces.me/gym/102452/problem/F It's tutorial says: Since n is small, $O(n^2)$ simulation is OK. Advanced 3-D geometry methods are highly required. The tutorial doesn't describe what the advanced 3-D geometry methods are. So, I have written this blog to remedy that gap. <spoiler summary="Chapter 1. Prologue"> You should create a `point` struct this makes things a bit easier. It has an `double x`, `double y`, `double z` coordinate. This point will be immensely useful, as we can define a line segment...
{2z} - p_{1z})t)$. Simplifying, we will get an expression where we have constants $a, b, c, d, e, f

Full text and comments »

  • Vote: I like it
  • +434
  • Vote: I do not like it

167.
By dnshgyl21, history, 4 years ago, In English
Newton Editorial 2022 October [A. Completing the square](https://my.newtonschool.co/playground/code/b5o0maa29vy5/) ------------------ <spoiler summary = "Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; cout<<n*n<<endl; } ~~~~~ </spoiler> [B. Fireworks](https://my.newtonschool.co/playground/code/t5x2lwkk9r09/) ------------------ <spoiler summary = "Hint"> What is the maximum possible value of $d(M)$. </spoiler> <spoiler summary = "Solution"> We can see that for $ M \le 10^18$, the maximum possible value of $d(M)$ is only $ 9 * 18$ attained for $999999999999999999$. So for finding the number of solutions for a given $N$, we can iterate over all the values of $d(M)$ upto $9 *18$, and then check if $d(N/p) == p$. </spoiler> [C. Lights](https://my.newtonschool.co/playground/code/8vn89k2p7y5e/) ------------------ <spoiler summary = "Hint"> Try solving the easier version of the problem where we only need to find the number of distin...
This expression can now be evaluated for all $i$ using FFT with coefficients as the terms in the

Full text and comments »

  • Vote: I like it
  • +29
  • Vote: I do not like it

168.
By Romka, 14 years ago, translation, In English
Codeforces Round #127 — editorial #### Problem A(div 2) --- LLPS It's assumed that this problem can be solved just looking at the samples and without reading the statement itself :) Let's find the letter in the given string which comes last in the alphabet, denote this letter by $z$. If this letter occurs $p$ times in the given string, then the answer is string $a$ consisting of letter $z$ repeated $p$ times. Why is it so? Using the definition of lexicographical comparison and the fact that $z$ is the largest letter in the string it's easy to understand that if some other subsequence $b$ of the given string is lexicographically larger than $a$, then string $b$ should be longer than $a$ and, moreover, $a$ should be a prefix of $b$ (that is, $b$ should start with $a$). But string $b$ must be a palindrome, therefore its last letter must be $z$. In this case string $b$ must contain more occurrences of letter $z$ than the original string $s$ does, which is impossible as $b$ is a subsequence of $s$. Beside...
minimum possible. This expression can be rewritten as $\sum_{i,j} c_{ij}(x-x_i)^2 + \sum_{i,j} c_{ij, expression for all $i \le j$ and recalculate it when moving to the next $j$, comparing $(left_j

Full text and comments »

  • Vote: I like it
  • +88
  • Vote: I do not like it

169.
By UnexpectedValue, 3 years ago, In English
Calculating Series Sums with Binary Exponentiation I could not find any article or blog on this idea, and felt having one could be helpful to many. There might be unwanted errors, so please feel free to to share any suggestions, corrections or concerns. For those who are unware of Binary Exponentation, [this CP-Algorithms article](https://cp-algorithms.com/algebra/binary-exp.html) or [this video by Errichto](https://youtu.be/L-Wzglnm4dM?si=VL1jTQI537JWwJ4-) can help get familiar with it. #### Introduction Now that we know the idea behind binary exponentiation; let us try expanding the idea. Say, we break the problem into two parts, $L$ and $R$, such that, once we have both the results, combining them gives us our final answer as $ans = L \odot R$, where $\odot$ is an _associative binary operator._ If we can find $R$ as a function of $L$ as in $R = f(L)$ fast enough, say $O(X)$, then our final answer can be found in $O(X\;log(n))$. [cut] The idea is simple enough, so we now have a look at some simple examples. For the sake...
add $1$ instead of $0$, keeping the remainder of the expression same. Thus, handle the odd case is to break the expression as $a^n = a \cdot a^{n-1}$. We can get the answer

Full text and comments »

  • Vote: I like it
  • +153
  • Vote: I do not like it

170.
By 3tao1n, history, 8 years ago, In English
Translation of China NOIP Qualification Round This article is an English translation of the NOIP Round 1 (the Qualification Round) problems. [cut] Here are some backgrounds about it. * [user:matthew99,2018-10-21] has written an [Introduction to Chinese OI contests](http://codeforces.me/blog/entry/51462), but he ignored this for some reason; maybe this exam is too easy for him in his province. * It is literally a "preliminary contest". * Basically, this is a qualification round for NOIP. * This is a written examination. * The exam lasts for 2 hours. * The total score is 100. You may need to get ~80 scores (in provinces like Zhejiang) or ~20 scores (in provinces like Inner Mongolia) to pass. * This translation may be not 100% exact, but you can feel the flavor of the NOIPR1. In part IV and V, the translator modified and formatted the source codes with `clang-format` . ### Part I: Single Choice Problems 2 score for each problem. ##### 1. In the following four numbers in different positional notation, whic...
What is the prefix form (Polish notation) of the expression `a*d-b*c`?

Full text and comments »

  • Vote: I like it
  • +75
  • Vote: I do not like it

171.
By paulzrm, history, 11 months ago, In English
Codeforces Round 1068 (Div. 2) Editorial [2173A-Sleeping Through Classes](https://codeforces.me/contest/2173/problem/A) Idea & Solution: [user:HHH666666,2025-12-05] <spoiler summary="Tutorial"> From the statement we can conclude that a class can be slept through $\textbf{if and only if}$: 1. The class itself is not an important class. 2. The class is not within $k$ classes after any important class. Here's an $O(nk)$ approach: We directly simulate the process: for each important class at position $i$, mark positions $i+1, i+2, \dots, \min(i+k, n)$ as “must stay awake”. After processing all important classes, count the classes that are neither important nor marked. This $O(nk)$ solution is acceptable under the constraints. There's also an $O(n)$ solution: For each unimportant class, we only need to focus on the nearest important class before it. Thus we maintain a variable $last$ storing the index of the most recent important class (or $-\infty$ if none seen yet), then for each $i$ from $1$ to $n$, if it's...

Full text and comments »

  • Vote: I like it
  • +123
  • Vote: I do not like it

172.
By muratt, 11 years ago, In English
Codeforces Round #352 Editorial ###[problem:672A] This one is a simple brute force problem, we will construct our array. Adding numbers between $1$ and $370$ will be enough. After construction we just have to print $n$-th element of array. ###[problem:672B] We observe that in a good string all letters must be different, because all substrings in size 1 must be different. So if size of string is greater than $26$ then answer must be $-1$ since we only have 26 different letters. Otherwise, Let's suppose we have $k$ different letters in string sized $n$, in our string $k$ elements must be stay as before, all others must be changed. So will be ($n$ &mdash; $k$). Here is the [code](https://ideone.com/NJw7V2). ###[problem:671A] Let's solve the problem when Adil and Bera in the same coordinate with bin. Then answer will be $2\times\sum\limits_{i=1}^n distance(Bin, Bottle_i)$, let's say $T$ to this value. [cut] If Adil will take $i$-th bottle and Bera will take $j$-th bottle $(i\neqj)$, then answer ...
for $j$+$1$, we don't need to keep $delta$ array since it will not effect expression. Also observe

Full text and comments »

  • Vote: I like it
  • +63
  • Vote: I do not like it

173.
By Noble_Mushtak, history, 4 years ago, In English
Solution to #810 Div. 1 Problem C: XOR Triangle I think the editorial for Round#810 is not out yet, and I found a solution for [810C: XOR Triangle](https://codeforces.me/contest/1710/problem/C) which I thought was interesting, even if my solution is probably more complicated the intended solution, so I wanted to write it up both because I want to share it with others and because I feel like explaining a solution can help myself remember it better. My implementation is [here](https://codeforces.me/contest/1710/submission/165613957). First, notice that, since every leg of the triangle $a\oplus b, a\oplus c, b\oplus c$ is the XOR of the other two legs in the triangle, and it is well-known that $x+y\geq x\oplus y$ for all positive integers $x, y$, the triangle is degenerate if and only if $x+y=x\oplus y$ for some legs $x, y$ of the triangle, i.e. $x+y < x\oplus y$ is not a possibility. I will be using this assumption implicitly throughout my solution. Let's say the binary string in the test case is $b_{N-1} \dots b_0$ (rightmost...
can replace the big sum in the expression above with $y_{i-1}$.

Full text and comments »

  • Vote: I like it
  • +93
  • Vote: I do not like it

174.
By ivan100sic, 5 years ago, In English
Binary search on integers using C++20 **Never write binary search again\*!** Often, solving a problem involves finding the smallest integer satisfying some predicate. The C++20 Ranges library allows us to run generic algorithms on ranges. Ranges can be backed by real data, such as ranges constructed from `std::vector`s, or they could be purely logical, such as `std::ranges::iota_view`. This class can construct views given two values. In case those values are integers, the constructed `range` supports random-access, meaning that random-access algorithms such as `std::ranges::lower_bound` can run efficiently i.e. in $O(\log n)$. For example, `std::ranges::iota_view(0, 5)` returns a view representing integers $[0, 1, 2, 3, 4]$. If you need to find the smallest integer value $v$ between $l$ and $r-1$ inclusive satisfying a predicate $p$ with the binary search property, or $r$ if it doesn't exist, you can do this in one line of C++ code: ``` auto v = *std::ranges::lower_bound(std::ranges::iota_view(l, r), true, {},...
boolean. Often this will be a lambda expression.

Full text and comments »

  • Vote: I like it
  • +179
  • Vote: I do not like it

175.
By Orn0, 2 years ago, In English
Codeforces Round 977 (Div. 2) — My Pupil's editorial Hello fellow Codeforcers ! I participated in [contest:2021] last Saturday and I had a great time. I was composed and was able to solve A, B and C1 in just under an hour. I thought I was close to solve C2 as well, but it took me some more time after the contest. Here is my thoughts and solution about the first 5 problems of the contest. Welcome to my humble green editorial ! ## [problem:2021A] My first thought was that choosing two elements of different parity would result in "loosing" a unit because of the floor operation. I then tried with toy inputs like $8,5,2$. - $\lfloor \frac{\textbf{8}+\textbf{5}}{2} \rfloor = 6$, $\lfloor \frac{6+\textbf{2}}{2} \rfloor=4$ - $\lfloor \frac{\textbf{8}+\textbf{2}}{2} \rfloor = 6$, $\lfloor \frac{5+\textbf{5}}{2} \rfloor=5$ - $\lfloor \frac{\textbf{2}+\textbf{5}}{2} \rfloor = 3$, $\lfloor \frac{3+\textbf{8}}{2} \rfloor=5$ I could conjecture two propositions. First, an order of summation could yield an optimal solution even if it...
The expression of $dpR$ can be written as $$dpR[i][r] = prefS[r] + \max_{0 < \textbf{p} < r, The left most expression can be illustrated with this picture. It is the max over columns $l$ of, The right most expression is the max of all rows $p$ of the max over all columns $l$ such that $l

Full text and comments »

  • Vote: I like it
  • +48
  • Vote: I do not like it

176.
By atigdng, history, 10 months ago, In English
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 ...

Full text and comments »

  • Vote: I like it
  • +23
  • Vote: I do not like it

177.
By eatmore, history, 7 years ago, In English
Java 14 for competitive programming Java 14 was released a few days ago. Here are some changes that may be useful for competitive programming. * Switch expressions, first introduced in Java 12, are now standard: ``` var whatToDo = switch (outcome) { "CE" -> "Check if you chose the right language"; "RE", "WA" -> "Check your logic"; "TL", "ML" -> "Check your complexity"; "AC" -> "Celebrate"; default -> "???"; }; ``` * Pattern matching for `instanceof`: ``` public boolean equals(Object o) { return (o instanceof Point p) && x == p.x && y == p.y; } ``` * Helpful `NullPointerException`s: now they include a message indicating which particular value was `null`. * Records: ``` record Fraction(int num, int den) { Fraction { if (den == 0) { throw new IllegalArgumentException("zero denominator"); } if (den < 0) { num = -num; den = -den; } } Fraction add(Fraction o) { return new Fraction(num * o.den + den * o.num, den * o.den); } // ... } ``` * `Print...

Full text and comments »

  • Vote: I like it
  • +77
  • Vote: I do not like it

178.
By UTPC_Admin, history, 3 years ago, In English
UTPC Spring 2024 Open Contest Editorial Hope you enjoyed our contest! The editorial is below: [A &mdash; Skipping Songs](https://codeforces.me/gym/105109/problem/A) Author: [user:sg2themax,2024-04-21] <spoiler summary="Solution"> For this problem, you maintain an index counter pointing to the current song, starting at 0. At each step, you always ensure that you mod by the length of the record. You start off by playing the song at the index of the first number. After printing each song, you increment by one since Noah has "finished listening" to it. Then, you add the number of skips, print the next song, and repeat. </spoiler> [B &mdash; 6th heaven](https://codeforces.me/gym/105109/problem/B) Author: [user:blueberryJam,2024-04-21] <spoiler summary="Solution"> We first check whether the conditions can be satisfied, then if so compute the number of arrangements. #### Pruning Consider a situation in which a disk appears three times or more among all the distinct pairs. This is impossible to arrange...
$a_i > 0$ and $b_i = 0$, the expression evaluates to $a_i$ since $a'_i = 0$ and $b'_i = 1

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

179.
By pilliamw, 13 months ago, In English
PHSCO Fall 2025 Editorial Thanks to everyone who participated in the Fall 2025 PHSCO! Over 40 teams participated across both divisions, which is a new record and extremely inspiring for our second-ever hosted contest. Things went a lot more smoothly this year and we hope that all (or at least a majority) of the problems were enjoyable. On a personal note, being able to run PHSCO is an amazing opportunity and I can't thank all of you enough for making it possible. Anyways, without further ado, congratulations to all of the winners in each prize pool! Please check your emails for prizes, which should be sent out within this week. (If you don't receive anything after a week, please contact me!) **Standard Division (Pre-College):** - 1st &mdash; Entropy &mdash; [user:TheInfiniteLoop,2025-10-26] &mdash; Narayana Educational Institution - 2nd &mdash; 1 orz 1 norz &mdash; Eason Li, Ethan Chang ([user:easonli416,2025-10-26], [user:spoonspoon1006,2025-10-26]) &mdash; Ellen Fletcher Middle School, Davidson Acad...

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

180.
By Spheniscine, history, 7 years ago, In English
Tutorial for Advent of Code 2019 day 22 part 2 [Advent of Code](https://adventofcode.com/) is a website that releases programming puzzles every December from the 1st to the 25th. The puzzles have two parts, and the second part isn't revealed until you solve the first part. This year, there have been many questions regarding part 2 of [day 22](https://adventofcode.com/2019/day/22), as it involves modular arithmetic in a way that hasn't been seen in previous puzzles there. I have been asked for a tutorial for it on Reddit, but I'm posting it here due to better support for mathematical notation. <spoiler summary="Part 2 summary"> You are basically asked to do the same thing as in part 1, but with $119315717514047$ cards, and repeating the steps in your input $101741582076661$ times. Also you're asked for the card in *position* $2020$. </spoiler> First off, if you are unfamiliar with modular arithmetic, I encourage you to read my other blog post, [Modular Arithmetic for Beginners](https://codeforces.me/blog/entry/72527). Th...
#Geometric_series). According to that Wikipedia page, we can thus transform the expression to

Full text and comments »

  • Vote: I like it
  • +40
  • Vote: I do not like it

181.
By dendi239, history, 6 years ago, In English
Micro- and macro-management for your next cpp source: General tips'n'tricks Hello, Codeforces! In this series of articles, I would like to tell you about tips'n'tricks I use in C++ sources. Some of them require a strong C++ background, some not, but all of them are aimed to reduce the time you spend on basic things like reading input/debugging/etc, so it might be useful for your next template. This part is dedicated to some basic tips (and probably should've been the first part but it's not ¯\\_(ツ)_/¯). <spoiler summary="TL;DR"> Full code: ~~~~ #include <bits/stdc++.h> using namespace std; using i64 = int64_t; using f80 = long double; using Str = string; template <class T> using Vec = vector<T>; template <class K, class V> using UM = unordered_map<K, V>; template <class T> auto &operator>>(istream &is, vector<T> &xs) { for (auto &x : xs) is >> x; return is; } namespace io { template <class ...As> auto &read(As &...as) { return (cin >> ... >> as); } template <class ...As> auto &log(const As &...as) { return ((cerr << " " << as...
Okay, it must be a result of expression with necessary debug output. Let's use a simple lambda on

Full text and comments »

  • Vote: I like it
  • +137
  • Vote: I do not like it

182.
By Nickolas, 15 years ago, translation, In English
VK Cup 2012 Wild-card Round 1: editorial So here goes the editorial. Note that Factor allows pretty random codes, feel free to put all words in one line, but all words must be separated by at least one space, don't try to skip a space between a bracket and a word or something like that. #### [problem:162A] This problem was almost the same as [problem:130A] from Befunge round. Data input and output is done exactly as in the sample code, and besides them the program needs only basic stack operations. ~~~~~ USING: io kernel math math.parser ; readln string>number dup 3 * 1 - * 2 / number>string print ~~~~~ Factor has a very system of built-in libraries which liberate the programmer from solving a lot of basic routine tasks. So after the first (trivial) probllem I gave several one-liners [cut] which needed only to find a proper library for the task. #### [problem:162B] This problem can be solved in several ways; the shortest one is to use >bin word from math.parser dictionary which does exactly what ...
-digits using a regular expression and concatenate them. My solution used replace word:, Now this is a match for regular expression. Word matches? checks whether the given string matches

Full text and comments »

  • Vote: I like it
  • +42
  • Vote: I do not like it

183.
By yashbihany, 20 months ago, In English
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)$ </...
Hence the final expression can be calculated by summing over all values of $t$ and $k$: $$\sum_{t

Full text and comments »

  • Vote: I like it
  • +42
  • Vote: I do not like it

184.
By codeonwort, 10 years ago, In English
Haskell Implementations for Round 379 (Div. 2) This post doesn't include a special or creative solution. It's about how to implement the solutions in the [editorial](http://codeforces.me/blog/entry/48397). This kind of post is unnecessary for C++ or Java, but it's Haskell and there's no one who completed the round with Haskell ;) I can't assure if my codes are in pure functional way or very efficient, but at least they were accepted. I hope it will be helpful. #### [problem:734A] Take the outcome as a `String` and count the number of 'A' and 'D' in it. It's very simple problem so I just traversed the string twice (two calls of `length . filter`.) If you want to do it 2x faster, you can use `partition` in `Data.List`. code: [submission:22282938] #### [problem:734B] Another simple problem. Here is the line that reads the input: ~~~~~ [k2, k3, k5, k6] <- (map read . words) `fmap` getLine :: IO [Integer] ~~~~~ If input is small like this, it has no problem. When you have to read a large number of integers, there...
expressions. `dfs` constructs a very long expression containing up to 200000 calls of `foldr` and then

Full text and comments »

  • Vote: I like it
  • +85
  • Vote: I do not like it

185.
By balakrishnan, history, 14 months ago, In English
Solving a 4000 rated Number Theory Problem Without Terence Tao–Level Math This is about [the problem](https://codeforces.me/contest/2147/problem/G) that drew controversy in a recent Div. 1 round because it had more accepted solutions than Problem F. That was surprising since G was rated 4000+, while F was intended to be much easier. This solution path is not a polished textbook derivation. Instead, it is a poor man’s, non-mathematician programmer’s way: brute force small cases, notice patterns in the resulting fractions, and then reverse-engineer a clean formula. ### Problem in simple terms You are given an integer m. For each number x, define a sequence like this: - Start with b(0) = 1 - Then repeatedly compute b(i+1) = x ^ b(i) % m We call x "good" if this sequence eventually becomes 1 and then stays 1 forever. The question: what fraction of all positive integers x are good? (That fraction is called the density of good x.) #### Step 1: Start by brute forcing small primes Begin with a small prime modulus p. For each x = 1, 2, … up ...
Since multiplying by m cancels out the exponents, the whole expression depends only on the prime

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

186.
By chromate00, 4 years ago, In English
STL in CP — Understanding Named Requirements (part 1) **Named Requirements** are a summary of what the STL expects for certain classes/types to be passed to functions as an argument. Understanding these are important for writing code that works well with other functions in the STL. There are many places you can read them on, but I personally prefer [Cppreference](https://en.cppreference.com/w/cpp/named_req). Let's take the following statement as an example. > Compare functions should return `false` when the two values are equal This is explicitly stated on the named requirement named [**Compare**](https://en.cppreference.com/w/cpp/named_req/Compare), the parts that state this are as follows: > Given `comp`, an object of type `T`, For all `a`, `comp(a,a)==false` From this we can see that objects of type `T`, when called as `f(a,a)`, should return `false`. Obviously the two `a`s are equal, and we can expect that the STL functions may (or in this case, *will*) spit unexpected errors if the requirement given in the statement is no...

Full text and comments »

  • Vote: I like it
  • +31
  • Vote: I do not like it

187.
By Peregrine_Falcon, history, 7 years ago, In English
Problems involving Bracket Sequences. Please suggest some. I've a fear of bracket sequence. Whenever I face one, It scares me. So, I'm gonna solve as many as possible. I was trying to make a list of problems which contains dealing with "Bracket Sequences". Here are some. Please suggest some if you've solved any. It'll be so kind if you comment the topic with the problem. Thank You in advance. Happy Coding O_o. [Reading Material CP-Algorithm ](https://cp-algorithms.com/combinatorics/bracket_sequences.html) [Online Judge &mdash; Parentheses Balance ](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=614) ( Stack ) [Codechef &mdash; Convert the Expression ](https://www.codechef.com/problems/CDM01)( Infix / Postfix / Prefix conversion ) [Online Judge &mdash; Equation ](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=668) ( Infix / Postfix / Prefix conversion ) [Codeforces &mdash; Sereja and Brackets](https://codeforces....
[Codechef — Convert the Expression ](https://www.codechef.com/problems/CDM01)( Infix

Full text and comments »

188.
By adamant, history, 10 years ago, translation, In English
Quaternion algebra and geometry Hi everyone! As you may already know (if you don't then I advice you to [learn](http://codeforces.me/blog/entry/22175) it), in 2D geometry it is convenient to use complex numbers to handling points operations and rotations. Now I would like to tell you about similar construction, which allows you to work efficiently with 3D geometry, in particular to use vectors and linear operations on them, calculate many popular operations (like dot or cross products) and maintain rotations in 3D space. [cut] <br> Let $\vec r_1 = (x_1, y_1, z_1), \vec r_2 = (x_2, y_2, z_2)$ &mdash; are vectors in 3D space. Following notation from analytical geometry will be used: 1. Dot product: $(\vec r_1, \vec r_2) = x_1 x_2 + y_1 y_2 + z_1 z_2 = |\vec r_1| \cdot |\vec r_2| \cos \varphi$, where $\relax \varphi$ &mdash; is the angle between $\vec r_1$ and $\vec r_2$ in their common plane, $|\vec r_1|$ &mdash; length of vector $\vec r_1$. 2. Cross product: $[\vec r_1, \vec r_2] = \begin{vmatrix} \vec ...
each $\vec a$ expression $g \vec a g^{-1}$ specifies vector $\vec a$ rotated around $\vec i$ on $\relax

Full text and comments »

  • Vote: I like it
  • +128
  • Vote: I do not like it

189.
By Nickolas, 9 years ago, translation, In English
April Fools Day Contest 2018: editorial #### [problem:952A] JAPE riddle generator is a program which can produce question-answer puns. This problem has been inspired by one of the witticisms produced by it: What do you call a quirky quantifier? An odd number. All you had to do was to check whether the given "quantifier" was "quirky". #### [problem:952B] This problem was inspired by the awesome book "Surely You're Joking, Mr. Feynman!" In one of his stories Feynman asks a librarian to fetch him a map of a cat, having a zoological chart in mind. Of course, such a serious interpretation was unsuitable for my purposes :-) This was a perfectly straightforward problem: just pet the cat! [cut] If the reaction you get is "no", try a different spot, otherwise you can figure out what kind of a cat this is right away. Just make sure you're not carried away: both kinds of cats get bored after 7th attempt to pet them and send you away without letting you guess their kind. One thing I didn't take into account was ...
The checker successfully iterated through the characters of the expression and accumulated them

Full text and comments »

  • Vote: I like it
  • +77
  • Vote: I do not like it

190.
By Kogut_Ivan, 19 months ago, translation, In English
Codeforces Round 1016 (Div. 3) Editorial We hope you enjoyed the contest! Thank you for participating! This is our first official round on Codeforces, so we would be happy to hear your feedback in the comments and in the mini-survey below. <spoiler summary="How did you like the contest?"> - Excellent: - Good: - Average: - Bad: - Terrible: </spoiler> <spoiler summary="Which problems did you like (you can choose multiple)?"> - A: - B: - C: - D: - E: - F: - G: </spoiler> <spoiler summary="Which problems did you not like (you can choose multiple)?"> - A: - B: - C: - D: - E: - F: - G: </spoiler> [problem:2093A] Идея: [user:EzikBro,2025-04-04] <spoiler su...
about the indices $i$ and $j$ for which the maximum value of the expression $a_i \oplus a_j$ is, case does the expression $x \oplus y = z$ hold? And $x \oplus y > z$?

Full text and comments »

  • Vote: I like it
  • -22
  • Vote: I do not like it

191.
By Spheniscine, history, 6 years ago, In English
[AtCoder] Unofficial HHKB Programming Contest 2020 Editorial ### [A &ndash; Keyboard](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_a) <spoiler> Basically, just do what it says in the problem statement. The function to turn a character uppercase is `std::toupper(t)` in C++, `Character.toUpperCase(t)` in Java, `t.toUpperCase()` in Kotlin, or `t.upper()` in Python. </spoiler> ### [B &ndash; Futon](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_b) <spoiler> Iterate through every row and column. If the current square is `.`, look at the neighbor to the right, if it's also `.`, increment the answer. Likewise the neighbor downward. There is no need to look leftward or upward as those positions would already have been counted. </spoiler> ### [C &ndash; Neq Min](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_c) <spoiler> Initiate an array of booleans indexed over $[0, 1 + \max p]$. Maintain a pointer $j$ starting at index $0$. Iterate through $p$. In each iteration, mark the corresponding index as "true", then use ...
Note that the middle expression is a degree-$1$ polynomial. To analyze the behavior of $F(x)$ we

Full text and comments »

  • Vote: I like it
  • +49
  • Vote: I do not like it

192.
By Nickolas, 13 years ago, translation, In English
April Fools Day Contest 2014: editorial Unfortunately, the most anybody could solve was 7 problems out of 9 total. 1289 participants solved at least one problem &mdash; this is less than the last year's numbers, but not bad either. Anyways, the key point is the total quantity of fun the people had! #### [problem:409A] The Most Intellectually Challenging Game In The World turned out to be the famous rock-paper-scissors. One could deduce this from the examples &mdash; ok, the rock () didn't look itself, but paper [] and especially scissors 8< looked really lifelike! Team competition is organized like this: players are split into pairs, with one player of each team in each pair, and pairs play against each other (the first line of input has "moves" of first team's players, the second line &mdash; of second team's players). The team which scores more individual victories wins. By the way, the game is not so trivial as it looks - [cut] there are big tomes written about the strategies, game ethics and organizing club...
Golorp's name (have anyone noticed that "golorp" is "prolog" spelled backwards?) is anexpression

Full text and comments »

  • Vote: I like it
  • +137
  • Vote: I do not like it

193.
By Bring, history, 4 years ago, In English
Solution to ARC154F Dice Game -- Generating functions and polynomials [For a better experience please click here.](https://www.cnblogs.com/BrianPeng/p/17103976.html) Link to the question: [Luogu](https://www.luogu.com.cn/problem/AT_arc154_f), [AtCoder](https://atcoder.jp/contests/arc154/tasks/arc154_f) ## Preface The very first generating function and polynomial problem solved in my life! *This blog is a detailed explanation and extension of the [official editorial](https://atcoder.jp/contests/arc154/editorial/5602). I will try my best to explain the mathematical expressions and their deeper meanings so that you may understand if you are also new to generating functions and polynomials* --- ## Our Goal Let $X$ be our random variable, which is the number of rolls after which all $N$-sides have shown up once for the first time. Its probability mass function $p_i=\mathbb P(X=i)$ is just the probability that all $N$-sides have shown up at exactly $i$-th roll. Then, what we are looking for is $\mathbb E(X)=\sum_{i=0}^\infty ip_i=0p_...

Full text and comments »

  • Vote: I like it
  • +94
  • Vote: I do not like it

194.
By dalex, 15 years ago, translation, In English
Codeforces Beta Round 76 - Analysis <p>At first I tell about the contest at all.<br></p>My problems in the contest were A-div2,&nbsp; B-div2,&nbsp; C-div2/A-div1,&nbsp; E-div2/C-div1,&nbsp; D-div1. I wanted to make only div.2 round, but then we decided to give you seven problems at both divisions. <a class="rated-user user-admin" href="../../../profile/MikeMirzayanov" title="Штаб, MikeMirzayanov">MikeMirzayanov</a> prepared the problem about milk pouring and <a class="rated-user user-orange" href="../../../profile/anonymous" title="Майор anonymous">anonymous</a> gave E-div1 problem. Also <a class="rated-user user-admin" href="../../../profile/RAD" title="Штаб, RAD">RAD</a> gave some advices to complicate problems Azembler and Flags a bit.<br><p>And now let's start analysis.<br><br><br><b>Problem A (div.2) - Restoring Password</b><br><br>Password was very easy to restore. You should just iterate over groups of 10 characters in the first string and over all codes. Then, if some number's code is equal to the group - print t...
} = \left(E+A\right)\left(E+A^{2}\right)\left(E+A^{4}\right)\dots\left(E+A^{b}\right)$. And theexpression

Full text and comments »

  • Vote: I like it
  • +26
  • Vote: I do not like it

195.
By BedwarKing, history, 2 years ago, In English
A permutation with probability problem with fast calculation Recently, I have participated in school contest and I got this problem: The problem is to generalize a formula for the probability P in terms of weights $w$ and sums $S$ for a given $n$, where $S=\sum_{j=1}^{n} w_j$ The probability formula involves choosing a permutation of the set $[2, n]$, which means the number of terms grows rapidly with $n$. Let's try to understand the general pattern by analyzing the cases for $n=3$ and $n=4$ $\textbf Case \ n = 3$ Given: $S = w_1 + w_2 + w_3$ For $n=3$, the formula for $P$ is: $$\Large P = \frac{w_2 \cdot w_3}{S \cdot (S - w_2)} + \frac{w_2 \cdot w_3}{S \cdot (S - w_3)}$$ We can factor the expression: $$\Large P = \frac{w_2 \cdot w_3}{S} \left( \frac{1}{S - w_2} + \frac{1}{S - w_3} \right)$$ This represents the weighted sum of two terms where the denominators correspond to the differences between $S$ and individual terms $w_2$ and $w_3$ $\textbf Case \ n = 4$ Now, let's analyze the case for $n=4$, where the formu...
We can factor the expression:

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

196.
By anmol73, 4 years ago, In English
Editorial: PC Educational Round | Programming Club, IIT Madras PC Educational Round was conducted by [Programming Club, IIT Madras](http://cfi.iitm.ac.in/club/Programming%20Club). The problems were based on Logic, Data Structures and Algorithms with particular emphasis on Graphs and Dynamic Programming. Here is the editorial with explanation and solution for each problem. Link to contest : [PC Educational Round](https://codeforces.me/contestInvitation/62ce4cba7e9b992786174de5fe3fb6b59332d84f) If you are unable to view the problems, then click on above link first. <p></p> #### [A. Candice's Chocolates](https://codeforces.me/gym/423099/problem/A) Problem Author: [user:RSG_02,2023-01-23] <spoiler summary = "Solution"> According to the problem statement, each friend should get at least one chocolate. So, if $n<m$, the division is not possible and the answer is $-1$. If $n \geq m$, then, as per the problem statement, $n$ chocolates have to be divided into $m$ friends such that every friend gets the same number of chocol...
Compute the expression of the final result, and try to calculate it in

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

197.
By vishwas_16.0, history, 10 months ago, In English
Editorial - Codeguerra Editorial &mdash; Codeguerra ================== [contest:663321] ------------------ [Problem A : Hawkins Rift](https://codeforces.me/gym/663321/problem/A) <br> Author : [user:vishwas_16.0,2026-01-30] <spoiler summary="Hint 1"> Notice that the rift at index $n$ is always stable, because $a_n \le n$ for every possible value.</spoiler> <spoiler summary="Hint 2"> $n$ can be as large as $10^{18}$. Do we really need to compute factorial up to that value? Think about the modulus $69696$ </spoiler> <spoiler summary="Solution"> We want arrays where after choosing exactly one index $i$ and setting $a_i=i$, there is exactly one stable rift ($a_i \le i$). All other positions must be unstable $\Rightarrow a_j > j$. Since position n is always stable eleven has no choice but to chose it. There are total of n different values for last index $\rightarrow n$ ways. Number of choices for rest: <ul> <li>Index 1 $\rightarrow (n-1)$ choices</li> <li>Index 2 $\rightarrow (n-2)$ choi...

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

198.
By luosw, history, 6 years ago, In English
The Application of Lagrange Interpolation in Mathematics ## Introduction ### Summary How to determine the analytical formula? The original undetermined coefficient method not only has small scalability, but also has a large amount of calculation, and it performs poorly in computer science design operations. The Lagrangian interpolation method can solve this problem. This article first introduces the Lagrangian interpolation method, and explores the process of using the Lagrange interpolation method to solve the problem. It discusses the application of Lagrangian interpolation in the four aspects of basic function properties, factorization, proof of algebraic identities, and finding the relationship between the serial numbers and numerical values ​​of several ordered and regular numbers. ### Symbol Convention 1. $\prod$ means accumulative multiplication operation, generally its subscript will be used as the condition of accumulative multiplication; 1. $\sum\limits^n_{i=1}i$ means $1+2+3+\cdots+n$; 1. $f(k)$ represents the va...

Full text and comments »

  • Vote: I like it
  • +150
  • Vote: I do not like it

199.
By NPsolved.cpp, history, 8 months ago, In English
OPC March 2026 Editorial Thank you for participating in $\mathbf{OPC\ March\ 2026}$! This editorial outlines the key ideas and solution approaches for each problem. We hope it helps you gain deeper insights and further strengthen your problem-solving skills in competitive programming. We would greatly appreciate your feedback. Please share your thoughts through this [Google Form](https://docs.google.com/forms/d/e/1FAIpQLSf2jvScUIwpxy16neU-CKQj7wIFx9diAO7vFY7TJSERR_PFwQ/viewform) Contest Link: [Link](https://codeforces.me/group/hUywLYmr80/contest/678537) ### [A. Find Sum](https://codeforces.me/group/hUywLYmr80/contest/678537/problem/A) <spoiler summary="Hint 1"> To make a sum of differences as large as possible, you want to subtract the smallest available numbers and add the largest available numbers. </spoiler> <spoiler summary="Solution"> The cost function is $Cost = |a_n - a_1| + \sum_{i=2}^{n} |a_i - a_{i-1}|$. This is equivalent to the total distance traveled if you start...
Substituting this into Nobita’s incorrect expression: $$ (a + b) \equiv (a \oplus b) \pmod{M

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it

200.
By HosseinYousefi, history, 8 years ago, In English
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...

Full text and comments »

  • Vote: I like it
  • +251
  • Vote: I do not like it

201.
By JaySharma1048576, 5 years ago, In English
Codeforces Round #730 (Div. 2) Editorial #### [A: Exciting Bets](https://codeforces.me/contest/1543/problem/A) <spoiler summary="Hint 1"> $GCD(a,b)=GCD(a-b,b)$ if $a>b$ </spoiler> <spoiler summary="Hint 2"> $a-b$ does not change by applying any operation. However, $b$ can be changed arbitrarily. </spoiler> <spoiler summary="Tutorial"> If $a=b$, the fans can get an infinite amount of excitement, and we can achieve this by applying the first operation infinite times. Otherwise, the maximum excitement the fans can get is $g=\lvert a-b\rvert$ and the minimum number of moves required to achieve it is $min(a\bmod g,g-a\bmod g)$. <spoiler summary="Proof"> Without loss of generality, assume $a>b$ otherwise we can swap $a$ and $b$. We know that $GCD(a,b) = GCD(a-b,b)$. Notice that no matter how many times we apply any operation, the value of $a-b$ does not change. We can arbitrarily change the value of $b$ to a multiple of $a-b$ by applying the operations. In this way, we can achieve a $GCD$ equal to $a-b$. Now, ...
is found using the generalised expression of queries derived in the Method 2 solution. Take some

Full text and comments »

  • Vote: I like it
  • +181
  • Vote: I do not like it

202.
By ECEgod, history, 5 months ago, In English
Using method of Lagrange multipliers in an AtCoder problem Hi all, I recently attempted [Square Price](https://atcoder.jp/contests/abc389/tasks/abc389_e). In this problem we are given N items, and it costs $k^2P_i$ yen to buy k units of the i-th product. We need to maximize $\sum_{i = 1}^{n}k_i$ given the total cost cannot exceed M. While the standard approach to solve this is with binary search, my approach was to treat this as a constrained optimization problem. We need to maximize $f = \sum_{i = 1}^{n}k_i$ under the constraint $g = \sum_{i = 1}^{n}k_i^2P_i = M$. So for now, let us allow $k_i$ to range over all positive real numbers. Setting $\nabla f = \lambda\nabla g$, we have a system of equations: $\frac{\partial \sum_{j = 1}^{n}k_j}{\partial k_i} = \lambda \frac{\partial \sum_{j = 1}^{n}k_j^2P_j}{\partial k_i}$ for all $1 \leq i \leq n$ $\implies 1 = 2\lambda k_{i}P_i$ $\implies k_i = \frac{1}{2\lambda P_i}$ Along with: $\sum_{i = 1}^{n}k_i^2P_i = M$ Plugging in the expression for $k_i$ gives: $\frac{1}{4\lam...
Finally we get the expression for $k_i$ $k_i = \frac{1}{P_i \sqrt{\frac{\sum_{j = 1}^{n}\frac{1

Full text and comments »

  • Vote: I like it
  • +32
  • Vote: I do not like it

203.
By mouse_wireless, history, 9 years ago, In English
Regular Expression problem -- better solution? I've recently come across the following problem in a real life scenario: You are given a regular expression with two special characters: `*` matches any sequence of characters (including the empty sequence) and `?` matches any one character. For example, `a?b` matches `acb`, but it does not match `abc`, `accb` or `ab`. `a*?b` however does match `accb`. `abc*f?h` matches `abcdefgh`. You have to write a program that checks if a pattern and a string match. Obviously, we can write an `O(n^2)` algorithm which looks like this: ~~~~~ bool matches(const char *pat, const char *s) { if (*pat == 0) return (*s == 0); if ((*pat == '?' || *pat == *s) && (*s != 0)) return matches(pat + 1, s + 1); if (*pat == '*') return ((*s != 0) && matches(pat, s + 1)) || matches(pat + 1, s); return false; } ~~~~~ For the scenario I have encountered, `O(n^2)` is more than enough, however I've been wondering for a while if a linear time algorithm (or anyway something b...
Regular Expression problem -- better solution?, You are given a regular expression with two special characters: `*` matches any sequence of

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

204.
By Peregrine_Falcon, history, 9 years ago, In English
Convert Infix to Postfix and Prefix **Convert Infix to Postfix Notation** Initially we’ve a _string_ S which represent the expression in infix format. Now we need a character _stack_. *We’ll iterate through the _string_ S, from left to right. * Whenever we encounter an operand we’ll print it. * If we encounter an ‘(‘ we’ll push it to the _stack_. * If we encounter an ‘)’ we’ll take the following actions: 1. We’ll continue to pop top of the _stack_ until we find the ’(‘ 2. Before we pop top of the _stack_, we’ll print every character of top of the _stack_ except ‘)’. * If we encounter an operator, we’ll take the following actions: 1. We’ll continue to pop top of the _stack_ until we find that S[ i ] is greater than the top of the _Stack_ (by the rules of precedence) Ex: if we found an Multiplication operator on S [ i ] We’ll continue searching for addition or subtraction operator on top of the _stack_. We’ll stop searching until it’s empty or we’ve f...
* Just reverse the postfix expression we’ve., Initially we’ve a _string_ S which represent the expression in infix format.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

205.
By dyatkovskiy, history, 7 years ago, translation, In English
Slow man's solutions. 1238, E. Покупка клавиатуры — некоторые пояснения к legacy разбору Here are some additional notes for [1238E](https://codeforces.me/contest/1238/problem/E)'s [tutorial](https://codeforces.me/blog/entry/70450), which is kindly made by [user:PikMike,2019-10-12] и [user:Roms,2019-10-12]. I got stuck there for a while with final expression. _( I even wrote solution with traces, haha (see after cut) )_ First, let's think about base expression for total moves amount. And then in top-down way try to come to solution. Moving rightward, for each symbol $s$, with keyboard position $x$ we will accumulate all moves between that symbol and all symbols at left.[cut] Obviously this is how we finally count all the moves. So here is a base expression: $cnt = \sum_{x=1}^{n} \sum_{y=1}^{x-1} cnt_{xy} (x - y)$ Where $x$ и $y$ are symbol coordinates on keyboard. And $cnt_{xy}$ is amount of moves between those symbols, namely $s_x$ и $s_y$ . (well, names are a bit different, but it allows to use shorter expressions) So, how to come to that nice e...
Suddenly, everything begins to make sence! For each $x$ we got that very expression (nice

Full text and comments »

  • Vote: I like it
  • +15
  • Vote: I do not like it

206.
By Tareq_Ali, history, 3 weeks ago, In English
Organized C++ Ordered Set and Multiset Hello everyone! After a long break from competitive programming, I’m back with something I wanted to have ready in my template: an ordered set and multiset with a clean member-function interface. One of the main reasons I created this project was to support the competitive programming community at Latakia University (Previously Tishreen University). I wanted contestants to have a reusable ordered-set and multiset template they can keep in their own templates and adapt to their problems. The project is **Organized C++ Ordered Set**. You can write `ordered_set<int>` or `ordered_multiset<int>`, access sorted ranks with `s[i]`, and use normal-looking bounds and erasure functions. It uses GNU PBDS with a strict comparator, including when duplicates are present. [Code, examples, and complete API reference](https://github.com/Tareq-Ali-1998/Organized-CPP-Ordered-Set) [GitLab mirror](https://gitlab.com/tareqali591998/organized-cpp-ordered-set) ## Usage first ```c++ ordere...
| Expression | Result | |---|---:| | `s[0]` | `2` | | `s.order_of_key(7)` | `2

Full text and comments »

  • Vote: I like it
  • -2
  • Vote: I do not like it

207.
By k.shivaram252, history, 3 weeks ago, In English
An approach to 1129 D2 ### 1. Optimization of $f(n)$ Let the boundary sequence be defined as: $$f'(k) = \sum_{i=0}^k 2^i = 2^{k+1} - 1$$ For any given $n$, let $b$ be the maximum integer such that $l \le n \le r$, where $l = f'(b)$ and $r = f'(b+1)$. The state transition is given by: $$f(n) = \min(b + f(n - l + 1) + 1,\; b + 1 + r - n)$$ ### 2. Prefix Sums $f''(x, y)$ and Pivot $k'$ Define the prefix sum function: $$f''(x, y) = \sum_{i=x}^y f(i)$$ Let $S$ be the ordered set of boundary values such that $f(S_i) = i$: $$S = \{ 2^k - 1 \mid k \in \mathbb{Z}^+ \} = \{1, 3, 7, 15, 31, \dots\}$$ For an interval $(l, r)$ where $l = S_i$ and $r = S_{i+1}$, the size of the range is $l$. Within $(l, r)$, there exists a pivot $k'$ that splits the piecewise evaluation of $f(n)$: $$f(n) = \begin{cases} b + f(n - l + 1) + 1 & \text{if } n \le k' \\ b + 1 + r - n & \text{if } n > k' \end{cases}$$ ### 3. Block Sum Expansions Using $k'$, the sum over the open interval $(l, r)$...
### 6. Final Recursive Expression

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

208.
By natalia, 16 years ago, translation, In English
School Team Contest #1 (Winter Computer School 2010/11): Tutorial <div><div><b>Problem A</b></div><div><br></div><div>To get the maximal possible result you have just to sort summands in non-decreasing order by coefficients (counting coefficients with preceeding signs + and -). You should not pay attention to 'a++' or '++a'! The question is: why is it true?&nbsp;</div><div><br></div><div>First, consider an expression with only 'a++'. Then our assertion is obvious: it is better to multiply 'a' by small coefficients when it has small value, and by large coefficients, when it becomes larger. The same also takes place in case of negative coefficients or a-value. Of course, it is not a rigorous proof. I hope you will think on it if you haven't get it yet.</div><div><br></div><div>Second, consider the expression $k*a+++k*++a$, where $k$ is some coefficient equal for both summands. Let initial value of 'a' equals to $a_0$. Calculating the value of the expression both ways, we obtain: $k * a_0 + k * (a_0 + 2) = k * (a_0 + 1) + k * (a_0 + 1)$. So in this case...
Third, let us have the expression $k*a+++l*++a$, where $k$ and $l$ are two distinct

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

209.
By goryinyich, 15 years ago, In English
Editorial for Codeforces Beta Round #78 <p></p><div>Hi there!</div><div><br></div><div>Here is editorial for the round #78.</div><div>Russian editorial will be published a bit later - I supposed that there are more people who can understand English (or who can do English -&gt; Russian web page translation) than vice versa.</div><div><br></div><div>Again, I'm very sorry for the situation with problem B (div. 1) / D (div. 2). Also, I'm sorry that I underestimated difficulty of the problems. At least, I hope the problems appeared interesting for many contestants.</div><div><b><br></b></div><div><b>Problem A (div. 2) - Help Far Away Kingdom</b><br></div><div>Here the problem was to round a number up according to the usual mathematical rules with the exception that if the last digit of integer part is equal to 9, you should output "GOTO Vasilisa.". One may notice that to check whether number's fractional part is not less than 0.5 only one digit just after the decimal point should be analysed. If it is '5' or greater - add one to ...
And (****) is quite straightforward expression for U(): move all discs but the largest group

Full text and comments »

  • Vote: I like it
  • +47
  • Vote: I do not like it

210.
By grhkm, history, 5 years ago, In English
[TUTORIAL] Basic Lagrange Interpolation pt. 2 As promised, here's "interpolating multiple values" in $O(n\log^2 n)$. **Pre-req: Polynomial multiplication and modulos, basic lagrange interpolation knowledge (you can read my previous post [here](https://codeforces.me/blog/entry/82953))** As a reminder, polynomial mod is $O(n\log n)$. Main results: ================== Given $f(x)$ and $x_1, x_2, \cdots, x_n$, we can find $f(x_1), f(x_2), \cdots, f(x_n)$ in $O(n\log^2 n)$. Given a bunch of points $\{(x_0, y_0), (x_2, y_2), \cdots, (x_n, y_n)\}$, we can find a degree $n$ polynomial $f(x)$ such that $$\forall 0\leq i\leq n, f(x_i)=y_i$$ Why useful? ================== It helps you AC problems that you can't with $O(n^2)$. It also gives you contribution on CF --------------------------- Idea 1: ================== Since the pre-req says polynomial modulo, let's see if we can mod something to calculate some of $f(x_1), f(x_2), \cdots$ quickly. It can be seen that we can split the set of $x$ into two halves &...
Now going back to the original expression, $f(x)=\sum_{i=1}^{n+1} \frac{y_i}{M'(x_i)}\prod_{j\neq i

Full text and comments »

  • Vote: I like it
  • +85
  • Vote: I do not like it

211.
By Ecrade_, 20 months ago, In English
Codeforces Round 1012 (Div.1, Div. 2, based on THUPC 2025 — Finals) Editorial We apologize for the late editorial. [problem:2090A] <br> Idea: [user:_Lucien,2025-03-26] <spoiler summary="Solution"> Let's calculate how many operations we need. The number of pairs of operations is $\left\lfloor\frac{a}{x + y}\right\rfloor$. Additionally, we add $+1$ if $(a \bmod (x + y)) \ge x$, because in this case, the first player will be able to make one more move. Note that the first part is always even, which means the answer depends only on whether $(a \bmod (x + y)) \ge x$, and in this case, the answer is YES. </spoiler> <spoiler summary="Code"> ~~~~~ #include <bits/stdc++.h> using namespace std; void solve() { int x, y, a; cin >> x >> y >> a; if (a % (x + y) < x) { cout << "NO\n"; } else { cout << "YES\n"; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) solve(); } ~~~~~ </spoiler> [problem:2090B] <br> Idea: [user...
number of characters in front the former `1`, i.e., `(..)*1(00)*1(..)*0` in regularexpression, the

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it

212.
By Dhakshith1189, 3 months ago, In English
Axiom 2026 Finals Editorial Thank you for participating in AXIOM '26 Finals! We hope you enjoyed the problems. Problems were authored by [user:omkaar,2026-08-09], [user:wounded_man,2026-08-09], [user:slashing_tsunami,2026-08-09] and [user:dhakshith1189,2026-08-09] ####Reconstructing the Permutation <spoiler summary="Hint 1"> What happens if you fix the very first element $p_1$? </spoiler> <spoiler summary="Hint 2"> What happens if you look at the last $k$ bits such that $2^k$ divides $n$? </spoiler> <spoiler summary="Solution"> Fixing $p_1$ uniquely determines the sequence as $p_i = p_1 \oplus \text{pref}_i$. Let $k$ be the highest power of $2$ that divides $n$. The set $\{0, 1, \dots, n-1\}$ has a special property: XORing every element by any value $y < 2^k$ simply permutes the set. This means if there is one valid starting value $p_1$, there are exactly $2^k$ valid choices varying only in their lowest $k$ bits. For any bit position $b \ge k$, the number of elements with the $b$-th bit ...
written as a single expression modulo the corrections, using the binomial theorem.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

213.
By mhnd01s, history, 18 months ago, In English
Need help in a cool math problem (I think it's cool) So, I've encountered this [problem](https://codeforces.me/gym/105319/problem/G) and solved it using the hombo bombo technique. If you're not familiar with the topic, it's a technique I use to solve pretty much any math problem: 1. Brute force the answer. 2. Try to find any patterns. However, I felt this problem is different. Here's what I did: <spoiler summary="Steps"> 1. Brute force for all numbers less than 20. 2. I found out that the answer of even numbers is always 2. 3. Tried to isolate odd numbers and after some tweaking, they follow this sequence: [A086668](https://oeis.org/A086668). The answer of any odd number $n$ starting with $3$ is $2^{A086668(\lfloor \frac{n}{2} \rfloor) + 1}$. 4. I generated the sequence up to $10^6$ and hola. </spoiler> Usually, it ends here and I never look at the problem again. But for this particular problem, it was a little too much to say "yeah the pattern is obvious.". How counting modules for 2 seemingly different expre...
I did search for the exact expression but no luck. I'm interested in the solution and some kind of

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it

214.
By rachitiitr, 5 years ago, In English
C++ Trick — Easy Debugging / Logging Hi Community, It's been a while I wrote a blog post here. You can follow more such tricks on &mdash; - Github: [https://github.com/rachitiitr/modern-cpp-tricks](https://github.com/rachitiitr/modern-cpp-tricks) - Discord: [https://bit.ly/discord-rachit](https://bit.ly/discord-rachit) - YouTube: [https://bit.ly/rachityoutube](https://bit.ly/rachityoutube) ## How debug macros work? Straight to the point, I have often used the `debug` macro which stringifies the variable names and their values. ```cpp #define deb(x) cout << #x << " " << x int ten = 10; deb(ten); // prints "ten = 10" ``` This is often useful in debugging. ## The Problem with this macro &mdash; its not scalable However, when you have multiple variables to log, you end up with more `deb2` and `deb3` macros. ```cpp #define deb(x) cout << #x << " " << x #define deb2(x) cout << #x << " " << x << " " << #y << " " << y #define deb3(x, y, z) cout << #x << " " << x << " " << #y << ...

Full text and comments »

  • Vote: I like it
  • +139
  • Vote: I do not like it

215.
By _admin_, 9 months ago, In English
Fundamentals of Polynomials ## Prerequisite Knowledge ### Polynomials An expression of the form $P(x) = a_0 + a_1 x + \cdots + a_n x^n$ is called a polynomial. #### The coefficient representation of a polynomial We use the coefficient $a_0, a_1, \cdots, a_n$ to express the polynomial. This is the most common form of polynomials in practice. #### The point-value representation of a polynomial Select $n + 1$ distinct values $x_0, x_1, \cdots, x_n$ and substitute them into the polynomial and calculate the corresponding values $P(x_0), P(x_1), \cdots, P(x_n)$, the set of all pairs $$\{x_i, P(x_i)\}$$ is called the point-value representation of the polynomial. ### Complex Numbers The imaginary unit $i$ is defined as the square root of $-1$, i.e. $i = \sqrt{-1}$. A number of the form $a + bi (a, b \in \mathbb{R})$ is called a complex number. #### Addition of Complex Numbers $(a + bi) + (c + di) = (a + c) + (b + d)i$ #### Multiplication of Complex Numbers $(a + bi)(c + di) = ac ...
An expression of the form $P(x) = a_0 + a_1 x + \cdots + a_n x^n$ is called a polynomial.

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it

216.
By slycelote, 16 years ago, translation, In English
Codeforces Beta Round #23 tutorial <h3>A. <a href="../../../contest/23/problem/A">You're given a string...</a></h3><br />Iterate over all substrings, starting with the longest ones, and for each one count the number of appearances. The complexity is $O(L^4)$ with a small multiplicative constant.<br />[cut]<br /><h3>B. <a href="../../../contest/23/problem/B">Party</a></h3><br />It's clear that at least one person (the one with the least number of friends) will have to leave. We claim that at least two persons will leave. Indeed, suppose that only one person left, and he had $d$ friends. Then all other people had more than $d$ friends before he left, and after that they had less than $d+1$ friends, i.e. not more than $d$. So, his leaving influenced the number of friends for every other person, which means that he was friends with everyone: $d=N-1$. But he has fewer friends than everyone — a contradiction.<br /><br />So, the answer is not more than $N-2$. We'll prove that it's possible for $N-2$ people to stay (of course, ...
maximum of the expression $f_v · (f_w/h_w) · Π_{i \le s} (f_i/h_i) · (s+2)$ as $w$ iterates

Full text and comments »

  • Vote: I like it
  • +27
  • Vote: I do not like it