". This is just a small fraction of the flow class. About 90% of it is
completely identical, This is just a small fraction of the flow class. About 90% of it is completely
identical.
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | maspy | 150 |
| 3 | Um_nik | 145 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 8 | nik_exists | 132 |
| 9 | AmShZ | 130 |
| 10 | Dominater069 | 129 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
Fractions
Last visit:
7 years ago
Registered:
7 years ago
2.
Who sorry_dreamoon really is Hello everybody. So I was really bored tonight and looked at so many comments being like "[user:sorry_dreamoon,2015-02-18] is X" and then people arguing and disagreeing. Since I had nothing better to do, I decided to finally unravel the truth of who he actually is. Here is the full case and how I actually got to him, hope you enjoy! :D
Selection
------------------
Let's start by the obvious. He managed to get first place in Div2 and he got second in Div1 (would've been first if the scores were static). So what we know is that he is really good.
Let's look at the past 10 Div1 contests. It turns out that only 8 times it happened that someone with a rating of less than 2500 got in top5. This is 8 times out of 50 people being in top5. But he was second and almost first, so he is better than that.
It turns out actually, that in the past 10 Div1 contests, only 2 times it happened that someone with rating less than 2500 got in top3.
Combining this information with [user:sorr...
3.
[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...
applications that I can only cover a small fraction of them here. If you are
interested in more examples of, fraction of them here. If you are interested in more examples of counting using
generating functions
4.
I've completed Project Euler It was a beautiful journey full of internet digging, searching for patterns, learning stuff, fighting with formulas on paper, making crazy observations, coming up with brilliant ideas, implementing crazy optimizations, waiting for the programs to finish, suffering when something was wrong, and so on (and each of the mentioned not once not twice took multiple hours).
It's been a couple of months since I was left with the last unsolved problem and finally I did it! I didn't give up and I obtained the answer alone, without anyone's help, like in the rest of the problems (I was using only internet sources created before the publication of the problem). I'm writing this blog because I am bursting with joy and I wanted to share it with the community. I highly recommend PE as most of the problems were definitely very high quality (and some were a real pain in the ass, but they still teach how to overcome stuff that you're uncomfortable with).
Here's a little souvenir for me:
![ ](/pr...
5.
I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021] <h3 style="color:red">If there are any blogs that I have missed, please tell in the comment section. Thank you.</h3>
# Mathematics Stuff
- [Number Theory in Competitive Programming [Tutorial]](https://codeforces.me/blog/entry/46620)
- [Number of points on Convex hull with lattice points](https://codeforces.me/blog/entry/62183)
- [FFT, big modulos, precision errors.](https://codeforces.me/blog/entry/48465)
- [Number of ways between two vertices](https://codeforces.me/blog/entry/19078)
- [Mathematics For Competitive Programming](https://codeforces.me/blog/entry/76938)
- [FFT and NTT](https://codeforces.me/blog/entry/19862)
- [Burnside Lemma](https://codeforces.me/blog/entry/51272)
- [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.me/blog/entry/76836)
- [On burnside (again)](https://codeforces.me/blog/entry/64860)
- [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.me/blog/entry/55912)
- [Probabili...
6.
[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, ...
similar to our second fraction)., For example, let's look at the second fraction. We want to find
$[z^{n}]\frac{-e^{z}}{(1 - e^{z}(1, It remains to compute $[z^{n}]$ of each fraction fast. Our main goal is to
isolate the variable $y, Letting $g(z) = \frac{1}{(1-z)(1 - e^{z}(1-z))}$, the first fraction reduces to
$[z^{n}]\frac{g(z, Similarly, the first fraction can be rewritten as
7.
Snapshot of finite calculus and using it to solve a 3000 rated problem Hey all,
First, I'll give a brief overview of what finite calculus is about and I'll then show you how I used it to solve [problem:1951G]. This may be not the most elegant way to solve that problem, but it requires few observations and I find it interesting enough to share it. I am also taking part in the [Month of Blog Posts challenge](https://codeforces.me/blog/entry/133806).
You can find better introductions googling terms "finite calculus", "discrete calculus", etc, although I still have not found an in-depth, thorough, introduction for these ideas, only some short expositions scattered around the web. But these ideas are pervasive throughout competitive programming (think of adjacent differences, prefix sums, slopes and the like).
_Disclaimer_: this blog requires some mathematics background to fully understand it.
### A short intro to finite calculus
If you know calculus, you have seen derivatives, integrals and the fundamental theorem of calculus. For a function $...
(int, input().split())) A = sorted(A) n = Fraction(N, 1) m = Fraction(M, 1) def
R(K, ~~~~~ from fractions import Fraction
8.
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 ...
Lagrange interpolation and partial fraction decomposition, highlight how it is useful when one needs an explicit meaningful solution for
partialfraction, it is useful when one needs an explicit meaningful solution for partial
fraction decomposition., #### Partial fraction decomposition, Noteworthy, $O(n \log^2 n)$ algorithm to compute partial fraction decomposition
was [proposed, Then, the whole partial fraction decomposition can be computed in $O(n \log^2
n)$ with divide and, where $Q_i(x) = \frac{Q(x)}{(x-x_i)^{d_i}}$. Let's get back to partial fraction
decomposition. If
9.
On continued fractions. Part 3: In competitive programming Hi everyone!
It's been quite some time since I wrote two previous articles in the cycle:
[Part 1: Introduction](https://codeforces.me/blog/entry/73655)<br>
[Part 2: Properties and interpretation](https://codeforces.me/blog/entry/73687)<br>
**Part 3: In competitive programming**
This time I finally decided to publish something on how one can actually use continued fractions in competitive programming problems.
Few months ago, I joined [CP-Algorithms](https://cp-algorithms.com/algebra/continued-fractions.html) as a collaborator. The website also underwent a major design update recently, so I decided it would be great to use this opportunity and publish my new article there, so here it is:
<center><big><b><a href = "https://cp-algorithms.com/algebra/continued-fractions.html">CP-Algorithms — Continued fractions</a></b></big></center>
It took me quite a while to write and I made sure to not only describe common competitive programming challenges related to contin...
) * [Tavrida NU Akai Contest — Continued Fraction
](https://timus.online/problem.aspx?space=1, , a_n]$ and $B=[b_0; b_1, \dots, b_m]$, compute the continued fraction
representations of $A+B$ and, ]$, compute the continued fraction representations of $A+B$ and $A \cdot B$. -
Given $\frac{0}{1} \leq \frac, ](http://poj.org/problem?id=3530) * [2019 Multi-University Training Contest 5 —
fraction](http
10.
On continued fractions. Part 2: Properties and interpretation Hi everyone!
Let's [continue](https://codeforces.me/blog/entry/73655) with learning continued fractions. We began with studying the case of finite continued fractions and now it's time to work a bit with an infinite case. It turns out that while rational numbers have unique representation as a finite continued fraction, any irrational number has unique representation as an infinite continued fraction.
[Part 1: Introduction](https://codeforces.me/blog/entry/73655)<br>
**Part 2: Properties and interpretation**
<br>
[cut]
<br>
**Distance between convergents.** In the first part we learned that for continued fraction $r=[a_0, a_1, \dots, a_n]$ elements of the sequence $r_0, r_1, \dots, r_n$ where $r_k = [a_0, a_1, \dots, a_k]$ are called convergents. We also derived that subsequent convergents obey a simple formula:
<br><br>
$$
\frac{p_{-2}}{q_{-2}} = \frac{0}{1},\quad\frac{p_{-1}}{q_{-1}} = \frac{1}{0},\quad\frac{p_k}{q_k}=\frac{a_k p_{k-1}+p_{k-2}}{a_kq_{k-1}+q_{k-2}}
$$...
"pretty" continued fraction representations:, finite continued fraction, any irrational number has unique representation as
an infinite continued, for continued fraction $r=[a_0, a_1, \dots, a_n]$ elements of the sequence
$r_0, r_1, \dots, r_n, such infinite fraction if it's the limit of its convergents:, It is also worth noting that continued fraction is periodic if and only if $r$
is quadratic, fraction, any irrational number has unique representation as an infinite
continuedfraction., }} $$ Let's rewrite the numerator of this fraction:
11.
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...
reduce the computation of its nested fraction coefficients to the case $(q, p
\bmod q)$, which is, , any _rational_ number $r=\frac{p}{q}$ may be _uniquely_ represented as a
_finite_ nestedfraction of, }$ may be _uniquely_ represented as a _finite_ nested fraction of the following
kind:
12.
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 — 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 — trie might do too
http://www.spoj.com/problems/NSUBST...
13.
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 — 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...
line, but the desire is not to write the fraction of the blue, too, is
understandable. In this case, mathematics division is not written in one line, but the desire is not to
write thefraction of the, If you want to write all the same fraction, it has two similar commands:
`\frac` and` \dfrac
14.
About Problem Coincidences Hi.
Of course, there was an unpleasant incident with the problem today. In fact, the problem almost coincided with another problem in the old round, which was hosted 5 years ago.
You, of course, are shocked. You, of course, think that the round should be unrated.
You are wrong. Here's why.
[cut]
We need to clearly distinguish between two scenarios with coincided problems in our rounds.
First. The writer has knowingly plagiarized. This is an outrageous scenario. Such behavior knows no excuse and it is a conscious detriment to our community. Shame on the writer!
Second. The problem was matched unintentionally. The writer was unaware of some old problem. This happens. The coordinator had not seen this old problem before or had forgotten it. We are all human. The round was tested, but the testers did not indicate such a coincidence. Too bad, it happens. Who can we blame for this situation? The writer? Most likely, the writer did a lot of work to prepare the ro...
not a bad skill. Let a small fraction of participants be rewarded for this if
such a mishap as a, put them into practice, that's not a bad skill. Let a small fraction of
participants be rewarded
15.
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...
#### Partial fraction decomposition
16.
Tips for writers: What requires a proof? If you are a contestant, you can be relaxed and you can do anything (except for cheating). It's perfectly fine if you just guess the solution and submit it without knowing why (though personally I don't find it very beautiful). However, if you are a writer, you need to prove your solution. Here is the list of things you have to prove:
#### 1. Correctness.
Does your solution always return correct answers for all possible valid inputs?
- GOOD: Strict proof.
- BAD: _My intuition tells that this is correct!_
- BAD: _I tried really hard to come up with counterexamples, but I couldn't. It must be correct!_
#### 2. Time Complexity.
Does your solution always run in time for all possible valid inputs?
- GOOD: It's $O(n^2)$ and the constraints say $n \leq 1000$. It should work.
- GOOD: For this problem we can prove that the slowest case is xxx. Experimentally, my solution works for the input xxx under the given TL.
- BAD: _I tried really hard to generate various testcases, and ...
17.
Yandex.Algorithm 2017, third elimination round: editorial (with challenges, bells and whistles) This time I've decided to play with spoilers to faciliate the presentation as some of the guys here did before. Tell me what you think about this write-up!
#### Problem A. Shifts
Topics: dynamic programming.
Summary: the first "hard" problem of the contest. Knowing your basic DP problems helps a lot, but coming up with the precisely correct solution may take a lot of persistence.
Solution: Suppose that we are allowed to make left circular shifts as well as right ones.
<spoiler summary="Can you solve the problem in this case?">
First of all, making a shift is effectively moving a character to a different position in the string. Clearly, moving a character more than once makes no sense since we could have just moved it to its final destination instead without wasting any operations. Also, it obvious that the number of occurences of each character should be the same in both strings since it is preserved by shifts.
Now, consider the characters that are *not* moved by ...
18.
Pythagorean triples and Pell's equations Hi everyone!
Recently I started solving projecteuler, and while doing so I encountered two concepts about which I heard before, but I didn't really bother to learn them. I made a few notes to myself about how they work, and thought it could be useful for somebody else too. This blog focuses on Pythagorean triples and Pell's equations, which are recurrent concepts on projecteuler.
Great thanks to [user:nor,2023-05-07], [user:Endagorion,2023-05-07], [user:Golovanov399,2023-05-07] and [user:Neodym,2023-05-07] for useful discussions about these topics.
[cut]<hr>
#### Pythagorean triples
**Pythagorean triple** is a triple $a,b,c \in \mathbb Z$ such that
$$
a^2 + b^2 = c^2.
$$
It is possible to parameterize them in a way that allows to find all triples such that $a,b,c \leq n$ in $O(\sqrt n)$.
##### Rational points on a unit circle
To do that, let's divide the equation by $c^2$ to get
$$
\left(\frac{a}{c}\right)^2 + \left(\frac{b}{c}\right)^2=1.
$$
This re...
for integers such parameterization is incomplete, as the fraction
$x=\frac{a}{c}$ could as well, ##### Periodicity of the continued fraction, Consider the continued fraction $\sqrt D = [a_0; a_1, a_2, \dots]$ and its
complete quotients $s_k, Note that for integers such parameterization is incomplete, as the fraction
$x=\frac{a}{c}$ could, That is, $x + y \sqrt D \in \mathbb Q[\sqrt D]$ has a periodic fraction if and
only if it's larger, fraction of $\sqrt D$, and only ever happens at $k=-1$ or after we just
completed another period
19.
Unofficial Editorial for Educational Round 95 (Div. 2) Here are my approaches to the problems today:
#### [problem:1418A]
Since the second trade is the only way to get coal, we clearly need to perform the second trade $k$ times. So how many times do we need to do the first trade? We can see that in order to end up with enough sticks and coal by the end, we need to obtain $ky + k$ sticks ($ky$ to convert to coal and $k$ to save as sticks). Since the first trade really just gives us $x - 1$ new sticks each time, we'll need to make $\displaystyle \left \lceil \frac{ky + k - 1}{x - 1} \right \rceil$ first trades ([reference to floor and ceiling functions](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) for anyone unfamiliar).
For implementation details, note that for positive integers $a$ and $b$, $\displaystyle \left \lceil \frac{a}{b} \right \rceil = \left \lfloor \frac{a + b - 1}{b} \right \rfloor$. Code: [submission:92851684]
#### [problem:1418B]
We can think about the problem as follows: we want to order the $a_i$ to...
= x_2 y_2$. Then if we write $\displaystyle \frac{x_2}{x_1} = \frac{a}{b}$ as
a reducedfraction, we
20.
Half-GCD algorithm Hi everyone!
Today I'd like to finally talk about an algorithm to solve the following tasks in $O(n \log^2 n)$:
- Compute the greatest common divisor of two polynomials $P(x)$ and $Q(x)$;
- Given $f(x)$ and $h(x)$ find the multiplicative inverse of $f(x)$ modulo $h(x)$;
- Given $F_0,F_1, \dots, F_m$, recover the minimum linear recurrence $F_n = a_1 F_{n-1} + \dots + a_d F_{n-d}$;
- Given $P(x)$ and $Q(x)$, find $A(x)$ and $B(x)$ such that $P(x) A(x) + Q(x) B(x) = \gcd(P, Q)$;
- Given $P(x)=(x-\lambda_1)\dots(x-\lambda_n)$ and $Q(x)=(x-\mu_1)\dots(x-\mu_m)$ compute their [resultant](https://en.wikipedia.org/wiki/Resultant).
More specifically, this allows to solve in $O(n \log^2 n)$ the following problems:
<hr>
**[Library Checker — Find Linear Recurrence](https://judge.yosupo.jp/problem/find_linear_recurrence)**. You're given $F_0, \dots, F_{m}$. Find $a_1, \dots, a_d$ with minimum $d$ such that
$$
F_n = \sum\limits_{k=1}^d a_k F_{n-k}.
$$
<hr>
<hr>
**[Libr...
we can derive from the continued fraction expansion of
$\frac{A_1(x)}{B_1(x)}$. Let, From continued fraction properties it also follows that $p_{i-1} q_{i-2} -
q_{i-1} p_{i-2} = (-1, From the continued fraction properties it follows that, Now we have a fraction $\frac{r_k}{r_{k+1}}$ and we need to continue the
process till we get to, This sequence corresponds to the continued fraction, Thus if the degree of $x^t (-1) r_i'$ is greater than of $A_0 q_i' - B_0 p_i'$,
thefraction $p_i, fraction computation, from $\frac{r_{k-1}}{r_k}$ to
21.
How to read problem statements But [user:Um_nik,2018-10-26], we all know how to read, we have our whooping 2 month of experience! Oh, my sweet summer child, my experiments show that many people with kinda cool achievements like medals on ROI don't know how to read statements. But don't worry, I'll teach you. Well, probably you won't understand anything, because you didn't try to understand anything in your life, you expect all hard work to be done for you by someone else. Let's start!
Basic rules
==================
- The result of reading the statement is usually pure math model. If story helps to build correct understanding, you can keep it, but still try to discard as many unnecessary details as possible.
- Imagine you want to tell the problem to someone else. What parts you want to tell? (According to my PM, this rule won't help you).
- Shorter = better.
- Simpler = better.
- Limitations are part of problem statement. Especially small limitations, because for small data you can try all the possib...
22.
[Contest] Statement Not Found: Season 2 #### Do you think you can solve CP problems without reading the problem statements? Let's find out!
On [August 28, 2022 (Sunday) 19:30-22:00 GMT+8](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Statement+Not+Found+-+Season+2&iso=20220828T1930&p1=122&ah=2&am=30), I will hold an unofficial fun contest called Statement Not Found. As you can deduce from the title, there will be no problem statements (except title and samples). Your goal is to collect as many points as possible within 2.5 hours :)
Obviously, this round is **unrated**. It is somewhere between April Fools contest and a legitimate contest.
The contest will be OI-style, meaning there will be no time penalty. You are allowed to use any resources online to help solve the problems. There will be **12** problems.
**Scoring Distribution:** 200-400-700-700-700-800-800-900-1100-1100-1100-1500 (Total: 10000)
**Please read all problems** as problem difficulty is very subjective and a 1100-point problem might b...
23.
Recovering a linear recurrence with the extended Euclidean algorithm Hi everyone!
The task of finding the minimum linear recurrence for the given starting sequence is typically solved with the Berlekamp-Massey algorithm. In this article I would like to highlight another possible approach, with the use of the extended Euclidean algorithm.
Great thanks to [user:nor,2022-04-08] for the proofreading and all the useful comments to make the article more accessible and rigorous.
### Tl'dr.
The procedure below is essentially a formalization of the extended Euclidean algorithm done on <!--$a$-->$F(x)$ and $x^{m+1}$.
If you need to find the minimum linear recurrence for a given sequence $F_0, F_1, \dots, F_m$, do the following:
Let $F(x) = F_m + F_{m-1} x + \dots + F_0 x^m$ be the generating function of the reversed $F$.
Compute the sequence of remainders $r_{-2}, r_{-1}, r_0, \dots, r_k$ such that $r_{-2} = F(x)$, $r_{-1}=x^{m+1}$ and $$r_{k} = r_{k-2} \mod r_{k-1}.$$
Let $a_k(x)$ be a polynomial such that $r_k = r_{k-2} - a_k r_{k-1}$.
...
24.
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...
addition is a fraction of general form $\frac{a + b_1 + \ldots + b_k}{a + b_1
+ \ldots + b_{k - 1}}$. As, multiplied by is the fraction $\frac{a + b_1 + \ldots + b_{i - 1} + b_i}{a +
b_1 + \ldots + b_{i - 1}}$. Now, ratio by which the value (and the whole product of values) is going to be
multiplied by is thefraction
Tutorial of Codeforces Round 295 (Div. 2)
Tutorial of Codeforces Round 295 (Div. 1)
25.
[Tutorial] Minimum cost (maximum) flow [Part 1: [Tutorial] My way of understanding Dinitz's ("Dinic's") algorithm](https://codeforces.me/blog/entry/104960)
**Part 2: [Tutorial] Minimum cost (maximum) flow**
[Part 3: [Tutorial] More about minimum cost flows: potentials and Dinitz](https://codeforces.me/blog/entry/105658)
#### Introduction
There is a section in our ICPC notebook from 2019 called "min cost dinic".
This blog started as an attempt to dissect what was written in there and
understand why it works. In time, I needed to refer to many general ideas about
flow, so it developed into a more general treatment of (min-cost) flow problems
and spawned an entire separate blog about maximum flow and Dinitz. Even after
splitting the blog, this blog was still too long, so I split it yet again.
This blog will deal with the basic ideas of minimum cost flow; there will be a
part 3, where I will generalize to a Dinitz-like algorithm and also talk a bit
about something called potentials.
This blog is somewha...
would exceed the amount of flow we were told to achieve, only send through a
fraction of the flow
26.
Recovering rational number from its remainder modulo huge integer Hi everyone!
It's been a while since I posted anything. Today I'd like to talk about [problem I](https://codeforces.me/gym/102354/problem/I) from [Oleksandr Kulkov Contest 2](https://codeforces.me/blog/entry/72656). Well, on some similar problem. Problem goes as follows: There is a rational number $x=\frac{p}{q}$, and you know that $1 \leq p, q \leq C$. You want to recover $p$ and $q$ but you only know number $r$ such that $r \equiv pq^{-1} \pmod{m}$ where $m > C^2$. In original problem $m$ was not fixed, instead you were allowed to query remainders $r_1,\dots,r_k$ of $x$ modulo several numbers $m_1,\dots,m_k$, which implied Chinese remainder theorem.
<br>
[cut]
<br>
To solve this problem let's start with the observation that we always can recover answer uniquely. Indeed, assume that there are numbers $p'$ and $q'$ such that $1 \leq p',q' \leq C$ and $p'q'^{-1} \equiv r \pmod{m}$. That would mean that $pq'\equiv p'q \pmod{m}$. But initial constraints claim that $C^2 < m$, thus...
\leq C$. Let's look on continued fraction for $\frac{r}{m}$ and its
convergents $\frac{p_1}{q_1}, \frac, look on continued fraction for $\frac{r}{m}$ and its convergents
$\frac{p_1}{q_1}, \frac{p_2}{q_2, The solution here is a bit sketchy as I only heard some continued fraction
solution in Petrozavodsk
27.
rationalisering — more issues with floating-point numbers I was motivated to write this blog post after reading [this blog post](https://codeforces.me/blog/entry/117430) about possible precision issues in output and requiring printing a rounded answer exactly instead of printing an answer within a tolerance. This blog post feels somewhat related insofar as that it has an issue with floating point numbers, and also a doubt as to the correctness of the underlying data. Alternatively, someone can find the mistake in my logic.
The problem in question is [Rationalization](https://open.kattis.com/problems/rationalisering) which asks to find a positive rational $\frac{A}{B}$ that is within a range $[C-F, C+F]$. Among all such fractions, minimize $A$, and among all such with minimal $A$, minimize $B$. The judge data guarantee that $1 \le A, B < 10^6$.
My solution path is as follows: If $C-F \le \frac{A}{B} \le C+F$, then $B(C-F) \le A \le B(C+F)$. Therefore, we can just check all $B$ in increasing order and find the smallest $B$ where $[B(C-F)...
~~~~~ from fractions import Fraction c = Fraction('7.80212, This fraction is not equal to either of $C-F$ and $C+F$.
28.
A look at Competitive Programming post-hibernation Hello friends!
As I've recollected in a previous [post](https://codeforces.me/blog/entry/97566), I am an old competitor who hadn't really participated since ~2014, and recently got a bout of nostalgia to return to Competitive Programming. So, I did a couple Topcoder SRMs, suffered through some SNWS rounds, participated in [three regional 5hr competitions](https://contest.yandex.ru/3QF2021) on three consecutive days, and dozed off at every Codeforces contest I tried to wake up for.
A lot of things are still the same as 8 years ago: [user:tourist,2022-01-26] is still at the top, grey coders still ask for how many minutes to solve a problem before reading the editorial, Russian university teams [continue winning](https://icpc.global/worldfinals/results) ACM ICPC, and Snarknews never gives up on his alternate competition formats. But in this post, I want to focus on the new patterns that emerged since my last time around.
#### #1: Codeforces rounds timing
Did you know that t...
but a fraction of this available back when I was a student!
29.
VK Cup 2018 Round 2 and Codeforces Round #472 Editorial Long time no see!
As [VK Cup Round 2](http://codeforces.me/contest/924) and its two parallel rounds ([Div. 1](http://codeforces.me/contest/956) and [Div. 2](http://codeforces.me/contest/957)) comes to a close, we're here to congratulate on all who did well on the contest and cheer for everyone who participated — the queue won't stop you!
Here are the detailed tutorials for the problems. Feel free to discuss in the comments!
Kudos to [user:arsor,2018-03-25] for translating the tutorials into Russian!
---
[tutorial:957A]
<spoiler summary="Model solution">
~~~~~
_, s = input(), input()
print('Yes' if
('??' in s or 'C?C' in s or 'M?M' in s or 'Y?Y' in s or s[0] == '?' or s[-1] == '?') and
not ('CC' in s or 'MM' in s or 'YY' in s)
else 'No')
~~~~~
</spoiler>
<spoiler summary="Alternative solution (Errichto)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void NO() {
puts("No");
exit(0);
}
void YES() {
puts("Yes");
exit(0)...
int x[MAXN], v[MAXN]; struct fraction { template static inline T gcd(const T a, // Time bounds at which clouds can arrive at the origin static std::pair<
fraction, fraction> t, ] = {fraction(-x[i], v1), fraction(-x[i], v2)}; }, fraction { template static inline T gcd(const T a, const T b) { return (b == 0, fraction() { } fraction(int64 num, int64 deno) : num(num), deno(deno) {
simplify(); }, inline bool operator < (const fraction &rhs) const { return num * rhs.deno <
deno, struct fraction { template static inline T gcd(const T a, const T b
Tutorial of VK Cup 2018 - Round 2
30.
Editorial of Codeforces Global Round 21 Thanks for participation!
If your solution to D involves any data structures and is not $O(n)$ -- please read the "solution 1". I believe it is very interesting, but to make the difficulty suitable for D we allowed not $O(n)$ solutions.
[problem:1696A]
<spoiler summary="Hint 1">
How many operations will we perform?
<spoiler summary="Answer">
At most one. Why?
</spoiler>
</spoiler>
<spoiler summary="Solution">
Suppose we can only perform exactly one operation. In this case the answer is $S=\max_{1\le i\le n}(a_i\mathrm{\ or\ }z)$. In fact, we can prove that this is the answer.
Define $a_i'$ as the value of $a_i$ after some operations.
It suffices to prove the answer will never exceed $S$. Note that $z$ will always become a submask of itself after any number of operations, so $a_i$ will always be a submask of $(a_i\mathrm{\ or\ }z)$ after any number of operations. This leads to the conclusion that $a_i'\le (a_i\mathrm{\ or\ }z)$ for all $i$. Thus $\max_{1\le i...
Tutorial of Codeforces Global Round 21
31.
[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...
hoc optimizations". In particular, the partial fraction decomposition
corresponds to, we move to the partial fraction decomposition is roughly the point where I
can't intuitively, As before, we want to find the partial fraction decomposition of
$\frac{\mathcal{C}(x)}{\mathcal{B
32.
Codeforces Trainings Season 1 Episode 10: Editorial #### **Welcome to The Editorial!**
<img src="http://th04.deviantart.net/fs70/PRE/f/2013/078/b/f/mi_super_saiyan_god_remasterizado_by_salvamakoto-d5ymxyi.png" height="50%" width="50%" />
**Keep the upvotes piling up! muhehe**
IZ.COMPLETE.
### A. Rasheda And The Zeriba
[cut] $\ $
(difficulty: medium)
The first question is: When is it possible to construct a (convex) polygon from sticks of given lengths $L_i$?
This question is answered by what's sometimes known as Polygon inequality theorem, which states that the sufficient and necessary condition is for every $L_i$ to be strictly less than the sum of all other $L_i$. You can imagine that it works because for the endpoints of every side, the shortest path between them (equal to the length of that side) must be smaller than any other path, including the other one along the perimeter of the polygon; constructing such a polygon, even a convex one, is pretty easy, just imagine it as having sticks linked to each other that...
33.
Codeforces Round #815 (Div. 2) Editorial [A — Burenka Plays with Fractions](https://codeforces.me/contest/1720/problem/A)
------------------
Authors: [user:zer0brain,2022-08-18]
<spoiler summary="Solution">
Note that we always can make fractions equal in two operations:
Multiply first fraction's enumerator by $bc$, the first fraction is equal to $\frac{abc}{b} = ac$,
Multiply second fraction's enumerator by $ad$, the second fraction is equal to $\frac{acd}{d} = ac$.
That means that the answer does not exceed 2.
If fractions are equal from input, the answer is 0. Otherwise, it can't be 0.
Now we have to check if the answer is 1. Let's assume that for making fractions equal in 1 operation we have to multiply first fraction's enumerator by $x$. Then $\frac{ax}{b} = \frac{c}{d}$ must be true. From this we can see that $x = \frac{bc}{ad}$. $x$ must be integer, so $bc$ must be divisible by $ad$. If we assume that we multiplied first fraction's denumerator by $x$, we can do the same calculations and see that...
: Multiply first fraction's enumerator by $bc$, the first fraction is equal to
$\frac{abc}{b} = ac
Tutorial of Codeforces Round 815 (Div. 2)
34.
Some useful conclutions for some naive algorithms to solve number theory problem Here are some useful conclutions for naive algorithms to solve number theory problem,I hope you can know something about it and solve number theory problems more easily.
# 1.The number of prime factors of an integer
It's sure that the number of prime factors of an integer is very small,and an integer $v$ can be the product of at most $\log_2(v)$ primes ($2 ^ k$ the worst).This can be used for bruteforce and State compression.
Thanks [user:AkiLotus,2024-09-21] to remind me that for the number of distinct prime factors of a integer $\operatorname{w}(n)$,$\sum_{i = 1}^n \operatorname{w}(n)$ is $\operatorname{O}(n \log \log n)$.
example:[510D](https://codeforces.me/problemset/problem/510/D),[problem:1422F].
# 2.The number of factors of an integer
First of all,$\sum_{i = 1} ^ n \operatorname{d}(n) = \sum_{i = 1} ^ n [\frac{n}{i}] \approx n \ln n$.
Then I've found out that the number of factors of an integer($\operatorname{d}(n)$) is usually small,and to make sure,I ma...
# 6.Special fraction sums
35.
[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., ...
1. **We want a Large `min_val`** – smaller fraction → good 2. **We want a Small
`dp[j
36.
[GYM] ACM ICPC Vietnam National First Round 2014 — Solutions Following are unofficial solutions for all problems.
[problem:100499A]
-----------------
**Solution 1**
The most obvious solution for this problem is to brute force all numbers, and check if it is a cool number. [My code](http://ideone.com/S5T6en)
After running this code for several minutes, you should be able to get results for all $K \leq 9$. The only result for $K = 7$ is $3211000$, for $K = 8$ is $42101000$ and for $K = 9$ is $521001000$. From these results, you should be able to guess the result for $K = 10$ is $6210001000$.
**Solution 2**
There are many ways to optimize the above solution. The most standard way is to see that the sum of all digits is equal to K, thus if you restrict your brute force to exit when sum of digit is greater than K, you should get a solution which runs in around a few seconds.
[problem:100499B]
-----------------
Since all numbers are at most $10^7$, you can count number of occurrence of each value.
[My code](http://ideone...
So, to solve this problem, you need to split the number into three parts:
Integer,fraction and
37.
Yandex Algo 2015 (cancelled) round 2 editorial Hello :)
I was the writer for the Round 2. I'm very sad that the contest platform failed and you couldn't do your best solving them -- for me it's also sad as my work on the problems is now wasted. Hopefully you liked the problems themselves.
Here are the problem statements:
- A http://pastebin.com/raw.php?i=U8SfbSL8
- B http://pastebin.com/raw.php?i=bAi07eMm
- C http://pastebin.com/raw.php?i=R72vqKkk
- D http://pastebin.com/raw.php?i=Ar5CmJ8j
- E http://pastebin.com/raw.php?i=wiCtb0ab
- F http://pastebin.com/raw.php?i=iaMnb9cs
And below are brief solution ideas. Ask if anything is unclear.
**A (ascending the stairs)**
Dynamic programming in O(n).
Let W[x] be the number of ways to climb the first x steps of the stairs. (We will call that "state x".)
W[n] is the answer we want.
For each x, let y be the lowest state that we can go directly from state y to state x -- i.e., the sum H[y]+...+H[x-1] is still <= m. Then W[x] is simply the sum of W[y] through W[...
38.
Codeforces Round 1044 (Div. 2) Editorial Thank you for participating in my round! I hope you all enjoyed it.
<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>
[problem:2133A]
<spoiler summary="Hint 1">
What does the speed of each gear depend on?
</spoiler>
<spoiler summary="Solution">
Suppose we have some arrangement of gears where gear $i$ from the left has $b_i$ teeth. Then the speed of gear $n$ is $1 \cdot \frac{b_1}{b_2} \cdot \frac{b_2}{b_3} \cdot \ldots \cdot \frac{b_{n-1}}{b_n}$. Notice that most of the fractions cancel, leaving only $\frac{b_1}{b_n}$. So in fact, the speed of gear $n$ depends only on $b_n...
Tutorial of Codeforces Round 1044 (Div. 2)
39.
This is most useful CP problem I create until now After Educational Codeforces Round 79, I want to share a problem I create this year.
It's host on 2019 [Multi-University Training Contest 5](http://acm.hdu.edu.cn/search.php?field=problem&key=2019+Multi-University+Training+Contest+5&source=1&searchmode=source).
[Problem link is here](http://acm.hdu.edu.cn/showproblem.php?pid=6624).
The statement of problem is following:
**Many problems require printing the probability of something. Moreover, it is common that if the answer is $\frac{a}{b}$, you should output $a \times b^{-1} \pmod{p}$ ($p$ is a prime number). In these problems, you cannot know the exact value of the probability. It's so confusing!!! Now, we want to reverse engineer the exact probability from such calculated output value x. We do so by guessing the probability is the one with the minimum $b$ such that $a \times b^{-1} = x \pmod{p}$. Now we invite you to solve this problem with us!**
What the statement mentioning is quite match the situation in contest ...
The following is the reference solution (you can use the code to get the correct
fraction format
40.
CodeAgon 2020 discussion thread. [Problems added] Guys please share your approaches for the problems you solved. How many did you guys solve?
Problem 1<br>
There are N cities numbered from 1 to N connected by M bidirectional roads. A concert is going to be held in each city and i_th city concert costs A[i] amount. Travelling through the roads also costs some amount given.
For each city i from 1 to N : find the minimum amount a person from city i has to spend to visit a concert in any of the city and come back to own city.
It may not be guarenteed that each city is reachable from other city.
N,M<=10^5
=====================================<br>
Problem 2
Given rooted tree of N vertices from 1 to N. Every vertex must not have same color as it's p-th ancestor. Every vertex must have either red or green color.
Calculate the number of ways to color the tree.
N,p<=10^5
=====================================<br>
Problem 3
You are going to make a necklace of N beads using K different colored beads. <br>
Th...
them from the array and append their average (in irreducable fraction from) to
the array.
It's, Your task is to calculate the number of distinct values the fraction can take,
modulo 1e9+7., fraction from) to the array.
It's guarenteed that A+B-C is multiple of C-1.
Indumati
41.
[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...
\frac{p}{q} \rfloor}{r}<\frac{1}{r}$. Since the fraction part of
$\frac{\lfloor \frac{p}{q} \rfloor
42.
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 `...
when your parenthesis include some fraction, summation, minimum/maximum with
limits, integration
43.
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...
44.
Codeforces Round 951 (Div. 2) Editorial Thank you for participating!
[problem:1979A]
------------------
<spoiler summary="Solution">
Let $m$ be the maximum among the numbers $a_i, a_{i + 1},\ldots, a_j$. Notice that there always exists such $k$ that $i \le k < j$ and $a_k = m$ or $a_{k + 1} = m$. Therefore, we can assume that Bob always chooses the pair of numbers $p$ and $p + 1$ ($1 \le p < n$) as $i$ and $j$.
Therefore you need to consider the maximums in pairs of adjacent elements and take the minimum among them. Let $min$ be the found minimum, then it is obvious that the answer is equal to $min - 1$.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a[n];
for (int& i : a) {
cin >> i;
}
int mini = max(a[0], a[1]);
for (int i = 1; i < n - 1; i++) {
mini = min(mini, max(a[i], a[i + 1]));
}
...
Tutorial of Codeforces Round 951 (Div. 2)
45.
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...
looked through a fraction of all code, I'm sure there are many more.
46.
How to Interpret Contest Ratings **UPDATE: the [new rating system paper](https://arxiv.org/abs/2101.00400) will appear in the Web Conference 2021!**
If you're new to competitive programming, you may be wondering: what are ratings and colors? What do they mean?
As a contestant and now coach of the UBC team, I've taken enough interest in the subject to have developed my own rating system, Elo-MMR, which I might describe in a future blog post. For now, I want to talk about ratings more generally: what does it mean to achieve a certain rating or title? How concerned should you be with your rating and title? Might it be harmful to be concerned with them at all?
A Brief History of Contest Ratings
--------------------------------------
Contest rating systems can trace their heritage back to the [Elo system](https://en.wikipedia.org/wiki/Elo_rating_system). Elo was devised for 2-player games, with rating updates based on whether a player wins, loses or draws. Starting in 1960, it was adopted by the chess community ...
recognize your handle and come to you for advice. People aspire to know even a
fraction of what you
47.
Farey sequence and Approximation of real number First, the Farey sequence $F_n$ represents the set of all completely reduced proper fractions with denominators not exceeding $n$, arranged in ascending order of value. Formally speaking,
$$F_n = \left\{\frac{p}{q} \bigg\vert 0 < p < q \le n, \, \gcd(p, q) = 1\right\}$$
The asymptotic size of this sequence is $\sum\limits_{i = 1}^{n} \varphi(n) \sim \frac{3}{\pi^2}n^2 + o(n \log n)$.
Regarding the Farey sequence, there are two classic conclusions:
- If $\frac{a}{b}$ and $\frac{c}{d}$ are two consecutive elements in $F_n$, then $\frac{a + c}{b + d}$ is also a valid Farey fraction.
- If $\frac{a}{b}$ and $\frac{c}{d}$ are two consecutive elements in $F_n$, then their next element $\frac{p}{q}$ satisfies
$$\begin{cases}p = \left\lfloor\frac{n + b}{d}\right\rfloor c - a \\ q = \left\lfloor\frac{n + b}{d}\right\rfloor d - b\end{cases}$$
We will only prove the second theorem above. For the Farey sequence of order $n$, two adjacent terms $\frac{a}{b} < \frac{c}{d}$ satisfy...
+ d}$ is also a valid Farey fraction., closest fraction $\frac{c}{d}$ that satisfies $bc - ad = 1$, we can use the
Extended Euclidean, - Count the fractions within this interval and find a valid fraction such that
its rank equals the, - Find an interval $\left[\frac{j}{n}, \, \frac{j + 1}{n}\right)$ such that the
targetfraction, - Find the smallest fraction $\frac{p}{q}$ strictly greater than $\frac{j}{n}$,
and use the, - Finding a fraction given its $\text{rank}$: $O(n\log{n})$, - Finding the $\text{rank}$ given a fraction: $O(n)$, - For a fraction with a denominator $q$, the numerator of the only possible
fraction can only be, - Note that there is at most one fraction for each different denominator within
this interval, // O(sqrt(n)log(n)^2) calculate the fraction of k-th rank PII
rank_to_fraction(ll n, ll k, > Given $n$ and a completely reduced proper fraction $\frac{p}{q} (q \le n)$,
determine its rank in, Obviously, from the definition of a proper fraction, we know $q > p$, so the
maximum $k = \left, }$ are two consecutive elements in $F_n$, then $\frac{a + c}{b + d}$ is also a
valid Fareyfraction
48.
Codeforces Round 993 (Div. 4) Editorial #### Special thanks to our hub of testuwuers for contributing solution explanations!
#### [problem:2044A]
Problem Credits: [user:cry,2024-12-15] <br>
Analysis: [user:macaquedev,2024-12-15]
<spoiler summary="Solution ">
For any $n$, Cube can set $a$ = any integer between $1$ and $n-1$ inclusive, and set $b = n - a$. $a$ cannot be less than $1$, because then it would be non-positive, and $a$ cannot be greater than $n-1$, because then $b$ would be less than $1$, which would make it non-positive. Therefore the answer is just $n-1$ for all $n$.
</spoiler>
<spoiler summary="Code (Python)">
```import sys
input = sys.stdin.readline
for _ in range(int(input())):
print(int(input())-1)
```
</spoiler>
#### [problem:2044B]
Problem Credits: [user:Lilypad,2024-12-15] <br>
Analysis: [user:Lilypad,2024-12-15], [user:macaquedev,2024-12-15]
<spoiler summary="Solution ">
The letters she reads that comprise string $b$ are just the letters that comprise string $a$, flip...
up a fraction using the `ceil` function; This has been a recurring issue in
almost every Div.4
Tutorial of Codeforces Round 993 (Div. 4)
49.
Codeforces Round #200 Tutorial #### [problem:344A]
By the definition each block consists of a number of consequent and equally oriented dominoes. That means that in places where adjacent dominoes are not oriented equally, one block ends and another block starts. So, if there are $x$ such places, the answer is equal to $x+1$.
Solution complexity: $O(n)$. Problem author: [user:gen,2013-09-15].
**Bonus:** The problem was created a day before the contest and filled in the last part of a physically flavoured DivII complect. :]
#### [problem:344B]
First solution. First, the sum $a+b+c$ should be even, since each bond adds 2 to the sum. Now let $x$, $y$, $z$ be the number of bonds between 1st and 2nd, 2nd and 3rd, 3rd and 1st atoms, accordingly. So we have to solve the system $x+z=a$, $y+x=b$, $z+y=c$. Now observe that the solution to the system is the length of the tangents on the triangle with sides of length $a$, $b$, $c$ to its inscribed circle, and are equal to $\frac{b+c-a}{2}$, $\frac{c+a-b}{2}$, $\fr...
If a fraction $\frac a b$ can be obtained with $k$ resistors, then it is simple
to calculate that
Tutorial of Codeforces Round 200 (Div. 1)
Tutorial of Codeforces Round 200 (Div. 2)
50.
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...
bother about the fraction maximization problem and don't care about $k$. Then,
it'll always be better, This means that the maximum value of the fraction is simply the maximum sum of
a sub-component in
Tutorial of Codeforces Round 525 (Div. 2)
51.
Competitive Programming in the Era of AI **Read the original post on :** https://www.vibhaas.net/posts/Competitive-Programming-in-the-era-of-AI/
<br>
<div align="center">
<img src="/predownloaded/3e/ae/3eaee0e93cf1784ab4923157729c81dd3a080fcf.jpg"
alt="Wanderer above the Sea of Fog, Caspar David Friedrich"
width="70%">
<br>
<small><i>Wanderer above the Sea of Fog, Caspar David Friedrich</i></small>
</div>
<blockquote>
Picture this. You've had a draining week at university or at work. You're exhausted, and you need a break. Most people would play a few video games, grab a few beers with their friends, or just sleep. But you have the (mis?)-fortune of being addicted to this weird, aesthetically questionable website called Codeforces (or AtCoder, or whatever your favorite OJ is).
</blockquote>
<blockquote>
You check the list of upcoming contests, and you're in luck. "Nice," you think to yourself, "two rated contests back to back!" This is going to allow you to farm some rating! ...
release of Large Language Models which can solve an increasing fraction of CP
problems, getting an AC
52.
Codeforces Round 736 Editorial All the division 2 problems were created by [user:Agnimandur,2021-07-06]. [problem:1548E] was created by [user:Benq,2021-07-06]. I hope that this hint-based editorial helps you, no matter what your rating is! Solution code is provided in both C++, Java, and Kotlin when available.
### [Solution Code Repository](https://github.com/Agnimandur/Round736Solutions)
<br/>
[problem:1549A]
---------------------------
<spoiler summary="Hint 1">
Fix $a$ into a convenient constant.
</spoiler>
<spoiler summary="Solution">
Since $P \ge 5$ and is also a prime number, we know that $P-1$ is an even composite number. A even composite number is guaranteed to have at least 2 unique divisors greater than 1. Let two of these divisors be $a$ and $b$. It is guaranteed that $P\mod{a} = P\mod{b} = 1$, and thus this selection is valid.
For example, we can simply pick $a=2$ and $b=P-1$, and we will get a correct solution.
The time complexity is $\mathcal{O}(Q)$.
</spoiler>
[problem...
The numerator and denominator of this fraction can be expanded in linear time.
Then all we have to
Tutorial of Codeforces Round 736 (Div. 1)
Tutorial of Codeforces Round 736 (Div. 2)
53.
Turkmen National OI — Day 2 ### A. Camel Caravan
There is a caravan of $n$ camels. You are fed up with seeing the same camel day after day. Now you wonder, how many ways are there to reorganize the camels, so that no camel sees the same camel as before?
По пустыне идет караван из $n$ верблюдов. За много дней путешествия надоедает идеть впереди себя одного и того же верблюда. Сколькими способами можно переставить верблюдов так, чтобы впереди каждого шел другой верблюд, чем до этого?
<div style="background:#FFFF99;border:1px solid #FF9B56;padding:5px;">
I had an argument with juries about what this task asks. I would be glad if you read russian version (which is official), and tell answers for $n = {1, 2, 3, 4, 5}$.
</div>
### B. Magic is Might
Given natural number $k$. Find $k^th$ number in the sequence consisting of powers of $2$: $2481632...$
For example for $k=4$ answer is $1$.
Задано некоторое натуральное число $k$. В последовательности $2481632...$ составленная из степеней $2$ найти цифру с...
54.
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...
need to calculate a fraction $\frac pq$ and ask you to output $r$ where $r
\cdot q \equiv p \pmod m, to the concept of a reciprocal, but here we don't want a fraction; we want an
integer, specifically, ? Even worse are those that say you need to calculate a fraction $\frac pq$ and
ask you to output $r
55.
Codeforces Round #196 — Problems Analysis [problem:337A]
--------------
First, let's sort the numbers `f[i]` in ascending order. Now assume that the smallest jigsaw puzzle which the teacher purchases consists of `f[k]` pieces. Obviously, she should buy the smallest `n` puzzles which are of size `f[k]` or greater to minimize the difference. These are the puzzles `f[k], f[k+1], ..., f[k+n-1]` (this is not correct when `f[i]` are not distinct and `f[k]=f[k-1]`, but such cases can be skipped). The difference between the greatest and the least size of the puzzles in such set is `f[k+n-1]-f[k]`.
To choose the optimal `f[k]`, we can test every `k` between 1 and `m-n` and pick the one producing the least difference. The full algorithm is as follows:
~~~~~
read(n, m, f[1..m])
sort(f[1..m])
best = INFINITY
for k = 1 to m-n
best = min(best, f[k+n-1] - f[k])
print best
~~~~~
[cut]
-
[problem:337B]
---------
Suppose that the width and height of the screen are `W` and `H` correspondingly. Since `W:H = a:b...
All that's left is to print the answer as an irreducible fraction. We need to
find the greatest
Tutorial of Codeforces Round 196 (Div. 2)
Tutorial of Codeforces Round 196 (Div. 1)
56.
Разбор Codeforces Round #325 [problem:586A]
The problem has been prepared by [user:adilbek-dalabaev,2015-10-12].
To solve this problem one should remove all leading and trailing zeroes from array and then calculate the number of ones and number of zeroes neighboured by ones. The sum of this values is the answer for the problem.
Complexity: $O(n)$.
[problem:586B]
The problem has been prepared by [user:Oleg_Smirnov,2015-10-12].
Let's call some path $i$th if we start it by going $i$ times left, then we cross the prospect and go left $n - 1 - i$ times again. Let $d_i$ be equal to the time we should wait on traffic lights while following $i$-th path. If we consider any way from the shop to home, it is equal (but reversed) to only path from home to the shop, meaning that we need to find two distinct paths from home to the shop. So the answer to the problem is the sum of the smallest and the second smallest values among $d_i$. One could easily calculate $d_i$ using calculated $d_{i-1}$, so $d_i$ could...
and the number of apples be denumerator of fraction. At every step we have two
fractions (at first, fraction and the answer is "Impossible". Other way, we could find it in the
tree. If $x>y$, we should
Tutorial of Codeforces Round 325 (Div. 1)
Tutorial of Codeforces Round 325 (Div. 2)
57.
Codeforces Round #172 Editorial Overview ...
==================
In DIV 1, there are 3 normal tasks accompanied with 2 challenge tasks.
About 40 competitors solve first three tasks during the contest and I believe there will be more if we extended the duration a little bit.
Task D is a standard data-structure problem hidden behind a classical maximum cost flow model. This kind of problem are usually trick-less, but hard to implement especially under the pressure. Because of this, it becomes tonight's draw-breaker.
Task E is a extended version on a classical DP && Math problem. There are many solutions to the original problem, one is giving a global view under the state transition, and using a data structure to handle it carefully. However, this one is even more harder, few people have ever tried it except [user:Jacob,2013-03-11]. (Although is wrong.)
As a seasoned competitor, [user:Petr,2013-03-10] took the C-B-A order which proved to be the best choice through out the night. And after quickly solved C and...
. Nearest Fraction](http://codeforces.me/problemset/problem/281/B) - [Problem
A. Rectangle Puzzle
Tutorial of Codeforces Round 172 (Div. 1)
Tutorial of Codeforces Round 172 (Div. 2)
58.
Response to "Is IOI Becoming Too Heuristic?" I wrote a comment for [this post](https://codeforces.me/blog/entry/156303) by [user:AmShZ,2026-08-30] and it became too long, so I made a separate blogpost.
Contains a bit of the spoiler for 2026 day 2 problems.
### On the title
I define heuristic problems as problems for which there is no reasonable way to infer the score of your solution (full or partial) solely from the problem statement PDF. Your score depends not on the objective merit of your solution, but on what the author decided to put in the input file.
Magic City has a solution that could reasonably be inferred solely from the PDF. It does not admit any heuristic that scores well. Therefore, I don’t think it is a heuristic problem.
I highly object to heuristic problems in top-level contests, especially for high school students. But I don’t think this was an issue for IOI 2026, so I would not open that can of worms here.
### Problems too hard
I think the main recurring issue with the IOI (not specific...
59.
Java 15 for competitive programming Java 15 was released a few days ago. Here are some changes that may be useful for competitive programming.
* Pattern matching for `instanceof`, first introduced in Java 14, is still a preview.
* Text blocks, first introduced in Java 13, are now final:
```
String input = """
3 3
1 2
1 3
2 3""";
```
* Records, first introduced in Java 14, are now final:
```
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);
}
// ...
}
```
* Useful new methods: `CharSequence.isEmpty()` (also inherited by `String`), `String.stripIndent()` (useful for text blocks), `String.formatted()`, `Math.absExact()`.
Previous posts: Java [8](/blog/entry/11156), [9](/blog/entry/54713), [10](/blog/entry/58502), [11](/blog/entry/62120), [12](/blog/entry...
3 2 3"""; ``` * Records, first introduced in Java 14, are now final: ``` record
Fraction, Fraction add(Fraction o) { return new Fraction(num * o.den + den * o.num, den *
o.den); }, ``` record Fraction(int num, int den) { Fraction { if (den == 0) { throw new
60.
(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. — [**Part-1 — 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...
For $N = 15$, $3^{15} \approx 14$ million operations, which executes in a
fraction of a second
61.
Codeforces Round #198 — Editorial [problem:340A]
------------------
You are given a range $[A, B]$. You're asked to compute fast how many numbers in the range are divisible by both $x$ and $y$. I'll present here an $O(log(max(x, y))$ solution. We made tests low so other not optimal solutions to pass as well. The solution refers to the original problem, where $x, y \le 10^9$.
Firstly, we can simplify the problem. Suppose we can calculate how many numbers are divisible in range $[1, X]$ by both $x$ and $y$. Can this solve our task? The answer is yes. All numbers in range $[1, B]$ divisible by both numbers should be counted, except the numbers lower than $A$ (1, 2, ..., A — 1). But, as you can see, numbers lower than A divisible by both numbers are actually numbers from range [1, A — 1]. So the answer of our task is f(B) — f(A — 1), where f(X) is how many numbers from 1, 2, ..., X are divisible by both x and y.
For calculate in $O(log(max(x, y))$ the f(X) we need some math. If you don't ...
As a conclusion, the answer is (S1 + 2 * Sleft) / N. For make fraction
irreducible, you can use
62.
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...
include a message indicating which particular value was `null`. * Records: ```
recordFraction(int, Fraction add(Fraction o) { return new Fraction(num * o.den + den * o.num, den *
o.den); }, ``` record Fraction(int num, int den) { Fraction { if (den == 0) { throw new
63.
Manthan, Codefest'19 Editorial ### [1208A — XORinacci](https://codeforces.me/contest/1208/problem/A)
The sequence is $a$, $b$, $a\oplus b$, $a$, $b$, $a\oplus b$ $\cdots$
Since, the sequence has a period of $3$, $f[i] = f[i \mod 3]$.
<br>
<spoiler summary="Code">
```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int test,a,b,n;
cin>>test;
while(test--){
cin>>a>>b>>n;
switch (n%3){
case 0:
cout<<a<<endl;
break;
case 1:
cout<<b<<endl;
break;
default:
cout<<(a^b)<<endl;
}
}
return 0;
}
```
</spoiler>
### [1208B — Uniqueness](https://codeforces.me/contest/1208/problem/B)
After removing a sub-segment, a prefix and a suffix remain, possibly of length $0$.
Let us fix the prefix which does not contain any duplicate elements and find the maximum suffix we can get without repeating the elements. We can use map/set ...
64.
AtCoder Beginner Contest 135 English Solutions #A — Harmony
Without loss of generality, let $A < B$. Then, we have three cases:
- $K$ is less than $A$. This gives $A - K = B - K$, which gives $A = B$, which is false.
- $K$ is greater than $B$. This gives $K - A = K - B$, which is also false.
- $K$ is between $A$ and $B$. This gives $K - A = B - K$, which gives $2K = A+B$.
Thus, we must have $2K=A+B$. If $A+B$ is odd, there is thus no solution. If $A+B$ is even, our answer is $\frac{A+B}{2}$. It is easy to verify that this number is indeed between $A$ and $B$.
Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc135/submissions/6560205)
---
#B — 0 or 1 Swap
Let $K$ be the number of positions $i$ at which $p_i \neq i$ (using 1-indexing). If $K = 0$, the answer is yes, as we can simply leave the permutation as is. If $K = 2$, the answer is also yes: swap the two misplaced elements. (Notice that we can never have $K = 1$, as if any element is put in the wrong posi...
fraction. - We must have that $NK \geq X+Y$ and that $NK = X+Y$ mod $2$. Both
of these are implied
65.
[Educational] Combinatorics Study Notes (3) Hello Codeforces!
Today I'll be writing about what I have learnt about combinatorics, which played, and, in my opinion, will still be playing an 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 third blog, which is friendly to 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.
### Previous Blogs
- [Combinatorics (1)](https://codeforces.me/blog/entry/110376)
- [Combinatorics (2)](https://codeforces.me/blog/entry/110390)
### Content
1. [Homework]((https://codeforces.me/blog/entry/110390)) Tutorial
2. Catalan Seq...
Reduce of the fraction, then $f'_{n+1}=\dbinom{2n-2}{n-1}$
66.
Online judge with IOI problem went public Hello everyone.
Two years ago there was a post titled "Submitting IOI problems" and [my comment](/blog/entry/10967#comment-161620) there. I offered everyone to contact me via PM on Codeforces to get the access and be able to solve problems from past IOIs (starting with IOI 2003). What was important here is that [user:PavelKunyavskiy,2016-06-12] and me took effort and made the system as similar to what was used on particular IOI as we could, including:
1. Original tests from archives
2. Tests grouping and correct subtasks scoring where applicable — you won't get 54 points if there are subtasks for 40 and 60 points — just like on IOI.
3. Interactive problems with interactive I/O (say, "Aliens" from IOI 2007 or "Maintain" from IOI 2003)
4. Partial scoring where you can get only a fraction of points per test, like "Reverse" from IOI 2003 or "Hotter Colder" from IOI 2010.
5. "Encode-decode" problems, where your solution is executed several times in separate processes, ...
2003) 4. Partial scoring where you can get only a fraction of points per test,
like "Reverse" from IOI, get only a fraction of points per test, like "Reverse" from IOI 2003 or
"Hotter Colder" from IOI 2010
67.
On linear recurrences and the math behind them Hi everyone!
There are already dozens of blogs on linear recurrences, why not make another one? In this article, my main goal is to highlight the possible approaches to solving linear recurrence relations, their applications and implications. I will try to derive the results with different approaches independently from each other, but will also highlight similarities between them after they're derived.
### Definitions
**Def. 1**. An order $d$ **homogeneous linear recurrence with constant coefficients** (or _linear recurrence_) is an equation of the form
$$
F_n = \sum\limits_{k=1}^d a_k F_{n-k}.
$$
**Def. 2**. In the equation above, the coefficients $a_1, \dots, a_d \in R$ are called the **recurrence parameters**,
**Def. 3**. and a sequence $F_0, F_1, \dots \in R$ is called an order $d$ **linear recurrence sequence**.
<hr>
The most common task with linear recurrences is, given initial coefficients $F_0, F_1, \dots, F_{d-1}$, to find the value of $F_n$.
<hr>
**Example...
the generating function representation, thanks to the existence of the [partial
fraction
68.
Rockethon 2014 Editorial In this post you will find the authors' solutions for the problems and subproblems featured in the competition, as well as some bonus questions related to these tasks.
[problem:391A]
--------------
Note that we can consider each maximal sequence of identical characters independently, since there is no way to insert a character and affect more than one such sequence. Also, note that there are multiple ways to correct a single maximal sequence by inserting one character into it: we can either insert a different character somewhere in this sequence and divide it into two sequences of odd length (this is always possible for a sequence of even length), or even just add the same character in any point of this sequence, thus increasing its length by 1 and changing its parity.
Therefore, the answer to the problem is the number of maximal sequences of even length. One can find all such sequences in linear time. A pseudocode of the solution follows:
~~~~~
i = 1
ans = 0
while i ...
small relative to the remaining number of segments, we know that a constant
fraction of segments
Tutorial of Rockethon 2014
69.
Help with some fractions operations Hi everybody!
I recently was in a programming contest. There were 20 tasks, and one of them was as follows:
In resume, you have C chairs and P pairs of chairs are given. The pairs $P(i,j)$ denote the probability of changing from chair $i$ to chair $j$. You are sitting in one of these chairs, and every second you have to move to another one.
Then you have Q queries, each with two integers $C_i, s$ , where $C_i$ is the initial chair you are seated and you have to tell the chair that has the highest probability of being seated in after $s$ seconds (after $s$ changes).
$1 \leq C_i \leq 50$
$1 \leq s \leq 100000000$
At first, I thought this was a simple problem, solvable using matrix exponentiation. First creating a matrix $M$, where $M_ij = P(i,j)$. The answer should be in the $C_i$ row of the resulting matrix $M^{ S}$, but the problem has the next important requirement:
You have to output the probability as an irreducible fraction. Worst of all, you have to output ON...
You have to output the probability as an irreducible fraction. Worst of all,
you have to output
70.
VK Cup 2012 Round 2 — Разбор ** UPD: Formulas are already fixed. **
**[problem:163A]**
Solution summary: dynamic programming.
Sample jury solution: [submission:1415300] (author = [user:levlam,2012-03-25])
The problem could be solved with the following dynamic programming.
Let $f[i, j]$ be the number of distinct pairs ("substring starting at
position $i$" and "subsequence of the substring $t[j\ldots |t|]$")
Then:
~~~~~
f[i, j] = f[i, j + 1];
if (s[i] == t[j])
add(f[i, j], f[i + 1, j + 1] + 1)
~~~~~
Answer = $\sum$ f[i,0]
**[problem:163B]**
Solution summary: sorting + binary search.
Sample jury solution: [submission:1415306] (author: [user:Burunduk1,2012-03-25])
We need to find the minimal time $T$.
Let us find it using binary search.
Once the time is fixed, one can arrange lemmings using greedy approach
starting either from the top or from the bottom.
In this solution we consider the way to start from the bottom.
Among all lemmings, that can get on the first ledge, l...
Tutorial of VK Cup 2012 Round 2
Tutorial of VK Cup 2012 Round 2 (Unofficial Div. 2 Edition)
71.
Yandex.Algorithm Test Round Analysis Test Round and its analysis were prepared by [user:snarknews,2013-07-07] and [user:Gassa,2013-07-07]. Problems of the Test Round have already been used before in different competitions. The following rounds will consist of new original problems, and you can still [register](http://algorithm.contest.yandex.com/register/) and compete in the [Qualification Round](http://algorithm.contest.yandex.com/contest/307/enter/).
During the round a lot of participants tried to make "blind" submits, from time to time even going to the top places, but as the system tests showed with only one problem solved in fact.
By the end of the round [user:tourist,2013-07-07] was at the first place with all problems but B submitted "blind". [user:vepifanov,2013-07-07] was at the second place with A, C and D submitted "blind", but B and F — submitted "open" (both with a wrong attempt), [user:Anton_Lunyov,2013-07-07] was at the third place with only C submitted "blind". All other participants had less ...
. So, $R^2$ can be computed exactly as an integer fraction $\frac{a^2 \cdot b^2
\cdot c^2}{16S^2}$.
72.
Randomized Algorithms and Online Judges Randomization is known to be a powerful algorithmic technique, and I want to start a discussion about it specifically in the context of competitive programming. What extra considerations should we make about how online judges work when analyzing our randomized algorithms, and approving such problems for an official contest? In particular, I want to discuss algorithms whose running times are uncertain.
Let's say that the running time of an algorithm is a random variable $X$. Typically, we might say the algorithm is acceptable if the expected running time is a fraction of the time limit: $E(X)=T/k$. With Markov's inequality, we can say $P(X>T)\le 1/k$. That is, the probability of failing a test case due to timeout is at most $1/k$.
TLE Trick
------------------
Online judges usually run your program a few times before giving the Time Limit Exceeded verdict. This fact is known to help randomized algorithms, as mentioned here: https://codeforces.me/blog/entry/78817
Let's apply...
the algorithm is acceptable if the expected running time is a fraction of the
time limit: $E(X)=T/k
73.
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_...
74.
Editorial Codeforces Round #184 (Div.2) ## [problem:305A]
All you have to do is implement following algorithm:
1. If we have numbers $0$ or $100$, we take them to needed subset.
2. If we got number greater than $0$ and less than 10, we take it.
3. If we got number $x \in [10;100)$ divisible by 10 we take it.
4. In case we have no numbers of second and third type, we take a number $x \in [10;100)$ that is not divisible by 10
[Solution](http://pastebin.com/nQXi0Khh)
## [problem:305B]
There are at most two ways to represent rational fraction as continued. Using Euclid algorithm you can do that for $\frac{p}{q}$ and then check equality of corresponding $a_i$.
[Solution](http://pastebin.com/x4rXtxen)
## [problem:305C]
First of all, let's carry over all powers of two in the following way: if we have $a_i = a_j$, $i \ne j$, carry 1 to $a_i + 1$.
Now as all of $a_i$ are distinct, the answer is $max(a_i)$ — $cnt(a_i)$ + 1, where $max(a_i)$ — maximal value of $a_i$,$cnt(a_i)$ — size of $a$
...
There are at most two ways to represent rational fraction as continued. Using
Euclid algorithm you
75.
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...
irreducible fraction.
76.
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 ...
total tested to get a fraction. You will see neat fractions: p = 3 → 1/2, : what fraction of all positive integers x are good? (That fraction is called
the density of good x.)
77.
Solutions for Codeforces Beta Round #70 (Div. 2) <p><b>A.</b> You should count a number of vowels for every of three phrases. Next, you should compare this numbers with numbers 5, 7 and 5. If all is <span id="result_box" class="short_text" lang="en"><span title="Нажмите, чтобы увидеть альтернативный перевод" class="hps">matched, answer is YES, otherwise answer is NO.</span></span><br><br>Author of problem is <a class="rated-user user-orange" href="../../../profile/Ripatti" title="Майор Ripatti">Ripatti</a>.<br>[cut]<br><br><b>B.</b> At first, you can $[n/7]$ times output string "ROYGBIV" ($[]$ is a rounding down). After than you can output "", "G", "GB", "YGB", "YGBI", "OYGBI" or "OYGBIV" according to remainder of division $n$ by 7. A resulting string will satisfy problem's <span id="result_box" class="short_text" lang="en"><span title="Нажмите, чтобы увидеть альтернативный перевод" class="hps">requirement</span></span>s.<br><br>You can also build answer in other way.<br><br>Author of problem is <a class="rated-user user-orange" href...
, let's consider a graph consisting of 4 parts:
1 - source (one vertex)
2 - first fraction (nxn, fraction (nxn vertices)
3 - second fraction (nxn vertices)
4 - sink (one vertex)
Each vertex
Tutorial of Codeforces Beta Round 70 (Div. 2)
78.
Forbidden sets\Find the kth maximum among a large set Hello, Codeforces!
==================
<spoiler summary="Really sorry">
Text may have a lot of mistakes, but i really tried very hard to make my post understandable.
</spoiler>
In this post I would like to talk about solving two types of problems, with almost the same solution. Unfortunately, I do not know how popular this idea is. For the first time I came up with it at the regional stage of 2021/22 in informatics for a certain subtask. And few days ago I noticed the idea in a problem from Google Kick Start and [problem:1637E], so I decided to write this post.
Problem 1
------------------
**Definition:** Given an integer $0 \leq K < 10^5$ and 2 _sorted in ascending order_ arrays $a_1, a_2, \ldots, a_n \ (a_i \leq 10^9)$ and $b_1, b_2, \ldots, b_n \ (b_i \leq 10^9)$. Were written $n^2$ fractions of the form $\frac{a_i}{b_j}, 1 \leq i \leq n, 1 \leq j \leq n$. After that, all these fractions were sorted in ascending order. You need to print the value of the $k$-th ascending...
$k$-th ascending fraction.
, ascending fraction.
**Idea:** It would seem to be generated $n^2 \leq 10^{10}$ and you cant, denote by $(i, j)$ fraction $\frac{a_i}{b_j}$. Not hard to notice, that $(i,
j) \leq (i + 1, j
79.
A2SV G5 ASTU — Contest #2 Editorial [Here](https://codeforces.me/gym/495407) is the mashup link (the problems are from Codeforces' problem set).
#### [A. The Lone Element Quest](https://codeforces.me/gym/495407/problem/A)
<spoiler summary="Solution">
To identify the unique element, this solution counts the occurrences of each number in the array. Then, it locates its index in the array.
</spoiler>
<spoiler summary="Code">
```python
from collections import Counter
t = int(input())
for _ in range(t):
n = int(input())
nums = list(map(int, input().split()))
count = Counter(nums)
for key in count:
if count[key] == 1:
mynum = key
for i in range(len(nums)):
if nums[i] == mynum:
print(i + 1)
break
```
</spoiler>
#### [B. YetnotherrokenKeoard](https://codeforces.me/gym/495407/problem/B)
<spoiler summary="Solution">
To solve the problem quickly, we can maintain two stacks: one for uppercase letters and one for low...
$, simplification yields $(-9/6 => -3/2)$, and the simplified fraction $(-3,
2)$ is used as a key in the, Fraction
80.
Number theory practice problems. Nothing is well understood unless we can apply it to solve some problems. Currently, I am learning number theory and there is no good classified list of problems for number theory. So, It is difficult to find some problem based on a specific topic.
Here I will maintain a list of problems of number theory in a few category. So, In near future, nobody have to face the same problem. Contribute interesting problems, people(mostly me :D ) will be grateful to you.
**1. Divisibility/Primes/Co-prime/GCD/LCM**
_Problems:_
1. **_LOJ_:** [1014](http://www.lightoj.com/volume_showproblem.php?problem=1014), [1035](http://www.lightoj.com/volume_showproblem.php?problem=1035)
2. **_CF_:** [230B](http://codeforces.me/problemset/problem/230/B), [711E](http://codeforces.me/problemset/problem/711/E),
[585E](http://codeforces.me/contest/585/problem/E), [585C](http://codeforces.me/contest/585/problem/C), [222C](http://codeforces.me/contest/222/problem/C), [546D](http://codeforces.me/con...
**2. Continued Fraction** _Problems:_ 1. **_UVA_:**
[834](https://uva.onlinejudge.org
81.
Is removing tags broken? I tried to remove the "constructive algorithms" tag from [problem:1704F] because the way I see it, there is nothing "constructive" about that problem. Within a minute, it reappears.
The first impression one might have is that I got into an "edit war" with someone who adds it back. However, I tried it 3 different times during the day (each time multiple times) and it has reappeared quickly every time. I don't believe that out of the few hundred people who have tag edit access on that problem, out of whom only a fraction care about the tags, out of whom only a fraction think the problem is "constructive", someone would instantly notice that the tag was gone and re-add it every time.
There is the possibility that it is done by a bot, but it seems unlikely that someone would write a bot like that seeing as it serves no purpose and is not that trivial to do.
The most likely interpretation still seems to be that removing the tag is actually broken. My theory is that the server cach...
on that problem, out of whom only a fraction care about the tags, out of whom
only afraction think, , out of whom only a fraction care about the tags, out of whom only a fraction
think the problem is
82.
Разбор задач Codeforces Round #137 (Div. 2) Problem A:
Note that the k-th element is copied to the end. Then the (k+1)-th element from the initial sequence is copied, then (k+2)-th, … , n-th, k-th, (k+1)-th, etc.
So all the numbers on the blackboard will become equal if and only if all the numbers from the k-th to the n-th in the initial sequence were equal.
It's now also obvious that the number of operations needed for it is equal to the index of the last number that is not equal to the n-th element of the initial sequence,
because it's exactly the number of deletions needed to eliminate the elements that are not equal to the last one.
If this number is greater than k, than answer is -1. Complexity — O(n).
Problem B:
Let’s store the order of the rows and columns of table.
Thus, row[x] is the number of the row x in the initial table and column[x] is the number of column x in the initial table.
Then, the value of an element in the row x and column y in the current table is equal to t[row[x], column[y]], where t — i...
in the condition. One of the ways to do it is to note that the fraction from
the statement
Tutorial of Codeforces Round 137 (Div. 2)
83.
Codeforces Round #362 (Editorial) [Here](https://gitlab.com/amirmd76/cf-round-362/tree/master) is git repository to solutions of problems of this contest.
### Div.2 A
You should check two cases for YES:
1. $x\ mod\ s = t\ mod\ s$ and $t \leq x$
2. $x\ mod\ s = (t + 1)\ mod\ s$ and $t+1 < x$
Time Complexity: $\mathcal O(1)$
[Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/2A)
### Div.2 B
Nothing special, right? just find the position of letters `.` and `e` with string searching methods (like `.find`) and do the rest.
Time Complexity: $\mathcal O(n)$
[Codes](https://gitlab.com/amirmd76/cf-round-362/tree/master/2B)
### A
Do what problem wants from you. The only thing is to find the path between the two vertices (or LCA) in the tree. You can do this in $\mathcal O(lg(n))$ since the height of the tree is...
First of all let's solve the problem if we only want to find the fraction
$\frac{p}{q}$. Suppose
Tutorial of Codeforces Round 362 (Div. 1)
84.
Tutorial for AlgoArena 2026 [Problem A1 : Pentagon Orchard(Easy version)](https://codeforces.me/gym/664936/problem/A1) <br>
Author : [user:Casual_W,2026-01-18]
<spoiler summary="Hint1">
First, calculate the total number of trees without worrying about visibility.<br>
Layer 1 has 5 trees.<br>
Layer 2 has 10 trees.<br>
.......<br>
Layer $k$ has $5k$ trees.<br>
What is the sum of $5k$ for $k=1$ to $n$?
</spoiler>
<spoiler summary="Hint 2">
A tree is "visible" if no other tree blocks the line of sight from the center.
Think of a tree's position as a fraction along one side of the pentagon.
A tree at layer $k$ and position $m$ (where $0 \le m \le k$) corresponds to the fraction $m/k$.
When is the fraction $m/k$ "blocked" by a previous layer?
It is blocked if the fraction can be simplified (e.g., $2/4$ is blocked by $1/2$).
</spoiler>
<spoiler summary="Hint 3">
A tree is visible only if its position fraction $m/k$ cannot be simplified.
This happens when $\gcd(m, k) = 1$.
The number of integ...
A tree is visible only if its position fraction $m/k$ cannot be, center. Think of a tree's position as a fraction along one side of the
pentagon. A tree at layer, means the fraction $\frac{m}{k}$ must be irreducible.
$$ \text{Condition for, side. The relative position of a tree can be described by the fraction
$\frac{m}{k}$.
85.
A2SV G5 — Contest #10 Editorial [Here](https://codeforces.me/contestInvitation/f9a3ec3d30cb15397ba1c3cd0a4a744bd3f8a2c5) is the link to the contest.
#### [A. Longest Non-Palindromic Subsequence](https://codeforces.me/gym/514644/problem/A)
<spoiler summary = "Solution">
Consider the substring of $s$ from the second character to the last, or $s_2s_3⋯s_n$. If it's not palindrome, then the answer must be $n−1$. What if it's palindrome? This implies that $s_2=s_n, s_3=s_{n−1}$, and so on. Meanwhile, the fact that $s$ is palindrome implies $s_1=s_n, s_2=s_{n−1}$, etc. So we get $s_1=s_n=s_2=s_{n−1}=⋯$ or that all characters in $s$ is the same. In this situation, every subsequence of $s$ is palindrome of course, so the answer should be $−1$.
</spoiler>
<spoiler summary="Code">
```python3
import sys
t = int(sys.stdin.readline().strip())
for _ in range(t):
s = sys.stdin.readline().strip()
if len(set(list(s))) == 1:
print(- 1)
else:
print(len(s) - 1)
```
</spoiler>
###...
numbers may be not precise enough. Let's store each fraction as a pair of
integers $(x,y)$, where $x$ is, Otherwise, we should choose $d=−b_i/a_i$. Let's calculate the required fraction
for each index, and
86.
О двоичных спусках и fractional cascading Всем привет, <s>мне так понравилось как растет мой вклад</s> я вижу, что вам понравился разбор в предыдущем посте, поэтому я решил периодически рассказывать о разных задачах, во многом, с применением не очень сложных структур данных. <br>
Сегодня я рассажу вам об оптимизациях дерева отрезков и декартовых деревьях(все вещи аналогичны ДО), позволяющих скинуть лишний логарифм в асимптотике, также разберу одну подзадачу, позволяющую решать кучу задач. <br>
**Будут разобраны:** <br>
1. Двоичный спуск <br>
2. Fractional cascading <br>
3. Задачи с удалением и добавлением элементов <br>
[cut]
<br>
**1) Двоичный спуск** <br>
Пусть вам надо найти элемент, начиная с которого сумма больше K, а вы очень упорный и не любите частичные суммы, зато хлебом вас не корми, дай дерево отрезков написать! А всё это надо сделать за log!! Как быть? На помощь приходят двоичные спуски! <br>
Пусть вы знаете сумму в левом поддереве, тогда если она больше K0, то переходим в него, иначе — в правое под...
строится fraction cascading](https://cdn.pbrd.co/images/HjNrcKz.gif)
Вернёмся к задаче и, В целом, fraction cascadinbg используется в задачах на MergeSortTree, в которых
требуется каждый
87.
Does IOI rank correlate with CF rating? **Background**
I have recently stumbled across [a paper](https://www.imf.org/en/Publications/WP/Issues/2018/12/07/Invisible-Geniuses-Could-the-Knowledge-Frontier-Advance-Faster-46383) which analyzed the correlation between the IMO medal and future success in the mathematical field. So, inspired by annual predictions of IOI rankings based on CF ratings, I <s> don't know what to do with my time </s> decided to take a more "serious" approach.
**Method**
I collected the data from the last $7$ editions of IOI in order to create the graph of $f(x)$ is the maximal rating of the participant with rank $x$. For the last $6$ editions, I relied almost solely on the IOI statistics website. The $2012$ edition, however, is missing a lot of information and I collected the CF handles either from snarknews or by finding the handle on search engines.
I put the participants in the same order they were arranged in the scoreboard, so if there are multiple people on the same position, they would ...
$$ \begin{array}{c|lcr} & \# & \text{Fraction of CF users} & \text{Median} &
\text{Mean, } & \# & \text{Fraction of CF users} & \text{Median} & \text{Mean} \\ \hline
\text{Gold} & 25
88.
Codeforces Round #341 (Div. 2) Editorial [problem:621A]
First, if the sum of all the numbers is already even, then we do nothing. Otherwise, we remove the smallest odd number. Since, if the sum is odd, we need to remove a number with the same parity to make the sum even. Notice it's always bad to remove more odd numbers, and it does nothing to remove even numbers.
[problem:621B]
Let's start with two bishops (x1, y1) and (x2, y2). Notice that if (x1, y1) attacks (x2, y2), either x1 + y1 == x2 + y2 OR x1 — y1 == x2 — y2. So, for each bishop (x, y), we will store x + y in one map and x — y in another map.
[problem:621C]
Let $f(x)$ be the probability that the product of the number of flowers of sharks $x$ and $(x+1) \mod n$ is divisible by $p$.
We want the expected value of the number of pairs of neighbouring sharks whose flower numbers are divisible by $p$. From linearity of expectation, this is equal to the probabilities that each pair multiplies to a number divisible by $p$, or $f(0)+f(1)+....
} = \frac{1}{(10/3)}^{x^y} = \frac{1}{(10/3)^{x^y}}$. But the denominator of
thisfraction is something we
Tutorial of Codeforces Round 341 (Div. 2)
89.
Let's discuss contest proposals Hello, Codeforces!
The current state of affairs is that running your own a contest on Codeforces is quite difficult. First, Codeforces doesn't accept single-problem proposals, so if you don't have many CP friends and can't make 6 good problems, you're out of luck. Second, many trash problems get proposed, and the coordinators have to spend much time filtering them out and then explaining why these problems were rejected. This status quo is bad for everyone, both participants and problem setters, so I'm thinking of a way to fix the situation.
Here is my idea. People generate trash problems because, when just a single of their problems is rejected, the whole contest is in danger, so problem setters 'bruteforce' problems to plug the hole. What if we help problem setters to propose just a single problem, and then problems from different people could be merged into a contest? This would reduce the fraction of bad problems because setters won't propose them just to fill holes.
The q...
people could be merged into a contest? This would reduce the fraction of bad
problems because setters
90.
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 ...
In the minimal sequence of a fraction with a maximal number of, in the minimal sequence of a reachable fraction $\frac{p}{q},\quad 1\le p,q\le
N$. Look at the, // The maximum division presses is exactly m - 2. // A fraction achieving this
optimally is F
91.
2025 ICPC Asia Manila Regional (Gym) Editorial [problem:106262A]
<spoiler summary="Hint">
There is only one way for the leftmost piece and the rightmost piece to refer to the same object.
</spoiler>
<spoiler summary="Solution">
If $n=0$, then Alice and Bob will not fight. Since they eat $2$ pieces at a time, that means $n=2, 4, 6, 8, 10, ...$ (i.e. the even numbers) will also have them not fight.
If $n=1$, then Alice and Bob will fight over that once piece. Since they eat $2$ pieces at a time, that means $n=3, 5, 7, 9, 11, ...$ (i.e. the odd numbers) will have them fight. Since an equal number of pieces are eaten from the left and the right, we know it is the center piece that remains (when $0$-indexed, this is at index $\lfloor n/2 \rfloor$).
So, the problem is just a parity check.
</spoiler>
[problem:106262B]
<spoiler summary="Hint">
For some letter, how many times does this letter occur in the substring of $t$ that begins at position $i$ and has some length $\mathrm{len}$?
You can answer this in $O(1...
Ignore the fraction. The interesting part is computing all the sums of powers
in subquadratic time
Tutorial of 2025 ICPC Asia Manila Regional
92.
My Pupil's editorial for Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 - I recently took part in [contest:2020], and I performed ... poorly (only A after 6 bad submissions). Thinking about this traumatizing experience, I first tried to find excuses. I entered 15 minutes late, I was sick and unprepared. But I realized that there were more to learn from it, and I wanted to try and produce a custom editorial of the first 4 problems in the contest to better understand and share what I did wrong (and also perhaps right thing :)).<br>
Welcome to my humble editorial
##[problem:2020A]
The first step was to understand the structure of the optimal solution. For given $n$ and $k$, the optimal number of operations is obtained by removing the largest possible portions of $n$ of the form $k^x$ at each step, i.e. finding the largest $x$ such that $k^x \leq n$.
The algorithm is as follows :
```
while n > 0
x = findLargestX(n,k)
while n-k^x > 0
n -= k^x
```
I was quickly able to see that the answer is the sum of the digits of $n$ in ba...
With $1 < k \leq n$, it is guaranteed that the fraction is greater to 0.
We now want to prove
93.
Experiment: dynamic problem max. scores Hello everyone.
The idea of dynamic problem scores is not new.
As far as I can remember, something that was discussed back in 2000.
Since then, the issue has surfaced several times — one of the latest experiments have
been organized by [user:Alex_KPR,2012-03-23].
Why do we need different problem scores? As correctly observed [user:RAD,2012-03-23],
they are actually needed for contests where the solution has a chance to fail after coding phase.
For example, Bob solved easy A, and Peter solved easy A and really hard B.
But Peter's A failed system tests and he solved B later (and may not from the first attempt).
In this case, if the problems were equal in value, Peter will take place below Bob, that somehow unfair.
Typically Codeforces problems has divible by 500 values: 500, 1000, 1500, etc. Usually we
try to pick up a 5-problems sets, varying in complexity. In this case, each
contestant will find interesting problems (for him/her). The traditional set of tasks ...
| Solvers fraction | Max. problem points | | --- | --- | | (0.707, 1] | 250 | |
(0.500, 0.707, |Solvers fraction | Max. problem points | |-----------------|--------| |(1/2,
1] | 500| |(1/4, 1
94.
Problems from analysis ## Problems from analysis
### 1 数学分析wsj习题5.41
$$
p_n(x)=\frac{1}{2^nn!}\frac{d^n}{dx^n}(x^2-1)^n\\
prove:\ p_n(1)=1 \\
proof\ 1:\\
\frac{d^n}{dx^n}(x^2-1)^n=n!\sum_{k=1}^n\binom{n}{k}\binom{2k}{n}x^{2k-n}(-1)^{n-k}\\
x=1\\
\sum_{k}\binom{n}{k}\binom{2k}{n}(-1)^{n-k}\\\
=\sum_{k}\binom{n}{k}\binom{2k}{n}(-1)^{n-k}\\
=\sum_{k,j}\binom{n}{k}\binom{k}{j}\binom{k}{n-j}(-1)^{n-k}\\
=\sum_{k,j}\binom{n}{j}\binom{n-j}{k-j}\binom{k}{n-j}(-1)^{n-k}\\
=\sum_{k,j,l}\binom{n}{j}\binom{n-j}{k-j}\binom{k-j}{l}\binom{j}{n-j-l}(-1)^{n-k}\\
=\sum_{k,j,l}\binom{n}{j}\binom{n-j}{l}\binom{n-j-l}{k-j-l}\binom{j}{n-j-l}(-1)^{n-k}\\
=\sum_{k,j,l}\binom{n}{j}\binom{n-j}{l}\binom{j}{n-j-l}(-1)^{n+j+l}(-1)^{k-j-l}\binom{n-j-l}{k-j-l}\\
=\sum_{k,j,l}\binom{n}{j}\binom{n-j}{l}\binom{j}{n-j-l}(-1)^{n+j+l}[j+l==n]\\
=\sum_{j}\binom{n}{j}\\
=2^n
$$
$$
prove \ 2:
\sum_{k}\binom{n}{k}\binom{2k}{n}(-1)^{n-k}\\
=\sum_{k}\binom{k}{n-k}\binom{2k}{k}(-1)^{n-k}\\
=[x^n]\sum_{k}\binom{2k}{k}(1+x)^...
Partial Fraction Expansion $$
F(x)=\frac{x!}{(x+n+1)!}=\frac{1}{(x+n+1)(x+n)...(x+1)} $$, convert it into partial fraction $$ F(x)=\sum_{k=1}^{n+1}\frac{b_k}{x+k}\\
b_k=\lim_{x\to-k}(x+k
95.
VK Cup 2016 Round 1 — Editorial Codes in nicer format will be uploaded later.
[problem:658A] and [problem:639A] — [codes](http://ideone.com/NYuwV8).
[problem:639B] and [problem:639C] — [codes](http://ideone.com/GcUNZJ).
[problem:639D] — [codes](http://ideone.com/FkE3DU).
[problem:639E] — [codes](http://ideone.com/OoSLF3).
[problem:639F] — [codes](http://ideone.com/PUSLI2).
[problem:658A] — Iterate once from left to right to calculate one player's score and then iterate from right to left. It's generally good not to write something similar twice because you are more likely to make mistakes. Or maybe later you will find some bug and correct it only in one place. So, try to write calculating score in a function and run them twice. Maybe you will need to reverse the given arrays in some moment.
[problem:639A] — You should remember all friends displayed currently (in set or list) and when you add someone new you must check whether there are at most $k$ people ...
problems by a fraction $\frac{p_i}{t_i}$ and it doesn't depend on a constant
$c$. There may be many
Tutorial of VK Cup 2016 - Round 1
Tutorial of VK Cup 2016 - Round 1 (Div.1 Edition)
Tutorial of VK Cup 2016 - Round 1 (Div. 2 Edition)
96.
Very short Editorial of SRM #671 Sorry for long testing queues and timeouts. I hope it won't repeat.
Congratulations for the winners — [user:tourist,2015-10-14], [user:Petr,2015-10-14], [user:Egor,2015-10-14], and [user:snuke,2015-10-14]. They managed to solve all three problems!
Thanks for helping Limak again. What do you think about problems? Feedback will be appreciated.
#### Div2
**250, BearPaints** — Iterate over one side of desired blue rectangle and in constant time calculate maximum possible second side. [code](http://ideone.com/6mflPV)
**500, BearDartsDiv2** — Iterate over three numbers. For found value of a*b*c we must know how many times it occurs in some suffix of a sequence. We need an array or a map. [code](http://ideone.com/SO6u9G)
**1000, BearDestroysDiv2** — Dynamic programming with bitmasks, $O(2^W \cdot H \cdot W)$. Iterate over cells in the given order (first row, then second row and so on) and consider all possible state of the next $W+1$ cells. [code](htt...
97.
Robocontest Round 103 Editorial ### Thank you for Participating !
#### [A.Hasan and Binary Function](https://robocontest.uz/olympiads/2619/tasks/A)
<spoiler summary="Solution">
We can obtain $n$ from the binary representation as following
$$\displaystyle n=\sum_{i=0}^{|s|-1}2^i \times (s_i=\mathtt{'1'})$$
We know that the fact
$$\displaystyle \sum_{i=0}^n 2^i=2^{n+1}-1$$
Let’s consider the last active bit i.e. $\mathtt{1}$ is $i$ then $n$ as integer is
$$\displaystyle \sum_{i=0}^n 2^i=2^{n+1}-1 \implies \lfloor \log_2(2^{i+1}-1) \rfloor = i$$
thus the answer is the index of last occurrence of $\mathtt{1}$ , Complexity $O(n)$.
</spoiler>
<spoiler summary="Code">
```python
for _ in range(int(input())):
n=int(input())
s=input()
ans=0
for i in range(n):
if(s[i]=='1'):
ans=n-i-1
break
print(ans)
```
</spoiler>
#### [B.Hasan and Beautiful !](https://robocontest.uz/olympiads/2619/tasks/B)
<spoiler summary="Solution">
Maintain two array...
Now we want to have $a \bmod b = 0$ (assuming fraction $\frac{a}{b}$) , so a
productive greedy is
98.
Cost-Benefit Flow ## Motivation
By chance, I stumbled upon the blog post by [user:errorgorn,2025-11-22] titled [Solving Problems with Min Cut Max Flow Duality](https://codeforces.me/blog/entry/136761). When they mentioned using flow (for certain problems) in a similar way to 2SAT, something clicked for me. While I knew how to solve a variety of flow problems along with forming certain flow networks ad hoc, there was this entire subset of flow problems which I previously did not understand how to do.
The blog post does a great job of explaining many of the concepts/applications, but there were certain things that got black-boxed. In order to understand things, my brain works such that truly understanding what is going on under the hood (often through proofs) helps me better intuit how to use ~~and abuse~~ a tool. Naturally, I tried to search the internet for more information on this topic. Unfortunately, I quickly came to realize that not much material as in-depth as the aforementioned blog p...
who reads even a fraction of it to come away with having learned something
new, whether that's the
99.
Beginner's Guide to Greedy _This blog post is a submission for the [Codeforces Month of Blog Posts Pt. III challenge](https://codeforces.me/blog/entry/149422). Thank you [user:cadmiumky,2026-02-10] for the initiative!_
This is how I wish I had been introduced to Greedy. Learning _how to prove_ is the truly valuable skill, one that I believe good Greedy problems test rigorously.
### **Introduction**
After struggling with proofs for quite a while, there are a few things I realized. Greedy proofs are very dependent on the rules of the problem. Loosely speaking each optimization problem gives you observations, from those observations, you realize that if you take certain choices while avoiding all others, then it will always be optimal. That realization is termed **Greedy**.
There are a lot of optimization problems, but only a small subset allows you to break the problem into smaller independent subproblems where solving them optimally leads to the best global answer. This property, known as Optimal Sub...
100.
[Tutorial] Tangents of a Polygon in O(log n) In one of the last stages of the 3rd Universal Cup, there was a not-so-nice problem (it required using fractions) that involved an algorithm for which I hadn't found a tutorial or much information on popular blogs. This approach was developed by me, and I appreciate any feedback on it or its implementation.
https://codeforces.me/gym/105657/problem/C
#### Parameters
- The polygon is convex
- The point is not strictly inside
#### What are the tangents to a polygon from a point?
The tangents of a polygon with respect to a point are the lines that pass through the point outside the polygon and touch the polygon at exactly one vertex or along one side, without crossing its interior.
<img src="/predownloaded/7a/2b/7a2bc71ba65fd9ebcf0df712893bfe96417c8dc6.png" style="width:350px; height:300px;" />
#### Why are these useful?
- Solve difficult problems
- Solve problems related to visibility or trajectory where the polygon cannot be crossed.
#### Algorithm
To descr...
101.
Interpolation of a multivariable polynomial, or how to guess a formula Hello, Codeforces. I wrote a prorgam using [this theorem](https://en.wikipedia.org/wiki/Combinatorial_Nullstellensatz?wprov=srpw1_1) for interpolation a function as a polynomial. At first, I will explain how does it work and then show some examples of using it.
Wikipedia does not provide one formula I need, so I will show it
<spoiler summary="Formula">
If there are now monomials with all exponents more or equal than our exponents, the coefficient with our monomial can be calculated by formula
</spoiler>
Code is quite long, but simple in use.
How to use program
------------------
At first, you need to set values of constants. N is the number of variables, MAX_DEG is the maximal exponent of a variable over all monomials. In `main` you need to fill 2 arrays: names contains the names of all variables, max_exp[i] is the maximal exponent of the i-th variable, or the upper_bound of its value.
Define...
add to the coefficient the value of fraction in this point (monomial).
102.
Tutorial: Codeforces formatting/markup # Tutorial: Codeforces formatting/markup
When writing [my first blog post](https://codeforces.me/blog/entry/104172) I grew frustrated because I couldn't find resources on how to format the post and what I can/can't use. So I decided to collect what I know in this blogpost, so this wouldn't be such a problem for other newbies in the future.
**This post has been written with my best knowledge. If something is incorrect please let me know!**
### Table of Contents
1. Markdown — general formatting
2. LaTeX (MathJax) — math and other special symbols
3. Codeforces specific features
4. Other useful resources
5. BONUS: Typing $ in your posts
## 1. Markdown — general formatting
#### Overview
When you are writing a post or a comment on codeforces, you are writing in a markup language called Markdown. You can [learn more about markdown and how it works here.](https://www.markdownguide.org/) It has its own easy syntax, for example if you want **bold ...
give us a fraction of 1/2. There are two ways to enter 'math mode' on
Codeforces:
103.
Segment Tree From The IMO Here's the problem (IMO 2013 Problem 1): Assume that $k$ and $n$ are two positive integers. Prove that there exist positive integers $m_1 , \dots , m_k$ such that $1+\frac{2^k-1}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_k}\right)$.
There is an inductive proof, which is generally the more popular solution among IMO contestants, but I would like to demonstrate a solution that relates this problem to a well-known data structure: the segment tree.
Think:
<spoiler summary="Spoiler 0">
How is this related to segtrees?
</spoiler>
<spoiler summary="Spoiler 1">
Could you reformulate the "fraction multiplication" into something that is more similar to something related to segtrees?
</spoiler>
<spoiler summary="Spoiler 2">
Maybe we could relate the ranges in a segtree to fractions of the form 1 + 1/m.
</spoiler>
<spoiler summary="Spoiler 3">
Yes, each thing on the RHS may be taken as ranges. But you need the range length (including start, but not e...
Could you reformulate the "fraction multiplication" into something, reformulate the "fraction multiplication" into something that is more similar
to something related, Let's try to turn the LHS fraction $\frac{n+2^k-1}{n}$ to a range $[n,
n+2^k-1]$. "Modify" our
104.
Why no floating point precision errors? I solved a problem recently using floating point arithmetic. I suspect the solution should not work for some test case because of floating point precision errors, but cannot find a case where it would fail. Moreover, the solution gets "Accepted" verdict.
Link to the submission (Codeforces Round #660 E): [submission:89366718]
The submission is an implementation of the Convex Hull Trick approach mentioned in the [editorial](https://codeforces.me/blog/entry/80828) of the problem.
If you look through the code, you will find that I have maintained forbidden ranges of cotangents of an angle and then iterate over the critical angles (i.e. extremeties of some range of forbidden angles, which are not forbidden themselves).
I suspect that `float(xr[j] - xl[i]) / (y[i] - y[j])` should return unequal values for some mathematically equal fractions (like $5/3$ and $15/9$) because of precision errors.
In such case, let's say there are two ranges $\[a, b\]$ and $\[c, d\]$ with $b = c$ ...
105.
Codeforces Round #124 — editorial [problem:197A]
If first player can't make first move (table is too small and plate doesn't fit it, i.e. $2r > min(a,b)$), second player wins.
Else first player wins. Winning strategy for first player: place first plate to the center of table. After that he symmetrically reflects moves of second player with respect to center of table. If second player has move, first player has symmetrical move, too. If not, first player won.
[problem:197B]
From math lessons we know, that only higher degrees of polinomials matter in this problem.
1. If denominator degree is larger than numenator degree, answer is "0/1".
2. If numenator degree is larger, answer is infinity. But what is sign of this infinity? To get it consider signs of highest degree factors of polinomials. If they are same, answer is positive infinity, else --- negative infinity.
3. If degrees of numenator and denominator are equal, answer is $\frac{a_0}{b_0}$. To get irreducible fraction, you should divide this numbers b...
irreducible fraction, you should divide this numbers by $gcd(a_0,b_0)$. And
don't forget that
Tutorial of Codeforces Round 124 (Div. 1)
Tutorial of Codeforces Round 124 (Div. 2)
106.
A simple application of O(nlogn) specific polynomial composition In Elegia's blog [How to composite (some) polynomials faster](https://codeforces.me/blog/entry/126124), we know how to compose some special power series in $\mathcal O(n\log n)$ time, especially for the quadratic rational fraction $(ax^2+bx+c)/(dx^2+ex+f)$ and the cubic polynomial $ax^3+bx^2+cx+d$. In this blog I will show how to use this method to calculate $\prod_{i=1}^n(x-g(i))$ in $\mathcal O(n\log n)$ time, where $g(x)$ is a quadratic rational fraction, written as $(ax^2+bx+c)/(dx^2+ex+f)$.
### Basic Knowledge
Let's review how to calculate $f_n(x):=\prod_{i=1}^n(x-i)$ in $\mathcal O(n\log n)$ time. We solve this problem by recursion.
If $n$ is even, assuming we have already computed $f_{n/2}$, then $f_n(x)=f_{n/2}(x)\cdot f_{n/2}(x-n/2)$, which could be calculated in $\mathcal O(n\log n)$ time.
If $n$ is odd, assuming we have already computed $f_{n-1}$, then $f_n(x)=f_{n-1}(x)\cdot (x-n)$, which could be calculated in $\mathcal O(n)$ time.
Hence, we know that th...
quadratic rational fraction, $h$ is any power series. The key is to find out
$\sum_{i=1}^n g(i)^j,1\le j, the quadratic rational fraction $(ax^2+bx+c)/(dx^2+ex+f)$ and the cubic
polynomial $ax^3+bx^2+cx+d
107.
N̶e̶e̶d̶ ̶h̶e̶l̶p̶: Selects K different columns from a 2xN matrix, maximizes the ratio of (sum selected top) to (sum selected bottom) #### Problem:
Given a $2*N$ matrix contains of positive integers with value not greater than $10^6$. Given an integer $K$.
Chooses $K$ column(s) from the matrix, call $P$ is the sum of all of the top integers from chosen columns, call $Q$ is the sum of all of the bottom integers from the chosen columns.
Your task is to maximizes $P/Q$ and print $P$ and $Q$ out in its reduced fraction form.
_Constraint:_ $1 \leq K \leq N \leq 5*10^4$
_Time limit:_ 1s
**Input:**
- First line contains: $N$, $K$
- Next $N$ lines contain two integers, first integer belongs in the top row of the matrix, second integer belongs in the bottom row. $i$-th line represents $i$-th column of the matrix.
**Output:**
- Two space-separated integers $P$ and $Q$.
**Example**
<spoiler summary="Input">
<pre class="prettyprint">3 2
3 1
1 2
1 1
</pre>
</spoiler>
<spoiler summary="Output">
<pre class="prettyprint">2 1
</pre>
</spoiler>
#### Attempts:
It was from our school...
Your task is to maximizes $P/Q$ and print $P$ and $Q$ out in its reduced
fraction form.
108.
Is the test of "Area of Two Circles' Intersection" correct? (--> YES!) **EDIT2:**
- I was wrong, and the test cases were correct.
- Added a section discussing my errors.
**EDIT1:**
- Changed the threshold of Taylor series from $x_\mathrm{th} = 0.001$ to $x_\mathrm{th} = 0.01$ (thanks to [user:Swistakk,2015-12-03])
- Fixed use of `Fraction` in Python: `Fraction(str)` instead of `Fraction(float)`
- No change in the outcome.
------
### TL;DR
[problem:600D] requires careful treatment of loss of significance, more than the geometry itself. <strike>The test is plagued by the numerical errors, and rejects "more accurate" solution.</strike> **EDIT2:** Solving this problem with `double` precision turned out very hard!
### Geometry
Let's review the geometry, first. We need three numbers $(r_1, r_2, d)$; where $d$ is the distance between two centers,
$$ d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}. $$
When two circles do not intersect, which is the case $d \geq r_1 + r_2$, the area of intersection is zero.
When one circle is c...
avoid the error. ($d$ is a floating point number but I still convert it into a
fraction as well.), - Fixed use of `Fraction` in Python: `Fraction(str)` instead of `Fraction
(float)`
109.
Video Editorial for Codeforces Round 1079 Div2 Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.
Thanks to [user:Shayan,2026-02-12]
### [2197A — Friendly Numbers](https://codeforces.me/contest/2197/problem/A)
<spoiler summary="Video">
<iframe width="800" height="450" src="https://www.youtube.com/embed/zx5Qk_3oPtk?start=166" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>
</spoiler>
### [2197B — Array and Permutation](https://codeforces.me/contest/2197/problem/B)
<spoiler summary="Video">
<iframe width="800" height="450" src="https://www.youtube.com/embed/zx5Qk_3oPtk?start=556" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web...
### [2197C — Game with a Fraction
](https://codeforces.me/contest/2197/problem/C)
110.
Pell's equation I first encountered Pell's equation when I was in 10th grade so I thought it was quite common. But alas, I cannot find a blog on Codeforces that talks about it, which makes me quite sad. So here, I will talk about it for a bit.
First, let me introduce the equation, since it would be hard to talk about it otherwise. It is the diophantine equation
$$x^2 - n y^2 = 1$$
where $n$ is a positive integer. Usually, we are given a positive integer $n$ and then we would be asked to find the smallest positive integer $x$ such that there exists a positive integer $y$ that satisfies the equation (or vice versa, but it doesn't matter). Usually, this minimal solution is called the fundamental solution.
It is easy to see that no fundamental solution exists whenever $n$ is a perfect square. However, it is not as easy to see that there is always a solution whenever $n$ is not a perfect square. This is true, but I will omit the proof since I haven't bothered myself to learn it. After learning this...
you truncate the continued fraction at the step before the last in a period
(yes, continued, fraction at the step before the last in a period (yes, continued fractions of
square roots are periodic
111.
An awesome list for competitive programming! This is a project I started from late January 2016.
My motive is that: Although there's fantastic information out there, I think they're still spread all over the place. Therefore, in my opinion it would probably be cool if there's an [awesome list](https://github.com/sindresorhus/awesome) for competitive programming! ( *It's now featured on the main list!* )
I'm actively updating the list here: [https://github.com/lnishan/awesome-competitive-programming](https://github.com/lnishan/awesome-competitive-programming)
# Awesome Competitive Programming [](https://github.com/sindresorhus/awesome)
A curated list of awesome `Competitive Programming`, `Algorithm` and `Data Structure` resources.
Created with a view to connecting people to information, this list below contains a complete collection of all the fantastic resources I've collected over the course of my 11...
a small fraction of the original site is translated into English, but Google
Translate would work
112.
Codeforces Beta Round #60: tutorial <b>Problem A</b><div><br></div><div><div>Fist, consider the case when all the numbers are non-zero. You can take a*c*e grams of sand, turn them into b*c*e grams of lead, and them turn into b*d*e grams of gold, and them turn into b*d*f grams of sand. If b*d*f > a*c*e, you can infinitely increase the amount of sand and consequently the amount of gold. Otherwise, if b*d*f <= a*c*e, it is impossible to get infinitely large amount of gold. The same is true when the fraction (a*c*e)/(b*d*f) has zero numerator only or zero denuminator only. Otherwise there is 0/0, and you have to check cases specially.</div><div><br></div><div>I explain, why I make this problem to be problem A.</div><div><br></div><div>1. Solution of the problem requires very little knowledge of programming (only "if"), so it was feasible for all participants.</div><div>2. Tricky cases really exist, but I hoped that "<span class="Apple-style-span" style="font-family: verdana, arial, sans-serif; font-siz...
amount of gold. The same is true when the fraction (a*c*e)/(b*d*f) has zero
numerator only or
Tutorial of Codeforces Beta Round 60
113.
[Tutorial] How to format a blog <i>This blog focuses more on the functions (which help you format a blog), not the tips and tricks.</i> <br>
Since many recent blogs are hurting my eyes (I'm talking to you, [user:MEGATRON_HACKER,2026-06-15]...), I decided to write a blog to share some tips and tricks about how to format a blog.
<b> This post has been written with my best knowledge. If something is incorrect please let me know! </b> <b style="color:white;font-size:5px"> I copied this sentence from [<b style="color:white;font-size:5px">this blog</b>](https://codeforces.me/blog/entry/104522)...</b> <br>
Here's a table of contents if you guys need it:
### <b>Table of Contents:</b>
<ol>
<li> <b>Codeforces specific features</b> </li>
<li> <b>Math</b> </li>
<li> <b>Emoji</b> </li>
<li> <b>Change font, font size, color, background color of text, and text's alignment</b> </li>
<li> <b>Tables</b></li>
<li> <b>YouTube videos</b> </li>
</ol>
<p style="font-size:0px"> This blog was written by ...
command. For example, `\frac{1}{2}` will be rendered as $\frac{1}{2}$. If you
want yourfraction to be
114.
Codeforces Round #814 (Div. 1, Div. 2) Editorial Sorry for not very good samples, and late editorial. It was our first round, so it was wary stressful for us, But we hope you liked the problems despite this!
[problem:1719A]
<spoiler summary="Hint 1">
Try to look at the parity of $n, m$.
</spoiler>
<spoiler summary="Hint 2">
The player who wins does not depend on player's strategy.
</spoiler>
<spoiler summary="Hint 3">
The only thing that the winning player depends on is the parity of $n, m$.
</spoiler>
<spoiler summary="Tutorial">
Note that the game will end only when the chip is in the upper right corner (otherwise you can move it $1$ square to the right or up). For all moves, the chip will move $n - 1$ to the right and $m - 1$ up, which means that the total length of all moves is $n + m - 2$ (the length of the move is how much the chip moved per turn). Since the length of any move is odd, then after any move of Burenka, the sum of the lengths will be odd, and after any move of Tonya is even. So we can find...
choose which pair of $b$ to choose for the $i$-th vertex of the first fraction
of the graph $a$. If we
Tutorial of Codeforces Round 814 (Div. 1)
Tutorial of Codeforces Round 814 (Div. 2)
115.
More on D-Finite Functions II: Problems After finishing this part, I found out some of them are not that related to D-Finite functions (especially for the last section), but in these problems, we still need some insight to deal with differential operators. So I'll keep them here.
## Sums involving powers
Let's consider the following problem of summation
$$ \sum_{0\leq n \leq M} f(n) \cdot n^k, $$
where $M$ can be finite or infinite. We want to separate a large class of $f$ such that such summation can be solved in $O(k)$.
You may already know some examples:
- For the constant function $f(n) = 1$, known as [662F](https://codeforces.me/problemset/problem/622/F), can be solved in linear time through Lagrange interpolation on consecutive sampling points.
- For the geometric series $f(n) = r^n$, you can find the [finite case](https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial) and [infinite case](https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomial_limit) (assume $|r| < 1$) in Libra...
solve this is through the partial fraction. - For the binomial case $f(n) =
\binom N n$, known as
116.
Avoid silly overflow mistakes taking modulo in C++ TL;DR This article features `Modular` class which can be conviniently used for modular arithmetic more "naturally".
#### Motivation
Recent round featured an interesting problem [problem:1081C] (if you plan to solve it, read this later). Combinatoric solution requires you to calculate:
$$
\displaystyle
\binom{n-1}{k}m \left( m-1 \right) ^{k} \mod 998244353
$$
Many contestants failed pretest because of missing modulo operation somewhere in code.
#### Solution
Many contestants use functions like `add(ll a, ll b)` or `mul(ll a , ll b)` which makes implementation somewhat clumsy.
I present you an alternate approach using `Modular` class.
---
~~~~~cpp
template <int MOD=998'244'353>
struct Modular {
int value;
static const int MOD_value = MOD;
Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
Modular(long long a, long long b) : value(0){ *this += a; *this /= b;}
Modular& operator+=(Modular const& b) {value += b.value; if ...
117.
Performance Ratings vs Ratings of Solvable Problems for the Recent GPT Models The GPT models have made great advancements in competitive programming recently. I saw from [user:Qingyu,2024-12-21]'s [blog](https://codeforces.net/blog/entry/137534) earlier that the new o3 model claims to achieve a 2727 performance rating.
However, I'm slightly uncertain of how this 'rating achieved' should be interpreted. There is very little detail publicly available on how the performance ratings are computed. The only available detail I could find regarding their benchmark methodology is the following quote from the ['reasoning with LLMs' blog](https://openai.com/index/learning-to-reason-with-llms/):
> Finally, we simulated competitive programming contests hosted by Codeforces to demonstrate this model’s coding skill. Our evaluations closely matched competition rules and allowed for 10 submissions.
This does not really offer any detailed computation methods. Given the limited details, I'm hypothesising that the LLM doesn't need to solve problems anywhere close to the 270...
also be allowed, since the -50 penalty takes a smaller fraction of the total
scores of the later
118.
Codeforces Round #940 and CodeCraft-23 (Div. 2) Editorial [problem:1957A]
==================
**Idea:** [user:keyurchd_11,2024-04-21]
**Problem Setting:** [user:shakr,2024-04-21] [user:lezirtin,2024-04-21]
**Editorial**: [user:shakr,2024-04-21] [user:TheRaja,2024-04-21]
There were a few solutions which passes pre-tests with the assumption that $a_i \leq n$. We apologize for the pre-tests on A not including this case.
<spoiler summary="Hint 1">
To create the most polygons, you should use as few sticks as possible per polygon. What polygon has the least number of sides?
</spoiler>
<spoiler summary="Solution">
[tutorial:1957A]
</spoiler>
<spoiler summary="Rate this problem">
-
Great Problem
-
Ok Problem
-
Bad Problem
-
Didn't solve
</spoiler>
<spoiler summary="C++ Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int> a(101, 0);...
$. Hence we can simplify the fraction by removing the denominator and replacing
the term $ j \times
Tutorial of Codeforces Round 940 (Div. 2) and CodeCraft-23
119.
Мощное свойство биномиальных коэффициентов, или как сдать задачу на формулу, если последнюю не хочется выводить? Привет всем!
Года два назад я решал задачу, в которой для сдачи требовалось вывести формулу, сворачивая суммы, ряды и делая кучу неприятных дел, на которые уходит много сил и энергии на контесте. Я тогда заинтересовался, а существует ли более простой способ вывести эту формулу, не делая почти никаких математических преобразований?
[cut]
Задолго до этого я наткнулся на [одно свойство биномиальных коэффициентов](https://en.wikipedia.org/wiki/Binomial_coefficient#Binomial_coefficients_as_a_basis_for_the_space_of_polynomials) в Википедии. Я естественно подумал, что это свойство довольно бесполезно, но, как оказалось, его можно применять для решения многих комбинаторных задач, в которых требуется вычислить формулу, задающуюся некоторым полиномом.
А теперь поставим общую задачу: пусть нам известны несколько значений, вычисленных в $k$ подряд идущих целых точках $x_i = i$ ($0 \leq i < k$), некоторой функции $f(x)$, являющейся многочленом. Требуется, зная эти точки, уметь находить...
просто реализовать, ведь придётся использовать реализацию рациональных чисел
для коэффициентов (Fraction
120.
NextTuring CP Indviduals on site final round 2026 — Official Editorial CodeForces Group Link: [https://codeforces.me/group/EP1lUFnsjA](https://codeforces.me/group/EP1lUFnsjA)
[Problem A](https://codeforces.me/group/EP1lUFnsjA/contest/688815/problem/A)
==================
<spoiler summary="Hint 1">
How many vowels are there?
</spoiler>
<spoiler summary="Hint 2">
odd*odd+even*odd=?
odd*odd+even*even=?
</spoiler>
<spoiler summary="Solution">
If n>5, we don't have enough vowels to give one to each row. Hence answer would be "NO"
If k is odd, odd number of rows each have an odd number of characters in them. Remaining rows have even number of characters. So, total number of distinct characters should be odd for the answer to be "YES". but we know that 26 is not odd. Hence, answer will be "NO"
If both the conditions "n>5" and "k is odd" are False, then it is guaranteed that n<=5 and k is even
We can first give one vowel to each of the row (remaining 26-n alphabets left)
Then, we can add one more character to n-k rows (remai...
this simplest form of fraction be $\frac{x}{y}$
121.
Analysis Codeforces Beta Round #64 <p><strong>Problem A.</strong><strong><br></strong></p><p>Let's define a half-filled square of size $k$ as an empty square of size $k$ after adding a cookie of the biggest posible size.<br></p>Notice, that if we add a cookie of the biggest possible size into the half-filled square of size $2^{n} \times 2^{n}$, it will be divided into three half-filled squares of size $2^{n-1} \times 2^{n-1}$ and one filled square. After performing the same actions with the three half-filled squares we will get nine half-filled squares of size $2^{n-2} \times 2^{n-2}$ and so on. It's easy to get the formula $f(n)=3*f(n-1)$, $f(0) = f(1) = 1$. $3^{n-1}$ (for $n > 0$) and $1$ (for $n = 0$).<br><p><strong> </strong><strong>Problem </strong><strong>B.</strong><strong><br></strong></p><p>It's obviously, that sentences should be added into the SMS greedily. Really, if we put the sentence into the new message, when it's possible to add into previous, the number of messages may be increased. The only thi...
Tutorial of Codeforces Beta Round 64
122.
Invitation to Code-MAT 2021 Hello codeforces!!!
**Mathematics and Computing Society (MACS) IIT BHU** is glad to invite you to our programming event **Code-MAT 2021**. The contest will take place on Codechef [15th April, 17:30 IST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Code-MAT&iso=20210415T1730&p1=1045&ah=2). You will be given 2 hours to solve six problems of varying difficulty which is bound to keep you on your toes.
**Contest link** : https://www.codechef.com/CDMT2021
The problem set has been prepared by [user:Test2311,2021-04-12] , [user:Delirious_Butter,2021-04-13] , [user:AK....,2021-04-13] and [user:TheBigBool,2021-04-12].
We would also like to appreciate [user:gaddopur_coder,2021-04-12] , [user:ShubhamAvasthi,2021-04-12] , [user:vivant,2021-04-12] , [user:akshat__1136,2021-04-12] and [user:sin_ha_rsh,2021-04-12] for testing the round and providing valuable feedback on the problems.
We have prizes worth **2000 INR** for IIT BHU Par...
- [IRREV (Irreducible fraction
)](https://discuss.codechef.com/t/irrev-editorial/88091)
123.
Faster Square Root Computation Using an Optimized Binary Search Hello there, welcome to my first Codeforces blog post! Today I’d like to share an educational — and frankly a fun observation — on optimizing the process of finding the square root of large integers using binary search. This may not be something you’d use in your everyday code (after all the built-in `sqrtll()` is hard to beat in speed), but it’s a neat mathematical trick that can literally save you seconds when processing many numbers.
Before we dive in, a huge thanks to [user:chromate00,2025-03-13]. An answer of mine getting hacked in one of his contests sparked this discovery.
---
## Aim
In a typical binary search algorithm for computing the integer square root of a number `S`, we initialize the search range with:
- `low = 0`
- `high = S`
This approach finds the square root in **O(log(S))** iterations. But if we have to compute square roots for too many numbers (like $10^8$), it can become laggy. However, if we can choose `low` and `high` more intelligently based ...
// high = 1 << ceil(msb_Val/2 + fraction) // fraction part can never be equal
to, integer // high = 1 << ceil(msb_Val/2 + fraction) // fraction part can never be, 5. **Scaling the Fraction:** Dividing the fractional part by a constant `k`
(greater than or
124.
CarYon — An OI/ACM Contest Test Case Generator based on C++ # CarYon: An OI/ACM Contest Test Data Generator based on C++
     
# Front
Have you ever encountered the following problems when holding a self-contained OI match:
- Want to quickly produce a paragraph of text?
- Want to quickly perform mathematical operations to generate data?
- Want to generate test data one by one without using freopen?
- Want to generate a set of random data or series?
- Quickly generate data to match the two programs?
Then, you can use CarYon and C++ to quickly generate data. Previously supported features are:
- Randomly generate a chapter, some words, some words
- Get out of the limitation of RAND_MA...
125.
Still don't get the "You should compute P⋅Q−1 modulo 109+7, where Q−1 denotes the multiplicative inverse of Q modulo 109+7." Working with fractions usually we get a hint like
"You should compute P⋅Q−1 modulo 109+7, where Q−1 denotes the multiplicative inverse of Q modulo 109+7."
So, I more (or less) understood what that means.
I can express, say 1/5 by the number 400000003.
I can calculate that number using https://www.geeksforgeeks.org/fermats-little-theorem/ implemented by some code I found somewhere (see below).
BUT: How do I add (and/or multiply) fractions with huge values?
i.e. how to calculate and express something like this:
Let E=10e9+7
Then, how to express: ((E+1) / (E+2)) + ((E+3) / (E+4))
Any hint or link to an understandable explenation would be really helpfull.
Thanks.
The code I use so far, based on that fermat thing:
'
class Inv {
companion object {
val defaultMod = 1000000007L
var MOD = defaultMod
fun toPower(a: Long, p: Long, mod: Long = MOD): Long {
var a = a
var p = p
...
126.
Unofficial Editorial — Back to School '24 Contest hosted on DMOJ [https://dmoj.ca/contest/bts24](https://dmoj.ca/contest/bts24)
### [P1 — Kicking](https://dmoj.ca/problem/bts24p1)
<spoiler>
You can solve each row independently of each other. Using window sums, you can count the number of `A` or `B` in any contiguous section of $K$ cells, and thus detect whether any player has an opposing player in front of them.
Time complexity: $O(NM)$
</spoiler>
### [P2 — Cheating](https://dmoj.ca/problem/bts24p2)
<spoiler>
The key observation is that you can think of the students as a queue standing from $1$ to $M$. The students that answer the $i$-th question are always the first $B_i$ students in front of the queue, then they move to the back of the queue in the same order that they were in before. We could prove this by induction:
- To avoid having to consider tie-breaking, we let each student $j$ start with a score of $j \cdot \varepsilon$, where $\varepsilon$ is a really small fraction.
- Let $P(i)$ re...
\varepsilon$, where $\varepsilon$ is a really small fraction. - Let $P(i)$
represent the predicate
127.
Help: Geometry problem. Find colinear points. Prove this solution is wrong. DISCLAIMER: I really want to understand why this solution (which I think is quite reasonable) is wrong. If this is a nonsensical solution, please say so. I am not looking for a AC solution, I'd like to prove that this one is wrong, but i've been unable to do so..
____
**Problem Statement**
The statement is from [timus 1588 — Jamaica](http://acm.timus.ru/problem.aspx?space=1&num=1588):
**Each two cities are to be connected by a road going along a straight line**. One road may connect several cities if they lie on the same straight line. Jamaican economists are sure that the new network will minimize transportation expenses. In order to estimate the cost of the project, it is required to **determine the total length of the roads to be constructed**, and this is the job for Andrey.
____
**Solution to be proven wrong**
So, we have N points and we want the sum of a subset of the lines.
Consider all point combinations, this give all lines. A line is described by...
import sqrt, floor from fractions import Fraction, ~~~~~ from fractions import Fraction # available since python 2.6 . Irreducible
fractions, very
128.
0-1 Knapsack **Knapsack** is a standard problem of dp (Dynamic programming) in which you need to pack a set of items, with given values and sizes (such as weights or volumes), into a container with a maximum capacity.
Identification
------------------
You have a container with a maximum capacity given. and given two arrays one array contains **value** and other containing **weight/limits** respectively. You have to find optimal value you can obtain within the bag's size limit.
and we have a choice along arrays.
Knapsack can be divided into three sub problem.
1. **Fractional Knapsack** :- Easily solved using Greedy. In this problem you have given all thing that kanpsack have but you can use value in fraction means if you have given a weight $4kg$ with value of $10$ then we can use $1kg$ with a weight of $2.5$.
2. **0-1 Knapsack** :- In this we can use one weight only one time also we can't break into pices. we have to use dp to find solution of this type of problem as we have a choice ...
that kanpsack have but you can use value in fraction means if you have given a
weight $4kg$ with
129.
Coin Changing (Greedy Approach) Here are four complete C++ programs, each taking input from the user.
## 1. Coin Changing (Dynamic Programming)
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cout << "Enter number of coin denominations: ";
cin >> n;
vector<int> coins(n);
cout << "Enter the coin denominations: ";
for (int i = 0; i < n; i++) cin >> coins[i];
int amount;
cout << "Enter the target amount: ";
cin >> amount;
vector<int> dp(amount + 1, INT_MAX);
vector<int> lastCoin(amount + 1, -1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < n; j++) {
if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
if (dp[i - coins[j]] + 1 < dp[i]) {
dp[i] = dp[i - coins[j]] + 1;
lastCoin[i] = coins[j];
}
}
}
}
if (dp[amount] == INT_MAX) {
cout << "It is not possible ...
cout << "\nItems selected (fraction taken):\n"; for (int i = 0; i < n &&
remainingCapacity > 0
130.
Notes on Codeforces Beta Round #62, A, B, C (Backtracing), D [problem:68A]
This problem can be solved by direct implementation as it requires. The main issue involved is the generation of all permutations for some given sequence. As the problem guarantees that all the given integers are different, a simple recursive backtracing algorithm is sufficient. Completing this, we can count the number of integers that satisfy the conditions.
[problem:68B]
This is a very nice problem to practice binary search. Different from the conventional binary search based on index, this one has to deal with "float type", and thus the loop should be terminated by limiting the number of search.
We can directly search the required answer. During each search, we enumerate all the elements and calculate two results, denoted as E_out and E_in as follows. If the element is no less than the current answer, then we add the difference to E_out; otherwise we add the difference to E_in. Note that here the difference is always larger than or equal to 0. Then, we com...
Although the complete binary tree will have about 2^30 nodes, only a small
fraction of them will be
131.
I will be using Ruby along with two other languages on today's Round (UPD: with results!) For the few weeks so far, I have been practicing ruby on multiple platforms (Atcoder and BOJ, solved about ~150 in total?). Now I feel that I am fluent enough with the language, so I will be using Ruby, along with Python 3 and C++, on todays Round (the Div.3). After that, I would like to share my honest thoughts about using Ruby in CP with others as well. I am eager to see how well Ruby can perform on Codeforces today!
P.S. Yes, I am writing this blog also for the ignorant people who might argue about this saying that I am cheating again, why can't they understand that one person can understand more than 2~3 languages? (Yes, I could've used Ruby, Java, C++, Python, and JS all in the same contest. I simply don't because there's no merit for that.)
**UPD: The round has concluded. I solved 4 tasks in total, 3 with Ruby and 1 with Python, and then tried 2 more tasks with C++. (Could not come up with the idea on E, could not come up with the edge cases on G. This is not to argue with ...
132.
Codeforces Beta Round #30. Tutorial for problem A <h1>Tutorial for problem "A. Accounting"</h1><h3>First solution: naive brute</h3><p>Let's brute all possible values of $X$, and check each of them. It's easy to understand, that $X$ will be constrained in the same limits as values $A$ and $B$, that is, from -1000 to 1000 inclusive (obviously, there exists a test for each such $X$, so we can't decrease these limits).</p><p>When we have some fixed value of $X$, we check it simply by multiplying $A$ by $X$ $n$ times. But, you should be careful with possible integer (and even 64-bit integer :) ) overflow. For example, you should stop multiplying by $X$ if the currect result exceeds 1000 by absolute value already.</p><h3>Second solution: formula</h3><p>It's easy to note, that if solution exists, then it is $n$-th root from $|B|/|A|$ fraction, with changed sign if $A$ and $B$ have different signs and if $n$ is odd (if $n$ is even, then no solution exists). That's why we could just use pow() function (or some analog in your language) to calcu...
root from $|B|/|A|$ fraction, with changed sign if $A$ and $B$ have different
signs and if $n$ is odd
Tutorial of Codeforces Beta Round 30 (Codeforces format)
133.
Algorithms Dead Episode 1: Divsion Under Mod! Algorithms Dead Episode 1: Division Under Mod
==================
Do you blindly do operations under mod without knowing why they work? Does it scare you when a problem asks you do print something mod a big number? If so, you should watch [Episode 1 of Algorithms Dead!](https://youtu.be/KfTcd0dg0DI)
In it, I talk about why mod operations (addition/subtraction/multiplication) are allowed, why mod inverses work, and what things are safe to do when you store fractions as $p*q^{-1}$.
134.
Why does this work? Somehow I managed to solve [problem:901B] however I don't know why my solution works. My idea was to pick two random polynomials of degrees n and n-1 check how many steps it takes to find the gcd and return the polynomials if the answer is n. However doing the gcd over $\mathbb{Q}$ is a pain because of fractions. If you try to avoid them by multiplication by denominators things overflow pretty quickly.
So I decided to pick a prime and do gcds over the finite field $F_{p}$. The strange thing is with a medium sized prime like 1009 the algorithm took more steps over this field than over $\mathbb{Q}$. Then I tried using the prime 43 just to see what would happen, since it worked on the case where 1009 gave an incorrect answer. Surprisingly using 43 worked for all the cases. Anyone know of a special relationship between the number of steps the Euclidean algorithm for polynomials takes over $\mathbb{Q}$ and $F_{p}$ for a given prime $p$?
<spoiler summary="code">
~~~~~
#include <bits...
135.
Word Ladder: For 1e5 Queries on a Static Dictionary # Word Ladder With 1e5 Queries — Efficient Approaches and Analysis
Hello ,
During learning graphs, I encountered a famous and classic problem *Word Ladder* problem. Given a beginWord and endWord, find the minimum number of single-character transformations, where each intermediate word must be from a given list. Given all words are of the same length.
This shows up on LeetCode, GFG, interviews, everywhere.
But almost every version of the problem is single-query.
You solve it once and move on.
Now I want to discuss for a scenario where the dictionary is fixed and you need to answer queries in range of **1e5**.
**N ≤ 5000 words**
**L ≤ 10 (word length)**
**Q ≤ 100000 queries**
This completely changes the problem.
The typical BFS solution (where we generate neighbours (26\*L) at each stage and check whether they are in the dictionary or not and proceed) became far too slow.
This article explores that space in depth and shows efficient techniques dependin...
fraction of the dictionary.
136.
[Amateur Selfmade] Codeforces Round 1028 (Div. 2) Editorial for ABC > Read before:
>
> This blog should be just taken as a witness of my progressions as well as ideas to inspire readers and will inevitably feature bad-looking code styles or non-best solutions. Better solutions to problems mentioned in the blog are welcome in your readers' comments.
>
> All codes in this blog can be compiled in C++.
Hello, Codeforces!
The 4-year-struggle eventually got paid off when [contest:2116] on [contest_time:2116] had made me a <span style="color:green; font-weight: bold">pupil</span> — firmly hope that the <span style="color:gray; font-weight: bold">newbie</span> age won't return later on!
The blog is a self-made editorial on ideas and codes for the round's first 3 problems. I do hope that this can inspire you as readers.
_<s style="color:#ddd">Jesus I publish this blog minutes later than the official one</s>_
### [problem:2116A]
<spoiler summary = "Ideas">
It can be noted that **knights of the two players in the duel are the only a...
/** * @brief Fast Power. If a great number modulo is asked for a fraction x/y,
use `((fastPow(y
137.
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...
138.
C++ BigInt and BigFloat. Hello Codeforces!!
A few days ago, I wrote a code for BigInt and BigFloat classes and i would like to share it with you for feedback and improvement.
For the code Press [here](http://ideone.com/4yUr8Q).
Note: My BigFloat class stores numbers as a numerator and denominator to efficiently represent fractions like (1/3) without wasting data.
You can use functions like floor(object, n), ceil(object, n), or round(object, n) to extract the first n decimal places or convert the object to a string with a specified precision using str(n).
I've also implemented all comparison operations for BigFloat objects.
Note: The modulus operation for BigFloat currently calculates the modular inverse of the number. While this is interesting, you might also consider offering standard modulus behavior for users.
The Important Operations is
Multiplication: O((n + m) * log(n + m)) using FFT (Fast Fourier Transform). However, for small values of m, O(n * m) might be faster due to lower cons...
139.
Question about convex hull trick. Hello all,
I have tried googling this a lot but can't find a good solution. So any help will be greatly appreciated.
today, when I was doing the NOI, I came across a question which required me to use the convex hull trick. This is usually quite standard and easy to implement except for one thing: gradients of the lines can be a fraction. Let me explain:
The "line" that I am talking about isn't really a line. An example would be y = [mx] + c, where [x] means the largest integer small than or equal to x. (yes i know that it's not the right symbol but idk how to write mathematical symbols. Sorry for the inconvenience). If you plug this into desmos, it looks like a staircase. But i'm pretty sure that I can just use the line y = mx + c because if a certain line y = mx + c is minimum at a certain x then it will also be minimum when you take the floor. I have just explained this as maybe there is a different method for this kind of line, so if there is please let me know. Note that...
think using a fraction is correct as when you use fractions, the denominator
can get quite large
140.
[Video + Contest]: Contribution Technique involving linear functions ft CF Edu
188F Sum of Fractions
[Video + Contest]: Contribution Technique involving linear functions ft CF Edu 188F Sum of Fractions I created a video editorial for problem [F. Sum of Fractions](https://codeforces.me/contest/2204/problem/F) from **Educational Codeforces Round 188 (Rated for Div. 2)**
The video starts with a bruteforce approach $O(N^4)$, and then subsequently optimizes it to $O(N^3 \cdot Log(N))$, then to $O(N^3)$, followed by 2 versions of $O(N^2 \cdot Log(N))$, and finally the intended $N \cdot Log(N))$ solution (ignoring the log factor from modular divison).
Here is the video link https://youtu.be/8ixZezwq_20?si=i3ChK6zAEZKf6nZG
I also curated some practice problems and created easy version of problem F so that you can submit to verify the correctness of your slower solutions. You can find the contest here https://codeforces.me/group/7Dn3ObOpau/contest/537569 (Note, some problems are already added, working on the remaining ones, check back after a couple of hours).
The problems are untested, if you see any issues, do let me know.
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/03/2026 23:40:35 (h1).
Desktop version, switch to mobile version.
Supported by
