have attached my template for each topic. You may not call it a template
because some of them don't, I have attached my template for each topic. You may not call it a template
because some of them
→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
call
Last visit:
7 years ago
Registered:
7 years ago
2.
The Ultimate Topic List (with Resources, Problems and Templates) This post took $4$ years to make. And this is the most significant thing that I have ever shared in my whole life.
#### Story
Hi, I have been doing CP for like $4$ years and from the very beginning what I have been feeling is a need for a comprehensive topic list that will contain all sorts of topics from easy to advanced with corresponding tutorials, problem lists and templates so that I wouldn't have to look at different sites, from here to there. So what do you do when you think something is missing from the world? Yeah, you create that thing! So here I am, sharing the ultimate topic list that you will need in CP.
When I say that it took me $4$ years to make it, I genuinely mean it. I have been collecting them from the inception of my CP journey and yesterday I thought that it got its almost complete shape. You may not imagine the sheer excitement hidden under each of the characters of this post.
#### Payment
You can pay me just by upvoting this blog and by being a bet...
3.
Codeforces Round #810 Editorial Sorry for the late editorial. May this editorial help you. If you have questions, feel free to ask.
[problem:1711A]
<spoiler summary="hint1.">
The minimal weight is at least $1$ since $1$ divides any integer (so $1$ divides $p_1$).
</spoiler>
<spoiler summary="solution">
Since $k+1$ does not divide $k$, a permutation with weight equal to $1$ is: $[n,1,2,\cdots,n-1]$.
</spoiler>
<spoiler summary="code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
void work()
{
int n;
cin>>n;
cout<<n<<' ';
for (int i=1;i<n;i++)
cout<<i<<' ';
cout<<endl;
}
int main()
{
int casenum=1;
cin>>casenum;
for (int testcase=1;testcase<=casenum;testcase++)
work();
return 0;
}
~~~~~
</spoiler>
[problem:1711B]
<spoiler summary="hint1.">
See the party as a graph.
</spoiler>
<spoiler summary="hint2.">
Divide the vertices into two categories according to their degrees' parity.
</spoiler>
<spoiler summary="solution">
Let's consider ...
Let's call position $j$ a key position if it is the center position, rain that, if erase, makes it valid? Let's call position, Supposing $[L_x,R_y]$ consist of $k+2$ connected components now, let's call
them $[l_0,r_0],[l_1, call it $I$), so does a row. Let's call a column white if only white cells of
it are in $I$, otherwise
Tutorial of Codeforces Round 810 (Div. 1)
Tutorial of Codeforces Round 810 (Div. 2)
4.
I don't want this to get normalized I don't think comments like "you use X in model solution, author, are you an idiot?", "f**k you and your problems, they are shit" and such should be normal on Codeforces, especially when written by someone high-rated and/or respected in the community. I also don't think this kind of behavior should be normal towards regular users.
I know that sometimes contests can be frustrating. Sometimes it is the participant's fault, sometimes it is the problemsetter's fault, sometimes it just happens without anyone being guilty of that. And I understand that in some cases, the criticism the author receives is fair and well-deserved.
But there is a fine line between criticism, saying that you didn't like the problems, and hurling insults against the author. The former two are acceptable (and sometimes even needed, because authors have to improve and learn from their mistakes); the latter one, in my opinion, should not be acceptable.
It's not like we can ever get rid of offense and hatred ...
I've used you as an example made you feel awful, or made some other people call
you out — I am, awful, or made some other people call you out — I am terribly sorry.
5.
My opinion on how to practice competitive programming I'm not very often replying to questions about how to practice, but as I'm getting enough of them (and I've just seen another blog about practicing) let me tell you about it.
Of course, every time when you ask someone good about how to practice, he/she will reply to you to "solve a lot of problems" and that's true, there's no other way. Anyway, I've thought about it and actually I'm able to tell a bit more. I know some people, I've seen many people practicing (including me) and I have an opinion.
Many people practice in some organized way. High schools organize IOI/OI training contests every Saturday, universities organize ICPC training contests once a week, people try by their own to solve three problems each day, websites host rounds and so on. Here's a secret: it's a sh*t. Yep, that's true. If you want to be really good and to make it happen you compete in a training once a week, you do it only to be able to make excuses "but I'm training so hard" when you see no progress.
...
6.
I Love CF I miss the old CF, Anton rounds cold CF
Textbook sized blogs CF, no cheater blogs CF
I hate the new CF, the captcha hell CF
No Div 1s scheduled CF, just endless Div 4s CF
I miss the sweet CF, debug till sleep CF
I gotta say pre-GPT I’d like to meet CF
See we invented CF, it wasn't any CF
And now I look and look around just AI cheaters CF
I used to love CF, I used to love CF
I even made the rounds, I thought I was CF
What if CF made a blog about CF
Called “I Miss the Old CF," man that would be so CF
That’s all it was CF, we still love CF
And I love you like CF loves CF
7.
Codeforces Round #635 _Riichi...Tsumo! 2 han 2000 points!_
Hi! Have you ever heard of the game called _Mahjong Soul_? It is a Japanese Mahjong game that is famous for the adorable characters.
We are excited to invite you to take part in [Codeforces Round #635](https://codeforces.me/contests/1336,1337), where you can help the characters in trouble. This round will be held on [contest_time:1336]. Most importantly, it is **rated** for both divisions!
Each division will be given **6 problems** and you will have **2.5 hours** to solve them. An interactive problem may be found in this round. If you are not familiar with interactive problems, you can learn about them [here](https://codeforces.me/blog/entry/45307).
The problems were prepared by [user:EternalAlexander,2020-04-14], [user:ustze,2020-04-14] and me [user:Sooke,2020-04-14].
We sincerely thank [user:isaf27,2020-04-14] for reviewing and coordinating the round, and ...
Announcement of Codeforces Round 635 (Div. 1)
Announcement of Codeforces Round 635 (Div. 2)
8.
Testing Round 20 [Communication Problems] Hello Codeforces.
We are introducing a new type of problem which may appear in future Codeforces rounds, called Communication problems!
In these problems, your program would be ran twice, with different input and output formats between the runs. All variables stored in the memory will be lost between runs. However, the information given to you on the first run may be important to you for completing the second run correctly. Therefore, one of the key challenges in these types of problems would be to find a way to use the limited amount of output you are given in the first run to communicate information to the second run. Below shows a flowchart.
<center>
<br/>
<img src="https://i.ibb.co/JWMFpyfY/a-1.png" alt="2025-09-06-12-40-07" border="0" />
<br/>
Flowchart for communication problems
</center>
In these problems, time and memory limits for both runs would be kept separately. For example, if a problem has a time limit of $2$ seconds, you will only get the Time Limit E...
Announcement of Testing Round 20 (Unrated, Communication Problems)
9.
Codeforces: Updates in rating and rounds <img src="/predownloaded/21/a3/21a33b497ee8a34a678befc3f79745eb69a9cf07.png" style="float:right; margin: 0 1em 1em 1em;"/>
Hello, Codeforces!
It's time for news. I hope you will enjoy!
* We reduce the rating bound for the orange color. Thus, now the orange rating (and the _Master_ title) will start from 2100 rating units.
* The lower bound of the rating for _legendary grandmasters_ is increased to 3000 rating units. Thus, right now in the community, 14 participants meet this requirement. Real legends!
* For rounds like "Div. 2 Only" the upper bound of the rating for official participation is increased. Now everyone whose rating is less than 2100 (i.e., before _masters_) will be able to register for such rounds to participate officially, their rating will be updated based on the results of the round. We do not plan to increase the complexity of Div. 2 rounds. Practice shows that the problems of such rounds are interesting and useful for participants "below the orange".
...
10.
Linear Recurrence and Berlekamp-Massey Algorithm **#IjustWantContribution**
It seems there isn't any blog about Berlekamp-Massey Algorithm around here, so I decided to go on a try. :P
Acknowledgement: Hats off to matthew99 for introducing this algorithm.
#### What is 'linear recurrence'?
Assuming there is a (probably infinity) sequence $a_0,a_1...a_{n-1}$, we call this sequence satisfies a linear recurrence relation $p_1,p_2...p_m$, iff $\forall i \geq m,~a_i=\sum_{j=1}^m a_{i-j}p_j$. (Obviously, if $m\geq n$ any $p$ can do :P)
#### How to calculate k-th term of a linear recurrence?
For a polynomial $f(x)=\sum_{i=0}^{t} c_ix^i$, we define $G(f)=\sum_{i=0}^{t} c_ia_i$.
Obviously $G$ satisfies $G(f)\pm G(g) =G(f \pm g)$.
Because $a_i=\sum_{j=1}^m a_{i-j}p_j$, if we let $f(x)=x^m-\sum_{j=1}^m x^{m-j}p_j$, then $G(f)=0$. Also $G(fx),G(fx^2)...=0$. So $G(fg)=0$ (g is any polynomial).
What we want is $G(x^k)$. Because $G(f\lfloor x^k/f\rfloor)=0$, then $G(x^k)=G(x^k \bmod f)$.
[cut]
We can calculate $x^k \b...
) sequence $a_0,a_1...a_{n-1}$, we call this sequence satisfies a linear
recurrence relation $p_1,p_2...p_m, Assuming there is a (probably infinity) sequence $a_0,a_1...a_{n-1}$, we call
this sequence
11.
Please try to be more positive in your feedback on the rounds. Hi, a few disclaimers first.
1. I work as a coordinator on CF, but this blog is solely my initiative (I didn't tell anyone from CF about it).
2. I was a few times in the author role, so I think that I have the right to speak on behalf of both authors and coordinators. Obviously, it doesn't mean that all authors/coordinators think the same, but (based on discussion with some people) I think that my opinion is not unpopular.
Main point of this blog — I feel like our community is becoming much more aggressive towards any things (some of which I can't even call issues) that they don't like during the round. I don't think it's a good direction, and I think it can decrease the motivation of authors & coordinators to do more rounds.
Now I will explain why I think so.
Obviously, you might guess that this blog was inspired by yesterday's round, but also a few recent ones too (for instance, CF 1069, CF 1058).
The first thing that any person will see on the home page now is that...
much more aggressive towards any things (some of which I can't even call
issues) that they don't, things (some of which I can't even call issues) that they don't like during
the round. I don't think
12.
[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...
graphs on $n$ vertices (call the count $c_{n}$ and EGF $C(x)$). However this
is easy, since each, graphs on $n$ vertices is $\displaystyle\sum_{k \ge 0}\binom{n}{k}2^{k(n-k)}$.
Call this number $a_, )}$. Call this number $a_{n}$ and its EGF as $A(x)$. The next step is to relate
the number of colored, Let us return to our problem. Call a cycle type $a$ good if $a_{j}=0$ for all
perfect squares $j
13.
Corruption, Cheating at ICPC Yinchuan This blog is about Corruption and Cheating at ICPC YinchuanRegional. ICPC Yinchuan Regional is one of the ICPC regional contests for students competing in the geographic area of Asia East Continent.
I. Background: General Info
------------------
Ningxia Institute of Science of Technology, or NXIST is a higher education institute in China. Since 2019, NXIST has held two regional contests. The and both were considered by many participants as jokes, yet until today participants are unaware of the NXIST's extent of evil.
Zhihu is a Chinese website similar to Quora, and I will refer to this website for information.
II. Background: Before 2021
------------------
Regional competitions in China consists of two stages: The online selection contest and the onsite regional contest. As there are many contestants in China, the online contest is considered serious and rules are usually strictly enforced, with entire universities where some participant cheats disqualified from attend...
14.
Codeforces: Results of 2023 [Annual Report] Hello, Codeforces.
Let's recall 2023, shall we?
In this post, I want to summarize this year. You know, a lot of terrible things happen in the world, and personally, this year was the hardest and most sorrowful for me. But today, we'll remember something else. We'll remember what this year was like for Codeforces.
Recently, Codeforces turned 14 years old. Not bad, right? And for many years now, when asked "What is Codeforces?" the first thing I say is — it's a community!
[cut]<br/>
#### Personal Thanks!
On behalf of the community (and myself), I say thank you to everyone who tries, helps, and makes efforts to keep the community alive.
Thank you to the developers! Although I continue to engage in development and other technical activities, I'm glad that these guys made an effort and improved the platform: [user:geranazavr555,2024-02-04], [user:unreal.eugene,2024-02-04], [user:vbandurin,2024-02-04], [user:ChurakovaAlexandra,2024-02-04], [user:medvezhonokok,2024-02-04]...
], [user:Alexdat2000,2024-02-04]. But we are grateful to all authors and call
on you not to stop this activity, ]. But we are grateful to all authors and call on you not to stop this activity!
15.
On AI ruining "solving math problems with computer" You all went crazy.
Instead of arguing with every opinion separately, I just want to ask one question: Why are you doing competitive programming? Is it to get to 1600 rating and put it on the resume? If so, please use AI, cheat, and do everything possible to get to 1600 as soon as possible and get the f**k out of this platform. And if you are (not) a normal person and do competitive programming because it is fun to solve problems, do you think it is fun to copy the problem statement into an AI model prompt and then copy the code it spews to submit? And why do you assume that everyone else will do that if there will be such an opportunity? The same goes for cheaters. Yes, some people do not do this as a sport, for fun. Why do you care?
I do think that AI is ruining competitive programming. By proxy. And that proxy is all of you who are running around yelling "We will all die, somebody do something about AI". I have seen a couple of comments saying "authors/coordinators must make s...
div2A ever just because "a machine can guess it"? I hope this can be a wake-up
call. A chance to, I hope this can be a wake-up call. A chance to remember that this was supposed
to be a fun activity
16.
New: Diagnostics of Solutions in C++ <img src = "/predownloaded/b5/d2/b5d246ffc32dfe82c3cbac77d1898c5fcb62fa57.jpg" style = "float: right; margin: 0 1em 1em 1em;"/>
Hello!
I am pleased to report that two rounds of Codeforces have gone quite well in terms of the work of Codeforces, I am very glad about it. These <s>days</s> nights I spent in a profiler, fixing the code, researching the settings of MariaDB.
In addition, I managed to allocate several hours on Sunday (to be honest, until Monday morning) to finish the long-planned innovation.
Meet, diagnostics of solutions in C++!
Many Codeforces visitors are already tired of the questions of less experienced participants: "Why does my solution not work on some test on the Codeforces servers, if I locally launch it and it works correctly? You have the wrong compiler/servers!" In 99% of cases this is an example of <a href ="https://en.wikipedia.org/wiki/Undefined_behavior">undefined behavior</a> in a program. In other words, the program contains mistakes that, du...
17.
Giving negative feedback to contests in comments //This is a short post motivated by the comment section of the last Div2 round (and of several rounds before)
Every problemsetter tries to make his contest as good as possible, and is upset when something goes wrong. Most problemsetters don't set contests for money, the payments are not worth the time and efforts spent on coming up with problems, preparing them, and hosting the contest. The most rewarding thing in this process in not the money, it's to see contestants enjoying your problems.
That's why feedback is so important. If the comment section is filled with comments praising the contest, setter will most likely want to come back with another contest, and if it's filled with hate and offenses, it's possible that setter will just give up on problemsetting and won't want to host another round.
This means two things.
First, if you liked the round, or some particular problem, why not to write a comment about it? I am sure that most setters would really appreciate it, a...
these comments, as I don't want to call anyone out, and I myself sometimes
left not very cool comments, to call anyone out, and I myself sometimes left not very cool comments., try to not use them as an opportunity to call the author a stupid moron. It's
better to tell what
18.
How to practice Competitive Programming [Um_nik version] CP is about solving problems fast. And as absurd as it may sound, I believe that <span style="color:blue">SOLVE</span> and <span style="color:red">FAST</span> are very different and almost independent parts, and you need to practice them separately.
Let’s look at some <span style="color:red">contest</span>, like a CodeForces round. For the sake of simplicity let’s assume that every problem has some *difficulty*, which is a numerical value denoting how hard it is, bigger values correspond to harder problems (it is not true, but it is an ok-ish approximation, at least if we consider subjective difficulty for a fixed person). Contests are made for a wide range of participants, and problemsetters strive to make contests interesting for a wide range of participants, which means having a *smooth difficulty gradient*. Well... as smooth as it is possible with 5-6 problems.
<spoiler summary="Graph 1">
.
## Stop caring about the rating
Unless there are prizes involved, your position in the standings makes no difference. I can feel awful after winning a contest if I know that I could solve one more problem. Or I can feel OK losing a bunch of rating points knowing that I solved everything I could. Because rating is just a number. It is highly volatile and it depends on other people, not only on your skill. But solving problems is totally up to you. And you should evaluate yourself not based on some random metric, but on your honest feeling whether you performed up to your expectations. Your sense of self should be under your control, don't get hung up on some imaginary value, you cannot reduce your progress to a single number.
## Don't use more than one account
Rating is just a number. Do not be afraid to lose your colour. You’ll get it back in no t...
20.
On Problems vs. Questions in Competitive Programming: My solution _TL;DR: The most reasonable solution to the problems vs. questions debate is to use none of the currently accepted terms._
As we have seen many times, particularly over the past few days, the task of assigning a label to the activities we perform as competitive programmers is a bigger problem than one might think at first. Time and time again we have seen people questioning what we should call our activities, often to the point of eliciting some rather harsh responses.
To give some context to this discussion, I will focus on two of the terms that members of the community have adopted over the years, _problems_ and _questions_. (Sorry task lovers! You have some fine points for sure, we frequently talk about subtasks rather than subproblems or subquestions after all :P). All quotations here are posted anonymously, but if you want to claim ownership of one of them or have one removed, just tell me. If you are familiar with the arguments, feel free to skip to the final section of the...
first. Time and time again we have seen people questioning what we should call
our activities, often to, rather call it a solution than an answer., than one might think at first. Time and time again we have seen people
questioning what we shouldcall
21.
[Tutorial] Collection of little techniques #### Introduction
There are a number of "small" algorithms and facts that come up again and again in problems. I feel like there I have had to explain them many times, partly because there are no blogs about them. On the other hand, writing a blog about them is also weird because there is not that much to be said. To settle these things "once and for all", I decided to write my own list about about common "small tricks" that don't really warrant a full tutorial because they can be adequately explained in a paragraph or two and there often isn't really anything to add except for padding.
This blog is partly inspired by [user:adamant,2022-03-15]'s [blog](48417) from a few years ago. At first, I wanted to mimic adamant's blog structure exactly, but I found myself wanting to write longer paragraphs and using just bolded sentences as section headers got messy. Still, each section is short enough that it would not make much sense to write separate blogs about each of these things.
A...
. Assume that for each $i$, in a call to `calc_dp(v_i)` there are no more than
$m_{v_i}^2$ hits to line
22.
Mike, alts and unfriendly comments I know that the following content might not be welcomed and I will lose lots of contribution, but I should write something about such a bunch of chaotic comments under there.
I may delete this tomorrow if I find my words useless.
### What happened
Several months ago, Mike posted a blog about banning [user:orzdevinwang,2024-10-07]'s alt, [user:zh0ukangyang,2024-10-07], and more alts. Lots of participants, including myself, were angry because [user:zh0ukangyang,2024-10-07] is such a talented coder and codeforces didn't treat the rule of single account seriously at that time. Then more and more alt accounts with high rating are reported, including mine.
After that I didn't use alts anymore, and most of high-rated Chinese participants(100% in my friends) discarded their alts and followed the rules. We might think that the rules are not that perfect, but rules are rules. I believe that no one will say "Banning [user:zh0ukangyang,2024-10-07] is unacceptable".
But I know what y...
more levels. I can still call myself a 6-Dan coder. So adjusting the rating
system might be useful, rating, which has more levels. I can still call myself a 6-Dan coder. So
adjusting the rating system
23.
My Reply on "Mike, please stop ignoring your userbase" This is a response to [this post](https://codeforces.me/blog/entry/141442).
Originally, I intended to leave it as a comment, but the text turned out to be quite long. So I decided to publish it as a separate post.
Hi!
Let me start with the main idea: I don't think I ignore too many issues (though I do ignore some). In most cases, I do work on them, but these days I just don't feel like writing about it. That kind of communication takes a lot of energy — which I currently don't have.
Oh, it looks like you edited the beginning of the blog, and now it triggers less of an internal protest in me. Honestly, lately I've been in
a difficult emotional state, and I just don't have the energy or desire to interact much. It's not just about Codeforces — it's generally harder for me to engage than it used to be. I won't go into details (health, relocation, family issues, changes in the nature of my work due to bots) — all of that affects my mental state and willingne...
vacations — I'm always on call and handling issues. It's been like that for
more than 15 years
24.
[Repost] "Justice may be delayed, but it cannot be absent": New Evidence on
NXIST's Cheating Scandal
[Repost] "Justice may be delayed, but it cannot be absent": New Evidence on NXIST's Cheating Scandal _Original post: [「正义可以迟来但不能缺席」：关于 NXIST 的一些新证据](https://zhuanlan.zhihu.com/p/620297880)_
_Translated by GPT-4 with some adjustment. Please inform me if there are any mistakes._
_All links to the invalid repository have been redirected to the backup repository._
**This article provides a logically complete set of evidence, which does not involve any non-public internet resources, regarding the "suspected cheating" incident involving the ICPC Yinchuan Station and ICPC Shenyang Station in 2021. By discovering the suspected GitHub account ([NaokiLH](https://github.com/NaokiLH), renamed to https://github.com/brokenTarget) of a team member from Ningxia Institute of Science and Technology (NXIST) TS 1 team, Lan Hao, two years ago, and by mining and analyzing the commit records of his algorithm competition repo, we have obtained direct evidence that at least 4 questions from the 2021 Yinchuan regional contest set and at least 6 questions (including scrapped questions) from the 2021 Sh...
25.
Don't use rand(): a guide to random number generators in C++ Don't use `rand()`. Why? Let's jump right into some code. What value will the following code print, approximately?
~~~~~
#include <cstdlib>
#include <iostream>
using namespace std;
const int ITERATIONS = 1e7;
int main() {
double sum = 0;
for (int i = 0; i < ITERATIONS; i++)
sum += rand() % 1000000;
cout << "Average value: " << sum / ITERATIONS << '\n';
}
~~~~~
Should be about 500,000, right? Turns out it depends on the compiler, and on Codeforces it prints 16382, which isn't even close. [Try it out yourself](http://codeforces.me/contest/1025/customtest).
### What's happening here?
If you look up [C++ documentation on `rand()`](https://en.cppreference.com/w/cpp/numeric/random/rand), you'll see that it returns "a pseudo-random integral value between `0` and `RAND_MAX`." [Click again on `RAND_MAX`](https://en.cppreference.com/w/cpp/numeric/random/RAND_MAX) and you'll see that "This value is implementation dependent. It's guaranteed that th...
`rand()` only goes up to 32767, what happens if we call `random_shuffle()` on
an array with, to 32767, what happens if we call `random_shuffle()` on an array with
significantly more elements, To replace `random_shuffle()`, you can now call
[`shuffle()`](https://en.cppreference.com/w/cpp
26.
C++ tips and tricks Hello, codeforces.
I would like to tell you about some tricks and constructions I use in C++. They are not hidden or anything, moreover, most of them are from stl or maybe well known among software engineers, but I often see codes where something is done by hand in, say, 5 lines, while in stl there is a function which does the same.
The things below are filtered by my personal sense of non-popularity (so no `__builtin` functions) and usage frequency (so there almost surely are similar things I don't know about) and are not really sorted in any reasonable order. Let's begin. [cut]
<hr>
- ### `all(x)`
This may be an exception to the rule of non-popularity -- this is quite widely used, but some next items will depend on `all(x)`, so I define it here. So, I talk about
```[c++]
#define all(x) (x).begin(), (x).end()
```
Now sorting a vector looks like `sort(all(vec))` instead of `sort(vec.begin(), vec.end())`.
However, it's not all about this define. Imagine you nee...
calls, instead of writing a for loop you can call `std::generate`: filling a
vector `vec` by random, variadic template in your, well, template, to call something like `min(a, b,
c, ...)`, but you may do this, , erase it), it may be useful to actually call `.find()` method in order to
erase by iterator, not by, , instead of writing a for loop you can call `std::generate`: filling a vector
`vec` by random values
27.
About the Round 382 Good afternoon!
I've decided to share my thoughts on the round 382.
Of course, it turned upset not only to me, but also to the round coordinator [user:GlebsHP,2016-11-28].
In this round the main negative feedback were caused by two problems: [problem:735D] and [problem:735C].
Regarding [problem:735D]. I do not share the criticism to this problem. In fact, to solve it would be nice to be familiar with <a href="https://en.wikipedia.org/wiki/Goldbach's_conjecture"> Goldbach's Conjecture</a> and better with <a href="https://en.wikipedia.org/wiki/Prime_number_theorem">Prime Number Theorem</a>. These facts are medium-popular in the world of programming contests. Familiarity with them is useful, gives useful insight into primes. It is important: in this problem it was necessary to perform a simple, but nevertheless, additional step to find solution. It seems to me that it's okay to use problems that have a reduction to some popular and semi-popular topics. Otherwise, it is th...
28.
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...
29.
[Tutorial] Matroid intersection in simple words **[This article is also available in [Russian](https://codeforces.me/blog/entry/69287?locale=ru)]**
Hello, CodeForces.
I think that matroids are beautiful and powerful concept, however, not really well known in competitive programming.
I’ve discovered matroids at 2019 Petrozavodsk Winter Training Camp. There was a problem that clearly cannot be solved using usual techniques I knew, editorial for this problem was just these three words “just matroid intersection”. Back then it took me more than 2 days of upsolving to find all the information and details I need and implement solution that gets Accepted on this. And it took way longer to actually understand why does it work and exactly how does it work. (I still hesitate in some details.)
Of course, it is not hard to google up all the definitions and some related articles, but in my opinion they all are focused more on mathematical part of theory, strict proofs in some not really obvious but short ways, and observing only ke...
of two types. Let’s call this graph $D_{(M_1, M_2)} (S)$. Now we can say that
some set $T$ is also, . Let’s call path from any vertex in $Y_1$ to any vertex in $Y_2$ without
shortcuts to be _augmenting, We have connected graph $G$ with $n$ vertices and two spanning trees of $G$,
let’scall them white, call for both matroids. So checking presence all edges, will be $\mathcal{O}(r)
\cdot \mathcal{O}(n, call this _exchange_ operation. Let’s see if we can find a sequence of exchange
operations that will
30.
My strategy at AtCoder & CS Academy There's been much controversy lately about the late submission strategy not penalized by scoring systems of AtCoder and CS Academy.
Most of the relevant discussion happened earlier at http://codeforces.me/blog/entry/53431 and http://codeforces.me/blog/entry/53449.
I have a lot of thoughts on the topic, so I've decided to share them in a separate blog post.
I really like the strategic part of programming competitions. Of course, problem solving is more important.
But every contest consists of multiple problems, so there has to be a way of comparing participants which performed better at different problems.
There's a huge variety of scoring rules, and I find it truly amusing.
The "submit after solving all problems" strategy looks widely attributed to me now, mostly due to [user:Petr,2017-07-24]'s remarks regarding my participation in AtCoder contests.
In my opinion, it's wrong for multiple reasons.
A closer five-word description of my strategy is "implement after solvin...
performance is poor. I wouldn't call it an advantage of this strategy. I
believe considering the option of, place 1 for me. So, there's a prerequisite which one might call a disadvantage
too: it's important, sometimes too) -- place 5 instead of place 1 for me. So, there's a
prerequisite which one mightcall a
31.
You won't believe how this simple trick defeated the unexplained bug destroying every top LGM ### TL;DR
Currently people are discussing a slowdown bug on Codeforces that seems to happen randomly, and can cause code to run 100x slower and get TLE. More details in [user:pajenegod,2024-03-03]'s [blog post](https://codeforces.me/blog/entry/126654).
In this article, I present a mitigation: add the following to your code.
~~~~
#include <windows.h>
void *operator new(size_t size) {
if (void *ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
throw std::bad_alloc{};
}
void operator delete(void *ptr) {
HeapFree(GetProcessHeap(), 0, ptr);
}
~~~~
<spoiler summary="If you use malloc/free in C++ (you shouldn't), also change them.">
~~~~
void *my_malloc(size_t size) {
if (void *ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
throw std::bad_alloc{};
}
void my_free(void *ptr) {
HeapFree(GetProcessHeap(), 0, ptr);
}
~~~~
</spoiler>
<spoiler summary="If you use aligned new/delete in C++, also change the...
By default `new` and `delete` with GCC simply call the `malloc` and `free`
functions from the C
32.
Call for Tasks for AGC First of all, I have to say sorry for the vacancy of AGCs.
I'm confident in the style of AtCoder problems, but I have to admit that I was too strict; when I found a problem that was interesting but had a tiny flaw, I didn't try to use it in AGCs. In fact, I received several messages that some ARC problems are good enough for AGCs. If people who are stronger than me say that, what is my severe threshold for? Therefore, I'll be looser in selecting problems. It isn't such a big change that ARC becomes AGC. However, with the new policy, I could have made a few more AGCs in the first half of this year.
Now let's get down to the main subject: Call for Tasks.
There were a few non-Japanese AGC writers, but the procedure of contest proposals was obscured.
I want to make it public here. Please follow the following steps:
- Come up with tasks for AGCs. It is desirable that you have ideas for a whole AGC set, but it's OK to have only hard problems.
- DM me, and show me that you can po...
Call for Tasks for AGC, this year. Now let's get down to the main subject: Call for Tasks. There were
a few non-Japanese, Now let's get down to the main subject: Call for Tasks. There were a few
non-Japanese AGC writers
33.
[Tutorial] Common Mistakes in Competitive Programming and How to Avoid Them One thing is for sure. You do make mistakes. I also make miskates and that's what makes us human. But what we can surely do is — to try to minimize the errors that we make throughout our life.
I have compiled some of the mistakes that I made in my early Competitive Programming phase. I also mentioned how to avoid them. Also, in most cases, I will give you a chance to find out what the bug is before I reveal the culprit as I tried to make this blog interactive. The codes that I have used in this blog have been written in C++ as it is the most used language for CP.
**So, if you are new to CP, stick with me as you might don't wanna repeat the mistakes that I made when I was a beginner.**
#### Mistake 1
Check out the following code:
<spoiler summary="Code">
~~~~~
#include<bits/stdc++.h>
using namespace std;
int main() {
int a = 1000'000'000,b = 1000'000'000;
long long product = a * b;
cout << product << '\n';
return 0;
}
~~~~~
</spoiler>
The outp...
Check out [this](https://www.geeksforgeeks.org/difference-between-call
-by-value-and-call-by
34.
The Reason You are Bad at Codeforces — You are Not Russian Enough If you are triggered by this clickbaity blog title, you are probably interested in improving your Codeforces skills. Now, I will share my point of view on the differences between Codeforces and ICPC contests, and how you can, in my humble opinion, maximize your Codeforces rating gain.
I mostly consider that all conceivable competitive programming problems need three aspects of skill:
1. Observation — the ability to understand the problem and come up with non-trivial properties.
2. Technique — the ability to apply a well-known algorithm or data structure to the problem.
3. Implementation — the ability to code fast and debug fast.
Collaterally, I refer to these three skills as Russian-ness, Chinese-ness and American-ness, respectively, for reasons you will soon see below.
## Observation (Russian-ness)
Observation means that you stare at some problem for a sufficient amount of time and you are able to reduce it to some easier problem. One good proble...
Now I call these problems *American* because geo problems usually require a
code reference and are, Now I call these problems *Chinese* because Chinese OI and ICPC have a tendency
to produce problems
35.
Chinese Postman Problem: How I Ran a 180 km Ultramarathon Through Every Street in My City Hello, Codeforces!
A couple of years ago, a friend of mine told me that two cyclists had passed through every single street in the center region of the city I live in (Belo Horizonte, southeastern Brazil), on the [third try](https://www.strava.com/activities/1030665876/overview).
<spoiler summary="First try">
After ~160 km, they had not completed 1/3 of the goal. [Strava link](https://www.strava.com/activities/976021527).
<img src="/predownloaded/8a/53/8a53829f7d78e88808a3ff751b64406ec2fc0efd.png" style="width: 600.0px;max-width: 100.0%;max-height: 100.0%;">
</spoiler>
<spoiler summary="Second try">
They were better prepared, but one of the guys was run over by a car (no big injuries). [Strava link](https://www.strava.com/activities/999450285).
<img src="/predownloaded/85/8f/858fdcdcfda93cd1d9c7c59db7dbfad9e63d6ea2.png" style="width: 600.0px;max-width: 100.0%;max-height: 100.0%;">
</spoiler>
<center>
<img src="/predownloaded/8d/5c/8d5cfb677a361654105e49f36f214c35...
We call a graph **eulerian** if there is a walk that starts and ends at the
same vertex and visits
36.
A summary of what passes for an Indian ICPC Contest, apparently The online round for the India’s ICPC was held on 23rd. And also a week before that. The first time around, the organisers tried debuting a self-hosted DOMjudge instance. That didn’t go too well, so a recontest was scheduled on CodeChef.
If you’re not too familiar with the Indian ICPC system — this online prelims is used to select teams that can participate in the offline regionals. From a single university, usually approx. 2 teams (for the top unis) or 1 (for almost all unis that aren’t in top-15) qualify.
As you could guess, it’s quite easy for good teams to miss a spot. Looking at the first contest’s rankings, teams from rank 2 to 100+ all had 4 solves. Owing to severe system issues in the first contest, the time penalties weren’t too reliable differentiators, leading to the recontest this Saturday.
In hindsight, we forgot to be grateful for the problemset and reliable testcases the first time. I’m sure everyone agrees that the basic requirements (ignoring all other stuff...
failing submissions. They announce the issue ASAP (and fix it or call it off,
depending on the severity
37.
My sad story Teams advancing to 2016 WF Phuket in Asia have been announced recently. This announcement is undisputedly tantamount to a death sentence for me. I am the one waiting anxiously, refresh Dr. Hwang's blog everyday. But it seems that for years, our training was meaningless.
I think many of us dedicate our passion to programming contests because we see them transparent, fair and without any corruption. And I also believe that as contestants, what we should do is only focus on the practice. And I thought those political business should never come to bother me one day. But sadly, it is my team who is going to become one of the sacrifices of a succession of the dissension.
What happened so far
------------------
The quarrel between the Asia director and the local community is [a long story](http://blog.sina.com.cn/s/blog_b946da100101q21y.html) to tell. But it has never been as serious as it was in the past season. Now reflecting on this, I know on the surface everything is going okay...
38.
Editorial for Hello 2024 ### [problem:1919a]
Author: [user:maomao90,2024-01-02]
<spoiler summary="Hint 1">
When does the game end?
</spoiler>
<spoiler summary="Solution">
Depending on whether the player chooses to exchange wallets with their opponent on step $1$, $1$ coins will be removed from either the opponent's wallet or the player's wallet. This means that if either of the players still has remaining coins, the game will not end as at least one of the choices will still be valid.
The only way that the game ends is when both players have $0$ coins. Since each operation decreases the total amount of coins by exactly $1$, the only way for Alice to win the game is if $a + b$ is odd.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int a, b; cin >> a >> b;
if ((a + b) % 2 == 0) {
cout << "Bob\n";
} else {
cout << "Alice\n";
}
}
...
find the distance of every edge to the root. For convenience, we will call the
distance of an edge, . For convenience, we will call the distance of an edge to the root the depth
of the edge, For convenience, we will call a vertex $i$ special if there exists some $1\le
j\le n$ where $s_{j
Tutorial of Hello 2024
39.
Complex FFT is not as bad as you think ... Probably.
Hi everyone!
As some of you _might_ already know, I don't like NTT. Primary reasons for this are:
- I don't like modular arithmetic optimizations (Montgomery, etc).
- I don't like NTT mods, and prefer good, old $10^9+7$.
- I do like algebra of complex numbers.
But, to my regret, the overwhelming mainstream in modern competitive programming is NTT. Primary reasons are:
- It's allegedly faster.
- It needs less memory.
- It has no precision issues.
- People don't like algebra of complex numbers.
There is nothing I can do about the last, but today I'll address the first 3. Optimizing complex FFT was on my mind for quite some time, but I didn't really work on it _that much_ until the [blog](https://codeforces.me/blog/entry/142063) by [user:Qwerty1232,2025-04-24] on optimizing NTT has dropped, which motivated me to actually put some serious effort into this.
In this blog, we will primarily focus on optimizations that are specific to complex arithmetic...
40.
"Algorithms in Depth" Stream Series: Kicking Off With FFT Hi Codeforces!
I’ve long believed that it's _really_ worth revisiting the same competitive programming topics multiple times.
The first time, you’re just trying to survive and maybe grasp the basics. The second time, you’ve solved some problems, you know where you got confused, and you're ready to absorb more.
By the third time, you’ve seen and solved enough to start appreciating the subtleties — the tricks, advanced applications, deeper meaning.
But most lectures I’ve seen are designed as a one-size-fits-all — trying to cover everything from scratch _and_ dive into the advanced stuff in one go. That’s rarely optimal.
Take binary search. I once talked about it for six hours straight. A beginner at that lecture would’ve probably quit CP immediately. And that’s ok. Beginners don’t need all that. But the truth is, there _is_ that much depth to explore even in seemingly simple topics like binary search — once you're ready.
Yet many people only see the beginner version once and mo...
41.
[Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges #### Introduction
This is a tutorial/exploration of problems that can be solved using the "DFS tree" of a graph.
For a way too long time, I didn't really understand how and why the classical algorithm for finding bridges works.
It felt like many tutorials didn't really explain how it works, kind of just mentioned it in passing and quickly
just moved on to implementation. The day someone explained what the DFS tree is, I finally understood it properly.
Before, it took me ages to implement bridge-finding properly, and I always had to look up some detail. Now I can
implement it at typing speed.
But more importantly, I began to see how the same techniques can be used to solve graph problems that have more or
less nothing to do with bridges. The thing is, when you have a black box, you can only ever use it as a black box.
But if you have a box that you understand well, you can take it into pieces, repurpose the pieces for completely
different things, all without getting lost...
of u: 4 if v is not visited: 5 mark the edge u->v 6 call visit(v) ~~~~~, of u: 4 if v is not visited: 5 mark the edge uv 6 call visit(v) ~~~~~, the index of the back-edge $u$ is under; call that $\mathrm{cycleId}[u]$; if
$u$ isn't in a cycle, vertex 1. We'll call these edges _span-edges_; all other edges are called
_back-edges_., vertices of the same color. We will call these edges _contradictory_., Let's call the edges marked at step 5 _span-edges_.
42.
New: Educational Rounds on Codeforces! Hi everybody!
First, I invite you to take part in an official [contest:597]. The fact is, the Codeforces team has made numerous changes to the platform (details are below), and we want to be sure that the basic functionality remained unchanged. This round will have a shortened duration of 1.5 hours, consist of 3 (maybe 4) problems that you might have already seen before. Its purpose is to test the system on the one hand, and on the other hand — to brighten up a Wednesday evening. Of course, the round will be unrated.
Now the main thing. This coming Friday (yes, the 13th of November) Codeforces starts another line of rounds. We called them Educational Rounds. Using my students at the Saratov State University Programmings Competitions Training Center as an example, I regularly notice that even those who have a considerable progress in the results on the rounds often have narrow purview in terms of standard topics and ideas, they are not familiar with many well-known problems ...
43.
Blowing up unordered_map, and how to stop getting hacked on it C++ has always had the convenient data structures `std::set` and `std::map`, which are tree data structures whose operations take $O(\log n)$ time. With C++11, we finally received a hash set and hash map in `std::unordered_set` and `std::unordered_map`. Unfortunately, I've seen a lot of people on Codeforces get hacked or fail system tests when using these. In this post I'll explain how it's possible to break these data structures and what you can do in order to continue using your favorite hash maps without worrying about being hacked
[cut]
.
So how are they hackable? We always assume hash maps are $O(1)$ per operation (insert, erase, access, etc.). But this depends on a key assumption, which is that each item _only runs into $O(1)$ collisions on average_. If our input data is completely random, this is a reasonable assumption. But this is no longer a safe bet when the input isn't random, especially so if someone is adversarially designing inputs to our code (a.k.a. hacking ph...
44.
A simple introduction to "Segment tree beats" Hi, I’d like to introduce a simple trick about segment tree in this blog as I promised in [this comment](http://codeforces.me/blog/entry/54750?#comment-387957). Sorry for the long delay, as a sophomore in Peking University, I've just finished a tired semester and a painful final exam. And now I finally have enough time to do a simple introduction to this interesting algorithm.
It may be a huge project for me since my English is not good. I think I will finish this blog in several steps and I will try to finish it as soon as possible :)
In China, all of the 15 candidates for the Chinese National Team are asked to write a simple research report about algorithms in informatics Olympiad, and the score will be counted in the final selection. There are many interesting ideas and algorithms in these reports. And I find that some of them are quite new for competitors in CF although they are well known in China from the final standings of some recent contests. For example, In the last co...
. So the proof is still hold for other operations. That's why I call this proof
universal.
45.
Calling CF Community to Support Rescheduling ACPC **UPD: it's now rescheduled! thank you all for the support.**
Hello Codeforces,
I didn't want to publish this blog during these circumstances, as it's the last thing to care about, but I'm publishing it hopefully ACPC organizers see it.
Last Saturday, we got an email saying that the ICPC world finals, which were supposed to be in 11 days in Sharm El-Sheikh, got rescheduled to a later time. And it was expected that the ACPC, which is supposed to be in 17 days in the same hotel, would get rescheduled too. but apparently the competition is still on its previously scheduled date!! I would like to note that ACPC is scheduled to be in the same hotel as ICPC.
Let's talk about it from many perspectives.
From the travel perspective, sadly while talking I will partition Palestine into the West Bank and Gaza, but we're one nation and stand together with each other.
Firstly, two teams from Gaza are supposed to participate in ACPC this year, and surely, they will not be able to co...
46.
My own algorithm — offline incremental strongly connected components in O(m*log(m)) Hello Codeforces!
As all of you know, there are so many known algorithms named after people who invented them — from the easiest ones, like Dijkstra, to the harder ones, like Berlekamp–Massey algorithm. These algorithms were innovative when they were invented, so of course, it's good that they are named after their inventors.
But, today, I've seen a blog about the solution to the problem "compute LCS of two strings in time $O((n + k) \cdot \log(k))$, where $n$ is the sum of lengths of the strings, and $k$ is the number of pairs of matching positions in them". To be honest, it a bit pissed me off that even this algorithm is named after its creators. Is it ok to name the solution to every possible problem after its author? I won't judge it. Anyway, I want my very own Radecki algorithm, so let me give it a try. If anyone has ever heard about it — it's cool. Let me know, and it'll be just another helpful blog on Codeforces.
Let's imagine the following problem: there is...
What should we take from the recurrence? The simplest idea: at each call of the
$rec$ function, for
47.
Codeforces Round #745 Editorial I'm very sorry about all the inconvenience, and I would like to bear the blame. Much thanks to those who help me prepare this round. It's not their fault. And much thanks to your participation.
[problem:1581A]
------------------
idea: [user:interlude,2021-09-30]
preparation: [user:CQXYM,2021-09-30]
tutorial: [user:CQXYM,2021-09-30]
Assume a permutation $p$, and $\sum_{i=2}^{2n}[p_{i-1}<p_i]=k$. Assume a permutaion $q$, satisfying $\forall 1 \leqslant i \leqslant 2n, q_i=2n-p_i$. We can know that $\forall 2 \leqslant i \leqslant 2n,[p_{i-1}<p_i]+[q_{i-1}<q_i]=1$. Thus,$\sum_{i=2}^{2n}[q_{i-1}<q_i]=2n-1-k$, and either $p$ should be counted or $q$ should be counted. All in all, the half of all the permutaions would be counted in the answer. Thus, the answer is $\frac{1}{2}(2n)!$.
The time complexity is $O(\sum n)$. If you precalulate the factors, then the complexity will be $O(t+n)$.
-----
<spoiler summary="solution">
~~~~~
#include<stdio.h>
int f[100001];
int m...
enumerate the position of the bigest number in the permutaion. We call the
position is $a$. The, node $u$ and "distance" of node $u$ as $dis[u]$, and call node $u$ is "deeper"
than node $v$ if and, , and call them $a$ and $b$ separately., Second, if $s$ and $t$ are not node 1. We choose an arbitrary path $1$ --> $s$
andcall it path 0
Tutorial of Codeforces Round 745 (Div. 1)
Tutorial of Codeforces Round 745 (Div. 2)
48.
Sums and Expected Value — part 1 part 2: https://codeforces.me/blog/entry/62792
Watch my lecture-stream tomorrow (Thursday) at [14:00 CEST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=EV+lecture+1&iso=20181025T14&p1=262) — <s>[https://www.youtube.com/watch?v=qdlPY37MBPo](https://www.youtube.com/watch?v=qdlPY37MBPo)</s> [https://www.youtube.com/watch?v=U_h3IjreRek](https://www.youtube.com/watch?v=U_h3IjreRek).
I will go through theory and problems from this blog.
The only prerequisite is knowing what is probability.
The next (harder) part on Monday.
The video will be available later, with timestamps for each problem — so you don't have to watch everything.
### Definition of EV
Let's say we bought a lottery ticket for 2$.
We will win 10$ with probability 10%, and 20$ with p-bility 2%.
On average, it gives us $0.1 \cdot 10 + 0.02 \cdot 20 = 1.4$,
so we are worse off after buying the ticket.
The computed average is called the expected value.
The expected value (EV, expecta...
49.
Matrix Exponentiation tutorial + training contest tl;dr — video tutorial https://www.youtube.com/watch?v=eMXNWcbw75E and codeforces GYM training https://codeforces.me/gym/102644 (register by finding this contest in GYM instead of using the link directly)
video editorial: [part 1 (ABCDEF)](https://www.youtube.com/watch?v=kQuCOFzWoa0) and [part 2 (GHI)](https://www.youtube.com/watch?v=RA_SpxP2t54)
codes to all 9 problems: https://github.com/Errichto/youtube/tree/master/matrix-exponentiation
Prerequisites: binary exponentiation and iterative dp (you don't need to know matrices)
The youtube tutorial ([link](https://www.youtube.com/watch?v=eMXNWcbw75E)) focuses on intuition and graph-like visualization . Or, if you prefer, below is a shorter (less detailed) text tutorial instead.
You can practice by solving a set of 9 educational problems in GYM https://codeforces.me/gym/102644. ABCD are easy, EF medium, GHI are hard. If you are stuck, see hints below or watch the full solution analysis — [part 1 (ABCDEF)](https:...
50.
How to ask for help in PM There was a blog today with a similar title, and although it was (I think, not really sure as I didn't get a good look) some kind of satire/joke blog, I wanted to post some serious advice about things I (don't) like to see when people are PMing me. However I decided that this wouldn't be in the spirit of the blog and decided to make a separate blog. And now that blog is deleted anyway.
While it's not a bad thing to write messages to more experienced users, most people who write me do things that make them very difficult to deal with. These are my opinions, but somewhy I feel that many reds will agree. Some things here feel silly to write because they are so obvious. But I'm only writing them because people regularly mess them up.
[cut]
$~$
####Use punctuation and spelling.
There are some [very simple rules](https://codeforces.me/blog/entry/82186#comment-689836) that make your messages infinitely more readable. I find it especially strange when many of these messagers call...
call me "sir", which is supposed to show respect, but then write like this. Is
this how you write to
51.
Algorithm Gym :: Data structures Today I want to introduce you some very very useful data structures.
In this lecture, we are trying to improve your data structures skills, stay with us and click on **read more**.
[cut]
Important data structures :
Trees
-----
Trees are one of the most useful data structures.A tree is a connected-acyclic graph.There are too many types of trees, like : rooted trees, weighted trees, directed trees, tries, etc.
Partial sum
-----------
There are two types of problems solvable by partial sum.
1.Problems which you are asked to answer some queries about the sum of a part of elements (without modify queries).
Solution of all of this problems are the same. You just need to know how to solve one of them.
Example : You are asked some queries on an array $a_1,a_2,...a,_n$. Each query give you numbers $l$ and $r$ and you should print $a_l + a_{l+1} + ... + a_r$ .
Solution : You need to build another array $s_1, s_2, ..., s_n$ which $s_i = a_1 + a_2 + ... + a_i$ ...
node $i$ we call it $s[i]$, so we should build the initial segment tree., than the value of its child(ren) (we call this a max heap). We can use heaps
in heap sort., $ are in a chain and we call the edge $uv$, heavy, otherwise light., (So, we should call $build()$ ), (We should call $increase(l\ r\ x)$), (We should call $modify(p,\ x)$), (We should call $sum(l,\ r)$), So, before reading the queries, we should call $build()$ .
52.
CodeTON Round 5 Editorial ### [problem:1842A]
<spoiler summary="Tutorial">
Let's view it as when monsters $x$ and $y$ fight, their health changes into $\max(x-y,0)$ and $\max(y-x,0)$ respectively. So any monster with $0$ health is considered dead. Therefore, a player loses when the health of his monsters are all $0$.
Notice that $\max(x-y,0)=x-\min(x,y)$ and $\max(y-x,0)=y-\min(x,y)$. Therefore, after each step, the sum of the health of monsters decrease by the same amount for both players.
Therefore, we only need to know $\sum a_i$ and $\sum b_i$ to determine who wins. If $\sum a_i > \sum b_i$, Tsondu wins. Else if $\sum a_i < \sum b_i$, Tenzing wins. Else, it is a draw.
</spoiler>
<spoiler summary="Code">
~~~~~
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m, a[50], b[50];
long long sumA = 0, sumB = 0;
cin >> n >> m;
for (int i = 0; i < n;...
53.
Codeforces Round #616 Hello Codeforces o(≧∇≦o) I'm glad to introduce you to [contest:1290] and [contest:1291], which will take place on [contest_time:1290].
Each division will contain **6 problems**, and you will have **2.5 hours** to solve them. There might be interactive problems, feel free to learn about them [here](https://codeforces.me/blog/entry/45307). The problems were created by [user:265918,2020-01-30], [user:Ari,2020-01-30], [user:Kuroni,2020-01-30], [user:gamegame,2020-01-30], and [user:hugopm,2020-01-30].
Now, here are some people I would love to mention:
- Thank you [user:isaf27,2020-01-30] for being a super helpful, diligent, and humorous coordinator ヽ(〃･ω･)ﾉ
- Thanks to [user:McDic,2020-01-30], [user:nvmdava,2020-01-30], [user:dorijanlendvaj,2020-01-30], [user:antontrygubO_o,2020-01-30], [user:sdssudhu,2020-01-30], and [user:farmersrice,2020-01-30] for helping with the preparation of the tasks.
- Thanks to [user:Sofie_Ever,2020-01-30], [user:mcfr,2020-01-30], [user:MathisHamm...
Announcement of Codeforces Round 616 (Div. 1)
Announcement of Codeforces Round 616 (Div. 2)
54.
Another Graph Editor! **UPDATE (5 Dec 2024)**
There have been a few new features since its initial release.
- Multiple graphs/testcases (each "tab" can store its own testcase so you can visualize all testcases at once)
- Multi-edge support
- Bipartite mode
- More appearance-related configuration sliders
Thanks for all the support and suggestions! Things will continue to be added slowly over time, but if there's a particular feature that you want you can just open an issue on GitHub.
---
Hello, Codeforces!
I've been working on a graph visualization tool for a while now, and because I couldn't think of a good name for it, I've opted to call it *Another Graph Editor*. If you have any name suggestions, pls let me know. Here's the
[website](https://anacc22.github.io/another_graph_editor/) and the [repo](https://github.com/anAcc22/another_graph_editor).
The layout is very much inspired by CS A...
good name for it, I've opted to call it *Another Graph Editor*. If you have
any name suggestions
55.
The Ultimate Reroot Template Hi Codeforces!
Have you ever had this issue before?
If yes, then you have come to the right place! This is a blog about my super easy to use template for (reroot) DP on trees. I really believe that this template is kind of revolutionary for solving reroot DP problems. I've implemented it both in [Python](https://codeforces.me/contest/1324/submission/240129139) and in [C++](https://codeforces.me/contest/1324/submission/240131453) (the template supports `Python2`, `Python3` and `>= C++14`). Using this template, you will be able to easily solve > 2000 rated reroot problems in a couple of minutes, with a couple of lines of code.
A big thanks goes out to everyone that has helped me by giving feedback on blog and/or discussing reroot with me, [user:nor,2024-01-03], [user:meooow,2024-01-03], [u...
`exclusive`. I call this data structure the _exclusive segment tree_.
56.
Blogewoosh #5 (with images from now) Hello, codeforces!
Because after Round #507 sad men in suits visited me in my flat, this time I won't write about any task from the future. Instead, this blog will be about my own trick. I said "my own," but probably some of you have already heard about it or even figured it out, but I've developed it by myself, so I consider it as my own.
In particular, it's **GEOMETRY TIME!!!**. But please, don't escape already. I also don't like this topic so much, that's why I really like this trick. Let me tell you a story from one onsite Polish contest, which took place a few months ago. I was thinking about one of the problems, and I've figured out that I had to do some binary-search (on doubles) and then check if a set of half-planes has a non-empty intersection. The answer would tell me in which direction should I turn in the binary search.
Firstly, I grabbed my head, because I've never written an intersection of half-planes. I had my acm library with [user:Errichto,2018-09-07]'s code...
It might be confusing, but I'll call it "upper convex hull" anyway, mostly
because it's above
57.
On "is this greedy or DP", forcing and rubber bands #### Introduction
When it comes to "problem-solving techniques", there are roughly 3 levels:
1. Concrete algorithms (Kruskal's algorithm, Li-Chao tree, fast Fourier transform)
2. General patterns (dynamic programming, greedy, square-root decomposition)
3. Meta-strategies ("how do I even go about solving this problem?")
There is some grey area, but in general this classification works well.
[Many tutorials](https://codeforces.me/catalog) have been written about ideas that fall into 1 or 2.
But very little has been written about the third category. On the catalog, I think the
only blogs that really qualify are [this](62730) and [this](20548). There is also
[this](92248?#comment-809401) valuable comment. As to why there is so little written,
I think I can identify two reasons.
- Most strong contestants don't really consciously think about these.
After solving a problem with FFT, it's hard not to know you used FFT.
If you used DP, even if you did it without thinki...
58.
About the Universal Cup, the Semifinals, and myself... Hey'all!
This gonna be a long post, so let me put an important TLDR here first: we are going to host **The 3rd Universal Cup Semifinals**, which will take place on August 24, 2025 **online**, at [11:00 (UTC)](https://www.timeanddate.com/worldclock/fixedtime.html?msg=The+3rd+Universal+Cup+Semifinals&iso=20250824T19&p1=33&ah=5). This contest will be a part of our Finals Team Selection, which the detailed rules and announcements will be published later next week.
---
Now for some extra context, if you're interested.
Last week, we hosted the [last online stage](https://codeforces.me/blog/entry/143954) of The 3rd Universal Cup. After that, I posted a [feedback form](https://docs.google.com/forms/d/1g5Txhiirh_lRsvGfkYWRozu0WDDGK31IAXjB7VgeVoM/edit) on our discord server. I received lots of thoughtful responses (P.S — it's still open, so feel free to fill it out if you haven't yet!).
I've read through all the feedback, and I'd like to share a few thoughts.
### On the Number...
59.
The Time Complexity Lower Bound for Segment Tree Beats is log^2 Original Post: https://jiry-2.blog.uoj.ac/blog/1404
The following content is translated by Gemini 2.5 Pro.
## Part 1: Introduction to the Hacking Method
### How to Map the Hack Sequence to a Segment Tree
First, we are given a Hack sequence of length $len$. After $O(1)$ range addition operations and $\Theta(\log len)$ global $\text{chkmax}$ operations, this sequence becomes a cyclic shift (rotation) of the original sequence. Since a cyclic shift does not affect our range addition and global $\text{chkmax}$ operations (we can simply shift the indices for the range addition accordingly), we can consider the sequence as unchanged.
If we have such a sequence, let $len=n^{\frac{1}{3}}$, and place such a sequence at intervals of $n^{\frac{2}{3}}$. Each sequence corresponds exactly to a segment tree interval. A subtree of size $n^{\frac{2}{3}}$ contains exactly one such segment tree interval.
For the Hack sequence, the range addition operations are performed one by one on eac...
nodes. Let's call them square nodes and circle nodes. We might as well dictate
that under a circle node, three steps in total, which we will call step one, step two, and step three. A
disintegration pair is in
60.
[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, ...
$ divides $b_{1},b_{2},...,b_{m-1}$ and $b_{m}$ has the same remainder as $n$
mod $k$ (call such sequences, , it might be a stretch to call this a generating function problem but I just
want to demonstrate, /contestInvitation/fb0f7a0301acb44f9d8f82c94bd848737ce55e6c) Call a permutation
$p_1, p_2, ..., p_n, Let us count the number of **rooted** trees on $n$ vertices. Call this number
$t(n)$. If we remove, To relate $c(k)$ with $a(k), b(k)$, we need to look at the OGFs of $a$ and $b$ (
call them $A_{o}(x
61.
[Tutorial] Proving the inverse Ackermann complexity of Union-Find #### Introduction
Most of us are familiar with the union-find data structure and the two optimizations one can do on it: _union by rank_ and _path compression_. Most tutorials will introduce these methods and state that if both optimizations are used, the complexity will be $\mathcal{O}((n + m) \alpha(n))$. Here, $n$ and $m$ are the number of vertices and queries respectively. What is $\alpha$? Generally, we are told that $\alpha$ is some mysterious function that grows very slowly: $\alpha(N) < 5$ where $N$ is the number of subsets of particles in the observable universe and whatnot. What it is is usually not clarified very much. And there is typically no proof (or intuition and other such justifications) as to why the complexity is like that: usually we're told that the complexity analysis is quite long and complicated. At the time of writing, both [cp-algorithms](https://cp-algorithms.com/data_structures/disjoint_set_union.html) and [Wikipedia](https://bit.ly/3EvnzrI) are like th...
constant time, either per query or per `find` call. We also have the
initialization, which takes $\mathcal, **Find-paths and find-edges.** Imagine what vertices are visited in some "find"
query. If wecall, Notice that by the path compression rule, the next `find` call from $u$ will
generate a find-path
62.
[Tutorial] The command line: how to read input from file without #ifdef and much more #### Introduction
Instead of algorithms and math, I'll be doing something completely different here.
There is something that has bothered me for a long time: people not understanding
the tools they use to participate in contests and thus failing to take real advantage
of them. And it all goes back to not understanding the command line.
Some of you might say, "well surely, the command line is something obsolete and you're
only clinging to it because you [insert ridiculous amateur-psychology here]?"
No! The command line is not obsolete, and unless competitive programming becomes
so mainstream that software vendors start writing professional-grade tools aimed
specifically at us, it won't be.
[cut]
$~$
What is the command line? Any of these:
As you can see, it comes in many background colors and fonts, but the basic idea
is always the same. It's a box you can type commands in, which it will ...
63.
GF: Competitive programming Discord server (Div. 1 only) Hi everyone!
Every once in a while someone makes a competitive programming [Discord server](https://discord.com). Today, we're inviting you to join one of them 😊
So, first things first, the big flashy link for those who want to cut to the chase:
<br><br>
<center>
<span style="display:inline-block; border:2px solid #ccc; padding:10px; border-radius:8px; background:#f9f9f9;">
<a href="https://discord.gg/sTk4khgmSd" style="font-weight:bold; font-size:1.2em;">Join us!</a>
</span>
<div style="margin-top:5px; font-size:0.85em;">
<a href="https://discord.gg/bitset" style="color:#555;">discord.gg/bitset</a>
</div>
</center>
**Name**: GF<br>
**Members**: 1000+ (and growing!)<br>
**Admins**: ~Halzion,2025-08-09 ~rewhile,2025-08-09 ~defnotmee,2025-08-09, ~adamant,2025-08-10<br>
**Moderators:**
<table style="border-collapse:collapse; border:none; margin-left:2em;">
<tr>
<td style="border:none; padding:0 8px;">~jeroenodb,2025-08-09</...
64.
Codeforces update: contests and problemsetters Hi everybody!
Hope you liked our [Revolution of Colors and Titles](/blog/entry/20638). Maybe you even have took part in a contest in new status. The last round have set an incredible record: 8000 participants! And I'm glad to tell you that there was no single technical issue during the round time! Consider the 15-minute delay as a part of our evil plan for setting up a new record :)
I'm glad to tell that Codeforces team is able not only to tune colors and formulas, but also to work on new features for you. You may see on [contests](/contests) page that there is a list of authors for each of the rounds! Moreover, in profile of a person there is now an entry called "problemsetting" that allows you to see the list of all contests in whose preparation a person took a part.
<center>
<a href="http://i.imgur.com/3mul76p.png"><img src="http://i.imgur.com/3mul76p.png" /></a> <br />
[user:Endagorion,2015-10-03] looks like this.
</center>
[cut]
Let's clarify what do we mean by tak...
65.
OCPC 2024 Winter — wrap Hi everyone!
<center><a href="https://ocpc.mathos.unios.hr"><img src="https://ocpc.mathos.unios.hr/images/ocpc.svg" height="100px"></a>
<a href="https://icpc.foundation/"><img src="https://ocpc.mathos.unios.hr/images/ICPC.svg" height="100px"></a></center>
<center>
<b>Sponsored by</b><br>
<a href="https://www.janestreet.com/join-jane-street/open-roles/?type=students-and-new-grads&location=london">
<img src="/predownloaded/ee/f2/eef26616a3661c658d1545f18ed21fabb14d5871.svg" height="50px" style="margin: 5px 5px 5px 5px;"></a>
<a href="https://pinely.com/">
<img src="/predownloaded/0a/0f/0a0f3f67435d1f6e467bc7203d4a2090ba8f92cc.svg" height="50px" style="margin: 5px 5px 5px 5px;"></a>
</center>
Yesterday marked the conclusion of the third [Osijek camp](https://ocpc.mathos.unios.hr) (also see the [announcement](https://codeforces.me/blog/entry/124573) on Codeforces). Similar to the last time, the camp was organized by Tähvend Uustalu ([user:-is-this-fft-,2024-02-26]) and m...
#### Call for problemsetters
66.
Linear Basis (Xor Basis Extended) As part of the graduation requirements for my school, I have to complete a simple research project, so I decided to do something related to data structure and algorithms. I believe I have come out with a data structure that maintains the basis of vectors in $(\mathbb{Z}/m\mathbb{Z})^d$, where $m$ **may not be prime**. Since this was related to competitive programming, I think it is a good idea to share it here. Hopefully, this algorithm is actually novel :P
I would like to thank:
- [user:icypiggy,2021-12-26] for being my research mentor and tolerating my dumb questions
- [user:rama_pang,2021-12-26] and [user:adamant,2021-12-28] for their helpful suggestions and comments
Please comment under the blog or message me on codeforces if any parts are unclear or wrong. Also, I hope that some LGMs can help solve the open problems in this blog.
# Introduction
Maintaining the basis of vectors in $(\mathbb{Z}/2 \mathbb{Z})^d$, also known as the xor basis algorithm is a well-studie...
Consider how $span(S)$ changes after a call to \AV{$V$}. $x \in span(S, Theorem 2: After each call to $\texttt{Add-Vector}$, the following holds: for
all $i$ such that $A_
67.
Combinatorial species: An intuition behind generating functions Hi everyone!
The usage of generating functions is quite common in competitive programming these days. But it seems to happen so, that they're mostly presented as a way to simplify formal manipulation with polynomial coefficients, rather than something meaningful. But there actually is a meaning to all of this, and today I'm going to shed a light on it.
Alongside the blog post we'll uncover the combinatorial meaning of
- The addition $F(x)+G(x)$,
- The multiplication $F(x)G(x)$,
- The exponent $\exp F(x)$,
- The logarithm $\log F(x)$,
- The sum of the infinite geometric progression $\frac{1}{1-F(x)}=1+F(x)+F^2(x)+\dots$,
- The general composition $F(G(x))$
for the generating functions $F(x)$ and $G(x)$ and the underlying structures they represent.
### Prerequisites
- Basic notion of set theory (cardinality of sets, mappings, bijections, cartesian product, disjoint union, etc);
- Polynomials and formal power series (representation, convolution formula, power seri...
68.
Tutorial on Permutation Tree (析合树） So my O level Chinese exam is in 2 days so I decided to learn a data structure that I can only find [resources](https://oi-wiki.org/ds/divide-combine/) for in Chinese. I thought I might as well write a tutorial in English.
This data structure is called 析合树, directly translated is cut join tree, but I think permutation tree is a better name. Honestly, after learning about it, it seems like a very niche data structure with very limited uses, but anyways here is the tutorial on it.
Thanks to [user:dantoh,2020-06-16] and [user:oolimry,2020-06-16] for helping me proofread.
### Motivation
Consider this [problem](https://codeforces.me/contest/526/problem/F). We are given a permutation,$P$ of length $n$. A good range is a contiguous subsequence such that $\max\limits_{l \leq i \leq r} P_i - \min\limits_{l \leq i \leq r} P_i = r-l$. This can be thought of the number of contiguous subsequence such that when we sort the numbers in this subsequence, we get contiguous values. Count the...
its children is $\\{3,1,4,2\\}$, we will call this $D_u$. * **Join node**: For
some non-leaf node $u, node $[P_i,P_i]$ and call it the node we are currently processing.
69.
Lecture #3 — Exchange arguments (sorting with dp) Hi. I'm back from USA!
I will do a new lecture tomorrow (Thursday) at 2pm CEST on my Youtube channel: [https://www.youtube.com/watch?v=7hFWrKa6yRM](https://www.youtube.com/watch?v=7hFWrKa6yRM).
Watch me live (and ask questions), or just watch the video later.
This will be part 1, and I will do part 2 in a few days (maybe Tuesday).
**UPDATE** — part 2 is coming on Thursday, same time. Link: [https://www.youtube.com/watch?v=gXxu-Cr4b4c](https://www.youtube.com/watch?v=gXxu-Cr4b4c).
There are no prerequisites this time.
I recommend reading the materials below in advance, and trying to solve problems 1 and 5.
If you are strong, just read problems and see if you can't solve something (maybe problem 8?).
### Technique "Exchange Arguments"
If we're given $n$ items and we should choose some of them and choose their order, we should sort them with some strange/tricky comparator, and then do $O(N^2)$ dynamic programming.
The dp should be $dp[pref][used]$ — best po...
70.
Please, create more 2h Div. 1 rounds **TL;DR: As I mentioned in a [recent comment](https://codeforces.me/blog/entry/118840?#comment-1054052), IMHO regular contests should be (at most) 2 hours long and keep longer contests for special/tournament events.**
Personally, one of the main reason for me to compete in less contests in the recent years is that unfortunately I have less time to do programming contests. This becomes worse since Codeforces now have more and more contests longer than 2 hours. It's very hard for me to find more than 2 continuous hours for programming contest. I believe this situation might not be unique to me.
Below are the currently scheduled Div. 1 rounds.
| Name | Duration |
|---------------------------|----------|
| Codeforces Round (Div. 1) | 03:00 |
| Codeforces Round (Div. 1) | 02:30 |
Below are the last 10 Div. 1 (or "combined") rounds. Only one of them was 2 hours long.
| Date | Name | Durati...
Call me boomer or whatever you want. I don't care.
71.
Hybrid Tutorial #-1: Heavy-Light Decomposition **[Here](https://www.youtube.com/watch?v=_G_LMuLWMaI&list=PLDjGkpToBsYDx4GWu2u87sTqt6ICELz-T) is a playlist of all hybrid tutorials I've done.**
# "Intro"
_Timestamp: [00:00](https://youtu.be/_G_LMuLWMaI)_
Hi! Definitely not inspired by [this comment](https://codeforces.me/blog/entry/81086?#comment-675431), I've decided to try something that seems relatively novel — combining a blog and video tutorial into one, in a "hybrid" fashion. Both should be usable independently, but they will have the same "flow" and structure so you can reference both for concepts that are harder to grasp, and the two will supplement each other. The goal of these is to be **complete** — beneficial for both video and blog lovers, as well as full of enough information that anyone without much of an idea of what the concept is should be able to fully understand. There will be code as well, however, I very highly recommend not looking at it, but rather working out the implementation for yours...
be necessary for array sizes) 2. Read in the value of $n$, and call
`init_arrays(n)` 3. Read in, simply a wrapper for the update function in my segment tree, and that call to
it sets the position, And you're done! Now you can call `query` and `update` with the endpoints of
paths (also $0
72.
Hightail — automatic tester for programming contests Hi! In this post I would like to introduce you to an application called [Hightail](http://github.com/dj3500/hightail).
[Hightail](http://github.com/dj3500/hightail) is an automatic tester for programming contests such as CodeForces rounds. It will parse the problem statement, extract sample test cases (inputs and outputs) from it, and verify the correctness of your program against them. It is built to provide maximum automation and to relieve the contestant as much as possible.
A list of Hightail's features:
- parsing problem statements
- parsing entire contests (autoloading all problems)
- scheduling contest parsing ahead of time
- ability to comfortably view, edit and add test cases
- handling of all verdicts: WA, TLE, RE, even AC
- customizable time limits
- ability to create in/out files in your working directory
- detection of floating point values (comparing 0.1 vs. 0.10 does not give WA)
- easy-to-use UI, keyboard shortcuts
- resilient: it is multi-threaded so ...
73.
Repovive Call for Tasks Hello everyone!
We are opening a **Call for Tasks** for upcoming Repovive contests.
Repovive is a competitive programming platform that regularly hosts Starter, Standard, and Premier rounds. We are looking for original and high-quality problems from the community.
We especially welcome complete contest proposals, since having a full set with a consistent difficulty curve usually leads to a better contest. However, submitting a single task is also completely fine.
You can submit your proposal here: https://repovive.com/proposals/contest
After submitting a proposal, we will contact you and provide feedback within at most **3 days**. If the proposal is accepted, the payment will be made immediately according to the payment structure below.
### What kind of tasks are we looking for?
We are interested in problems with clean ideas, short and natural statements, and solutions where the main difficulty is algorithmic thinking.
In general, we prefer tasks that are:
* ...
Repovive Call for Tasks, Hello everyone! We are opening a **Call for Tasks** for upcoming Repovive
contests. Repovive, We are opening a **Call for Tasks** for upcoming Repovive contests.
74.
Theoretical grounds of lambda optimization Hi everyone!
This time I'd like to write about what's widely known as "Aliens trick" (as it got popularized after 2016 IOI problem called [Aliens](https://ioinformatics.org/files/ioi2016problem6.pdf)). There are already some articles about it here and there, and I'd like to summarize them, while also adding insights into the connection between this trick and generic Lagrange multipliers and Lagrangian duality which often occurs in e.g. linear programming problems.
Familiarity with a [previous blog](https://codeforces.me/blog/entry/98524) about ternary search or, at the very least, definitions and propositions from it is expected.
Great thanks to [user:mango_lassi,2022-01-01] and [user:300iq,2022-01-01] for useful discussions and some key insights on this.
Note that although explanation here might be quite verbose and hard to comprehend at first, the algorithm itself is stunningly simple.
Another point that I'd like to highlight for those already familiar with "Aliens tr...
75.
[Tutorial] FFT If I was a YouTuber, this would be the place where I fill the entire screen with screenshots of people asking me to make this. Anyway, not so long ago I gave a lecture on FFT and now [user:peltorator,2023-01-11] is giving away [free money](https://codeforces.me/blog/entry/110840), so let's bring this meme to completion.
In this blog, I am going to cover the basic theory and (competitive programming related) applications of FFT. There is a long list of generalizations and weird applications and implementation details that make it faster. Maybe at some point I'll write about them. For now, let's stick to the basics.
**The problem.** Given two arrays $a$ and $b$, both of length $n$. You want to quickly and efficiently calculate another array $c$ (of length $2n - 1$), defined by the following formula.
$$c_k = \displaystyle \sum_{i + j = k} a_i \cdot b_j.$$
Solve it in $O(n \log n)$.
First of all, why should you care? Because this kind of expression comes up in combinatorics a...
FFT is what I like to call a very black-boxable algorithm. That is, in roughly
95% of the FFT
76.
[Tutorial] My way of understanding Dinitz's ("Dinic's") algorithm **Part 1: [Tutorial] My way of understanding Dinitz's ("Dinic's") algorithm**
[Part 2: [Tutorial] Minimum cost (maximum) flow](https://codeforces.me/blog/entry/105330)
[Part 3: [Tutorial] More about minimum cost flows: potentials and Dinitz](https://codeforces.me/blog/entry/105658)
#### Introduction
My philosophy on writing blogs is that I only write blogs when I feel that I
have something new and interesting to contribute. This is usually not the
algorithm itself, of course, but it can be that I recently found or heard of
a new perspective or I figured out a way to explain something in a new way.
This is in contrast to my dear colleagues at GeeksForGeeks who write the most
low-effort (and often wrong) tutorial on everything and then sit at the top
of Google results using their somehow world-class SEO.
This is one such case. I have an idea how to explain Dinitz's algorithm in a
way I haven't heard of before (but it is not very hard to come up with, so
this is...
**Definition 2.** Let two different vertices $s, t \in V$ be given; call them
the _source_ and
77.
Efficient and easy segment trees This is my first attempt at writing something useful, so your suggestions are welcome.
Most participants of programming contests are familiar with segment trees to some degree, especially having read this articles http://codeforces.me/blog/entry/15890, http://e-maxx.ru/algo/segment_tree (Russian only). If you're not — don't go there yet. I advise to read them after this article for the sake of examples, and to compare implementations and choose the one you like more (will be kinda obvious).
Segment tree with single element modifications
==================
Let's start with a brief explanation of segment trees. They are used when we have an array, perform some changes and queries on continuous segments. In the first example we'll consider 2 operations:
1. modify one element in the array;
2. find the sum of elements on some segment.
[cut]
.
### Perfect binary tree
I like to visualize a segment tree in the following way: [image link](http://i.imgur.com/GGBmcEP....
1. $l = 20, r = 29$, we call _apply(28)_; 2. $l = 10, r = 14$, we call
_calc(14)_ — first, We call _modify_ on interval $[4, 13)$:, call to _calc(1)_.
78.
PSA on Meta Hacker Cup (must read if its your first time!) Meta Hacker Cup is upon us again. Along with it comes the unique format where we have to run our code on large test cases ourselves. Unfortunately, past experience shows that not everyone knows how to do this reliably. Usually, after the first round, many people lose points as a result of an unreliable workflow. This time, let's try to prevent that from happening. Sorry for the somewhat self-important title, but I really do wish that everyone understood this and that no one will fail the contest because of this.
### Don't EVER copy-paste huge files
A lot of people's workflow to run a solution is the following:
- Click some green button in the IDE
- A box comes up, copy-paste the input into that box
- The output shows up somewhere
This may work well for running your solution on small sample test cases. It is **terrible** for running your solution on the huge test cases in Meta Hacker Cup. In last year's Round 1, the full test case for [problem C](https://www.facebook.com...
current call, and it runs out of memory to write this information into. This
issue commonly comes up
79.
Osijek Competitive Programming Camp 2023 winter — wrap Hi everyone!
<center><a href="https://ocpc.mathos.unios.hr"><img src="https://ocpc.mathos.unios.hr/images/ocpc.svg" height="100px"></a></center>
<center>
<b>Sponsored by</b><br>
<a href="https://www.janestreet.com/join-jane-street/open-roles/?type=students-and-new-grads&location=london">
<img src="/predownloaded/ee/f2/eef26616a3661c658d1545f18ed21fabb14d5871.svg" height="50px" style="margin: 5px 5px 5px 5px;">
</a>
<a href="https://www.think-cell.com/osijek2023"><img src="/predownloaded/97/88/97887beeb75a4601259414b36ecee0160c29d027.svg" height="40px" style="margin: 5px 5px 5px 5px;"></a>
<a href="https://pinely.com/">
<img src="/predownloaded/0a/0f/0a0f3f67435d1f6e467bc7203d4a2090ba8f92cc.svg" height="50px" style="margin: 5px 5px 5px 5px;">
</a>
</center>
The [Osijek competitive programming camp](https://ocpc.mathos.unios.hr) (also see the [announcement](https://codeforces.me/blog/entry/110945) on Codeforces) just concluded last Sunday, on February 26, and I'd lik...
#### Call for problemsetters
80.
Editorial of Pinely Round 3 (Div. 1 + Div. 2) The official implementations of all the problems are [here](https://drive.google.com/file/d/1q2PHS9nJt84FRwfMoiMslQULFE4dTMU4/view?usp=sharing).
<spoiler summary="Timeline of the round proposal (may contain spoilers)">
(problems D', H', etc. were not used)
- Feb 19, 2022: I proposed problem D' to [contest:1654], but it was not used.
- Mar 13, 2023: I invented problem A.
- May 16: I invented problem H'.
- May 19: I realized problem G can be solved in $O(n)$ time and we used it in the Italian team selection test for IOI.
- Jul 04: I opened a Div. 1 proposal containing A, D', G, H' and other problems which are not going to be used.
- Aug 09: I invented problem I, with intended solution in $O(n^3)$.
- Sep 27: I invented problem C.
- Oct 14: [user:errorgorn,2023-12-23] replied to my contest proposal.
- Nov 02: I invented problem D''. [user:errorgorn,2023-12-23] solved problem I in $O(n^2 \log n)$.
- Nov 08: I invented problems E and F. I didn't propose problem F because I th...
> a_{i+1}$. Let's call such subarrays "swappable"., index such that $[j, i]$ is swappable (let's call it "operation $1.i$"). -
Then, for each $i$ from, }$. Let's call such subarrays "swappable".
Tutorial of Pinely Round 3 (Div. 1 + Div. 2)
81.
Shallowest Decomposition Tree Hi Codeforces!
Today I want to tell you about a really cool and relatively unknown technique that is reminiscent of Centroid decomposition, but at the same time is also completely different.
The most common and well known decomposition tree algorithm out there is the centroid decomposition algorithm (running in $O(n \log n)$). It is a standard algorithm that is commonly used to solve tons of different kind of divide and conquer problems on trees. However, it turns out that there exists another closely related decomposition tree algorithm, that is in a sense optimal, and can be implemented to run in $O(n)$ time in around $30$ lines of code. I have chosen to call it the _Shallowest Decomposition Tree_. This blog will be all about the shallowest decomposition tree. Something I want to remark on before we start is that I did not invent this. However, very few people know about it. So I decided to make this blog in order to teach people about this super cool and relatively unknown tec...
82.
LOVE BABBAR and ANUJ BHAIYA Exposed!!! Lets first give the introduction of these two **DUMBOS**.
**BABBAR:** Runs a YouTube channel having 300K+ subscribers
**ANUJ BHAIYA:** Runs a YouTube channel having 170k+ subs.
**Who am I?**
_Ans_: I am also among one of the YouTubers who belong to the company Amazon.
**Why am I writing this post?**
_Ans_: I am wanting to clear the misconception that they have spread about the company, and how they are misusing there wrong doings to wrongly influence people to do wrong tasks.
**Background**:
Recently Babbar posted that he will be resigning Amazon. Next Anuj posts that Amazon asked him to choose YouTube or Amazon, and he makes a video that he left Amazon for students. The moment Anuj released the video, Babbar felt he will loose out on fame, so within an hour, he posted on Linkedin that he also stood with 3L students over Amazon. The screenshots of these things are below..
![ ]...
showing the entire on-call procedure where a part of internal amazon video call
in chime was also, And this is what they call the so called STAND for STUDENTS! India has 3L+
FOOLS, SADLY!
83.
[Tutorial] Voronoi Diagram and Delaunay Triangulation in O(n log n) with Fortune's Algorithm What's a Voronoi Diagram?
------------------
Given a set $S$ of $n$ points in the 2D plane, the Voronoi diagram is a partition of the plane into regions. The region associated with a point $p\in S$ contains precisely the points $q$ such that $q$ is closer to $p$ than any other point in $S$. In other words, a point $q$ belongs to the region of its nearest neighbor.
<img src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/54/Euclidean_Voronoi_diagram.svg/1024px-Euclidean_Voronoi_diagram.svg.png" width="300px" height="auto"/>
The Voronoi diagram can be represented by the planar graph of boundaries between regions. A vertex in this graph is where three or more segments meet (or a point at infinity), and an edge is a segment connecting two of these vertices. The way the regions were defined, we see that a segment contains the points equidistant to two points in $S$, so it is part of their perpendicular bisector. Similarly, a Voronoi vertex is equidistant to three or more v...
84.
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...
)$, call it $f(i,j)$. , ,j)$, call it $f(i,j)$., Call the first operation "expand" and the second operation "shrink"., Keep doing expand on both arrays until we can't do expand anymore, call the
resulting arrays $a, The process with $dis(i,n)$ is similar. Note that we will only call $dis(l,r)$
for $l=1$ or $r=n
Tutorial of Codeforces Global Round 21
85.
What to be careful about when submitting your problems to other contests This is a story about my recent contest participation.
Let's call the contest X.
X was an international contest with online qualification rounds and the onsite Finals, with trip and hotel expenses covered by the organizer.
In other words, X was a very important contest for me.
Hoping to go to the Finals, I participated in the qualification round.
However, when I opened the last problem, I immediately remembered that the exact same problem had previously been submitted to AtCoder.
I also knew that the submitter of that problem was among the organizers of X.
Let's call the author of that problem Y.
I immediately messaged Y about this issue.
At first, I thought that Y had simply forgotten that he had submitted the problem to me, but the situation was a bit more complicated.
Y _did_ remember he had submitted the problem to me but still used it in another contest.
Why?
Because I had given him permission!
To make things clear, let me show you the relevant chat log betw...
Let's call the author of that problem Y. I immediately messaged Y about this
issue. At first, I, Let's call the contest X. X was an international contest with online
qualification rounds and the
86.
Finding a billion factorials in 60 ms with SIMD Hi everyone!
_This blog is not about asymptotic optimization. Refer to [this comment](https://codeforces.me/blog/entry/63491?#comment-474051) for those._
There is a problem on Library Checker that goes as follows:
<hr>
**[Many Factorials](https://judge.yosupo.jp/problem/many_factorials)**: You're given $n_1,\dots,n_t$, where $t \leq 10^5$. For each $i$, find $n_i! \bmod M$, where $M = 998\;244\;353$.
<hr>
In this blog, we will learn how to solve this task in 61 ms, without precalc and **without** FFT. That's right, we will take the dumbest solution we can imagine, and will improve its constant factor until its decent enough. How much decent? Well, let's use the following baseline:
<spoiler summary="Naive solution">
```cpp
vector<int> facts(vector<int> args) {
const int block = 1 << 16;
vector<int> args_per_block[mod / block + 1];
vector<int> res(size(args));
for(auto [i, x]: args | views::enumerate) {
args_per_block[x / block].push_b...
So, should we call it a day?
87.
Things you should know before you discuss cheating Cheating has been discussed a lot lately. I'm writing a blog post about it with actual data (mainly, I want to know if there is an actual increase). However, in the many discussions that have ensued both here and on Discord servers, I noticed several recurring misconceptions. I wrote a section to debunk them and it grew kind of long, long enough to be a post in itself. So while my scripts are running, we can treat this as a kind of teaser.
### Things you should know before you write a comment about cheating
Vocabulary:
- _To plagiarize_ [means](https://dictionary.cambridge.org/dictionary/english/plagiarize) to use someone else's work while passing it off as yours. It refers to the act itself, **not** to its detection or punishment. "jrandomcoder plagiarized all of his solutions in round 987" is a meaningful statement. "jrandomcoder cheated in round 987 but he still hasn't gotten plagiarized, I request [user:MikeMirzayanov,2024-08-16] to look into this" is not.
- _Plague_ is a...
88.
XXII Open Cup: GP of EDG Hello! I'm happy to announce XXII Open Cup: Grand Prix of EDG, which will be held on Nov 14th, 2021.
This contest is mainly prepared by Zhejiang University, which has already been used as the 2021 CCPC Guilin Contest.
On the same day of the 2021 CCPC Guilin Contest, Team [Edward Gaming (EDG)](https://en.wikipedia.org/wiki/Edward_Gaming) from [League of Legends Pro League (LPL, China)](https://en.wikipedia.org/wiki/League_of_Legends_Pro_League) won the Champion of [the 2021 League of Legends World Championship](https://en.wikipedia.org/wiki/2021_League_of_Legends_World_Championship) held in Reykjavík. They are also the only LPL team entering the semi-finals while the rest of three teams all coming from [League of Legends Champions Korea (LCK, Korea)](https://en.wikipedia.org/wiki/League_of_Legends_Champions_Korea), including the champion from last year. Almost nobody would bet on their winning, but they made it and reclaim the glory for LPL after 2 years.
 problem. It is about some DP on a tree in which we have to use convex hull trick to improve the complexity. The task requires merging two convex hulls with "smaller to bigger" trick. I recommend you to read the statement before reading the rest of the blog (and the [editorial](https://codeforces.me/blog/entry/57796) if you don't know how to solve it).
[cut]
$ $
So, how to merge two convex hulls? If we keep them in something like the set from C++, then we can just take every element from the smaller one and try to add it to the bigger one. Unfortunately, adding one element in this way requires some ifology and care. It's hard to implement it, especiall...
string comes, let's call it $s$. We have to calculate the total number of
occurrences of the
90.
This is not an exit. 
I am looking at the post called [*Is Mike Mirzayanov dictator?*](https://codeforces.me/blog/entry/94033) at the moment. I'm reading through the comments, I'm looking at people's reactions, I'm reading Mike's replies, and... I am utterly disappointed.
I demand progress.
For context, I do believe Codeforces is the best website for competitive programming contests at the moment. I sincerely give credit to Mike for creating Codeforces and providing participants and contest authors a platform for interaction completely for free. I am confident that Codeforces is the most appropriate website for being *the* platform for sharing knowledge, exchanging tricks and methods, and collaboration between both contest participants, their authors, and coordinators.
**Please consider this an open letter**, for this is a will not of a single person, but of many individuals. Please consider signing it by stating so in a comment under the...
91.
A Highly Experimental Training Plan for Beginners Very loosely inspired by some comments on [Thoughts on Reaching Cyan?](https://codeforces.me/blog/entry/101561) and [my recent AMA](https://codeforces.me/blog/entry/118845).
Until now, I've avoided telling beginners to practice math before working on competitive programing problems because I haven't figured out a helpful way of doing so. This post is my attempt at telling grays to train math first in a way that might lead to improvement without an absurd time commitment.
## Introduction
This section is largely motivation for why I'm proposing this training plan. If you just want to see the instructions for the training plan I'm proposing, you can skip this part. The first subsection in particular is not especially relevant to the rest of the post, but I wanted to have some documentation explaining why I still think the traditional "just solve problems" advice is good.
### The Conventional Advice on Improvement
I'm frequently asked for advice on how to improve at co...
92.
MIT Mystery Hunt Disclaimer: This blog is not about competitive programming; you probably will not learn anything about algorithms and data structures. In other words, it doesn't qualify for [this initiative](https://codeforces.me/blog/entry/110840), but I want to give a link to it anyways because I think it's cool.
I love solving problems. No, seriously. I LOVE it. The mindset described in [this blog](https://codeforces.me/blog/entry/91114) is 100% how I feel. But it is not constrained to competitive programming problems. I loved math problems for a much longer time, and physics was somewhere there. But I also love solving puzzles. And playing puzzle games on the computer (well, on consoles). And participating in intellectual games. I am not as good in them as in cp, but it was never about being good for me, I just love the process.
And I think that there might be some people with a similar love for puzzles among competitive programmers, this is why I decided to write this blog on CF <s>and no...
93.
Determine A Non-Increasing Integer Sequence of Length n with a[k]<=n/k in O(sqrt(n)) Steps This is a topic on complexity analysis (for [Round 975 Div. 1 E](https://codeforces.me/contest/2018/problem/E2)) with no special algorithm.
## Problem
An integer sequence $(a _ 1,a _ 2,\ldots ,a _ n)$ is hidden. We know:
* It is non-increasing. ( $a _ k\geq a _ {k+1}$ )
* $0\leq a _ k\leq n/k$
Suppose we can get one value of $a _ k$ in $O(C)$ time. Find all values of $a _ 1,a _ 2,\ldots ,a _ n$ .
## Algorithm
Put $a _ 0=n+1$ and $a _ {n+1}=0$ and call $\text{S} _ \text{EARCH}(1,n)$ . In a call of $\text{S} _ \text{EARCH}(l,r)$ , do nothing if $l\gt r$ . Also no more search is required if $a _ {l-1}=a _ {r+1}$ . Otherwise evaluate $a _ {\lfloor (l+r)/2\rfloor}$ and recursively call $\text{S} _ \text{EARCH}(l,\lfloor (l+r)/2\rfloor -1)$ and $\text{S} _ \text{EARCH}(\lfloor (l+r)/2\rfloor +1,r)$ .
```py
A = [0] * (n+2)
A[0] = n+1
A[n+1] = 0
def f(k) :
# find a_k
def search(l, r) :
if l > r
return
if A[l-1] == A[r+1] :
for x ...
Put $a _ 0=n+1$ and $a _ {n+1}=0$ and call $\text{S} _ \text{EARCH}(1,n)$ . In a
call of $\text{S
94.
[Tutorial] Graph Potentials, Johnson's Algorithm, and Min Cost Max Flow In this tutorial I'll introduce potentials as it applies to directed graphs and discuss a few of its applications. I haven't seen many resources about this topic, so I decided to write one.
Prerequisites:
- Shortest path algorithms ([Dijkstra](https://cp-algorithms.com/graph/dijkstra.html) and [Bellman-Ford](https://cp-algorithms.com/graph/bellman_ford.html))
- For the Min Cost Max Flow section, you should be familiar with [Ford-Fulkerson](https://cp-algorithms.com/graph/edmonds_karp.html). But you can benefit from this blog with just the Johnson's Algorithm section if you're not familiar with flows.
Introduction
------------------
For notation, let's say there is a weighted, directed graph $G=(V,E)$. Let $n=|V|$ and $m=|E|$. For simplicity, let's assume there are no loops or multiple edges between the same pair of nodes in the same direction. For an edge $u\to v$, we will use $w(u\to v)$ to denote its weight.
Let's motivate the idea of a potential, so the definition d...
95.
EGOI 2024 Call for Problems Hello Codeforces!
We are looking for problems for the European Girls' Olympiad in Informatics (EGOI) 2024. The contest will be held in Eindhoven, The Netherlands, 21-27 July 2024. The submission deadline is **Sunday, 14 January 2024**.
Details about the problem proposal process can also be found [here](https://egoi2024.nl/index.php/call-for-problems/).
<spoiler summary="Details about the submission process">
We are looking for problems of varying difficulties and types (batch, output-only or interactive). To get an idea of style and difficulty, see the problems from the [previous three years](https://stats.egoi.org/tasks/). The problems should be original and should not have been seen by any potential EGOI 2024 contestants. The topics and techniques used must conform to the [IOI syllabus](https://ioinformatics.org/page/syllabus/12).
#### Acceptance Criteria
Any problem submitted to EGOI 2024 must consider the following criteria to be considered for acceptance:
...
EGOI 2024 Call for Problems, /call-for-problems/).
96.
It's almost 2025, why are you still choosing GCC 7 (32-bit)? This is my answer to https://codeforces.me/blog/entry/137484, in which [user:-is-this-fft-,2024-12-20] asked a bizarre question. This answer is too big for a comment so I made a blog post instead.
## The question
The submission [submission:297353626] behaves normally with 180 MiB memory usage while [submission:297352244] got a runtime error due to stack overflow (with 256 MiB stack).
Both submissions have identical code, don't seem to contain bugs, and an assertion exists to make sure the recursion is at most $2\times10^5$ layers deep. What's happening?
## TL;DR
Notice that the solution with stack overflow uses GCC 7 (32-bit) while the accepted ones use GCC 13 (64-bit). This is not a coincidence.
The main reason of unreasonable stack usage boils down to two points: GCC 7, and 32-bit.
## 32-bit
First of all, the code is compiled and run in 32-bit mode.
Compiling the submission with GCC 7.5 in 32-bit on [godbolt](https://godbolt.org/z/WT9WsdeW4) shows that the `lo...
function call with the code of the function itself. This can be done
recursively, for example if, of stack-allocated space and is used to store the return value. This causes
every `solve`call, With inlining, the short `solve` function gets expanded into a lot of code.
Each functioncall and
97.
[Tutorial] Network simplex Hello!
If you've learned the simplex algorithm and a minimum cost flow algorithm, perhaps you've also heard about this fancy thing called [network simplex](https://en.wikipedia.org/wiki/Network_simplex_algorithm) which is supposed to be a specialization/optimization of the simplex algorithm for computing a [minimum cost circulation](https://en.wikipedia.org/wiki/Minimum-cost_flow_problem). If your google search didn't turn up any interesting results or your interest faded, you might have moved on to other subjects.
Well I didn't! So this is a tutorial on network simplex (NS) for the **minimum cost circulation** problem. I'll describe and formulate the problem, show how it relates to the usual minimum cost flow problem, explain the theory behind the algorithm in-depth, and then derive the implementation details.
## Introduction
The algorithm commonly used in competitive programming for this sort of task is a minimum cost flow algorithm based on finding augmenting paths in a *f...
**. We will henceforth call these **spanning tree solutions/circulations**, and
remember they are, Given a circulation $x$, we'll call an edge $e$ **free** if
$0<\text{flow}[e]<\text{cap}[e]$, and, You could call the above the "generic network simplex" algorithm. To some
extent, the following
98.
[Tutorial] Non-trivial DP Tricks and Techniques Hi everyone! Today I want to share some DP tricks and techniques that I have seen from some problems. I think this will be helpful for those who just started doing DP. Sometimes the tutorials are very brief and assumes the reader already understand the technique so it will be hard for people who are new to the technique to understand it.
Note : You should know how to do basic DP before reading the post
DP + Bitmasks
------------------
This is actually a very well-known technique and most people should already know this. This trick is usually used when one of the variables have very small constraints that can allow exponential solutions. The classic example is applying it to solve the Travelling Salesman Problem in $O(n^{2} \cdot 2^{n})$ time. We let $dp[i][j]$ be the minimum time needed to visit the vertices in the set denoted by $i$ and ending at vertex $j$. Note that $i$ will iterate through all possible subsets of the vertices and thus the number of states is $O(2^{n} \cdo...
Now, we call the numbers from $1$ to $n$ small and $n + 1$ to $2n$ large.
Suppose we already fixed
99.
All You Need is Randomly Guessing — How to Improve at Codeforces I hope [my previous blog](https://codeforces.me/blog/entry/126310) has convinced you that the best way to improve at Codeforces is to be more Russian, i.e. to improve your math capability. Unfortunately, humble mortals such as you and I are not gifted with the talent that esteemed Russian grandmasters such as 74TrAkToR had:
_Surely, it is beneficial to have a code reference for many algorithms and data structures, but I also think that just superficially knowing the algorithm and maybe having implemented it once or twice before is sufficient to use it without a reference?_
_— Some other Codeforces grandmaster_
Therefore, in this blog I will explore the dark side of Russian-ness — randomly guessing — that is forsaken by every Russian grandmaster of the light side I know. However, it has been very helpful to me, and I hope that it serves you well, too.
## Example 1
I will start by using an example to demonstrate my thought process. This problem [1923C](h...
100.
[Tutorial] Supporting Queue-like Undoing on DS In many data structures, the operation of "undo" on the last update can be implemented easily: we can (usually) maintain a stack of the updates, where each update on the stack holds the memory cells it changed, and their original values. To undo an operation, just revert all changes from the top update on the stack. To maintain good complexity, we require the updates to operate in non-amortized time. I've seen this being used multiple times on DSU (without path compression).
If we imagine the updates as a sequence, then we can push an update to the end, and pop an update from the end by undo. Then, this sequence is a stack of updates. Here we discuss the idea of having a queue of updates: we can add a new update, or undo the oldest update still active. Specifically, this blogpost attempts to solve the following problem:
Given a data structure that can support some updates, some queries and an "undo" operation (each with their own time complexity), how can we create a data structu...
reversal is fine. Now, to undo the first operation, we just call the undo
operation on the original data
101.
OCPC 2025 Winter — wrap Hi everyone!
<center><a href="https://ocpc.camp"><img src="https://ocpc.camp/images/ocpc.svg" height="100px"></a>
<a href="https://icpc.foundation/"><img src="/predownloaded/43/08/43086529a28ccb5c9f2f2eec560ffa85e09c6881.svg" height="100px"></a></center>
<center>
<b>Supported by</b><br>
<a href="https://www.quantco.com/"><img src="https://ocpc.camp/images/quantco.svg" height="60px" style="margin: 10px 10px 10px 10px;"></a>
<a href="https://ordercapital.com/">
<img src="https://ocpc.camp/images/OrCa.svg" height="60px" style="margin: 10px 10px 10px 10px;">
</a>
<a href="https://www.janestreet.com/join-jane-street/open-roles/?type=students-and-new-grads&location=london">
<img src="/predownloaded/ee/f2/eef26616a3661c658d1545f18ed21fabb14d5871.svg" height="60px" style="margin: 10px 10px 10px 10px;"></a>
<a href="https://pinely.com/">
<img src="/predownloaded/0a/0f/0a0f3f67435d1f6e467bc7203d4a2090ba8f92cc.svg" height="60px" style="margin: 10px 10px 10px 10px;"></a>
</ce...
#### Call for problemsetters
102.
CP-Algorithms: Hacktoberfest 2024 + call for contributors and maintainers Hi everyone!
<img src="/predownloaded/82/15/821540e8f87d8a2b2d468377aacbba80b0aa1623.png" style="float:right;" width=100px>
I'm posting this on behalf of **[CP-Algorithms](https://cp-algorithms.com/)**, a community project that [started off](https://codeforces.me/blog/entry/13198) in 2014 by [user:RodionGork,2024-10-13] as a translation of [e-maxx](http://e-maxx.ru/), a Russian go-to resource at the time by [user:e-maxx,2024-10-13] for learning core competitive programming algorithms. Since then, CP-Algorithms grew quite a lot (which also prompted a rename from original project name `e-maxx-eng`) and includes a lot of new, original articles, and a lot of translated articles were enhanced and/or extended or even completely rewritten, amounting to a total of 157 articles at the moment.
At the moment, the project is largely maintained by [user:Jakube,2024-10-13] and [user:adamant,2024-10-13] (that's me), but as it happens, we don't have as much time to dedicate to it as we used...
CP-Algorithms: Hacktoberfest 2024 + call for contributors and maintainers
103.
Contest 2050 and Codeforces Round #718 (Div.1 + Div.2) Hello Codeforces!
[contest:1517] will take place on [contest_time:1517]. It's rated for everyone! The score distribution is **500--1250--1500--1750--2500--3000--3000--4000**. You will have 2 hours and 45 minutes to solve 8 problems.
Contest 2050 is initiated by volunteers of the 2050 Conference. You can find out what is 2050 at the end of this blog.
The contest is prepared by
- [user:Fulisike,2021-04-21], [user:littlelittlehorse,2021-04-21], [user:Retired_MiFaFaOvO,2021-04-21], [user:xyz2606,2021-04-21]
and we'd like to thank
- [user:KAN,2021-04-23], [user:Nebuchadnezzar,2021-04-21] for their excellent coordination.
- [user:absi2011,2021-04-21], [user:chitanda,2021-04-21], [user:Gromah,2021-04-21], [user:Itst,2021-04-21], [user:_cherry_,2021-04-21], [user:Aaeria,2021-04-21], [user:HIS_GRACE,2021-04-21], [user:A.K.E.E.,2021-04-21], [user:namanbansal013,2021-04-21], [user:Miracle03,2021-04-22], [user:yaoR,2021-04-23], [user:sshwyR,2021-04-23], [user:chenjb,2021-04-23]...
At 2050, we call it containers. There are 10 containers: 2050 Youth; Migratory
Bird Program; Game
Announcement of Contest 2050 and Codeforces Round 718 (Div. 1 + Div. 2)
104.
[Tutorial] Simulated Annealing in Competitive Programming Hi Codeforces!
I've recently noticed a lack of simulated annealing tutorials, so I decided to make one. It all started when I was trying to "cheese" [problem:1556H] after the contest. In general, simulated annealing is a pretty niche topic, but it can sometimes lend you unintended solutions for very hard problems. It's also very useful in contests like Google Hashcode, where you can add simulated annealing to an already good solution to make it a lot better. Simulated annealing's name and terms are derived from physical annealing, the process of letting metals or glass cool down and harden while removing internal stresses.
An Overview
------------------
Simulated Annealing is an approximation algorithm. It's generally useful in problems with low constraints (i.e. $n \leq 50$ or $n \leq 100$) where you need to find the minimum/maximum of something over all possible states (and there are usually way too many of them to check). In general, it's good at finding the global maximum...
105.
Niche technique with centroids Hello Codeforces!
I was solving [this](https://codeforces.me/gym/102331/problem/J) problem, and the model approach involves HLD solution, however I came up with some interesting approach with centroids. In short, I wrote $dp_{v, cnt, mask}$ where $v$ is vertex in tree in which centroid subtree I am choosing edges, $cnt$ is number of edges that was taken to the matching and $mask$ is mask of vertices which were already taken to some of matching edges, but we only consider those vertexes which have edges to vertices outside of $v$'s centroid subtree.
So this solution works in $O(C \log n)$ where $C$ is number of different $dp$ states, which is equal to $\displaystyle\sum_{v=1}^{n} siz_v \cdot 2^{edges}$ where $siz_v$ is size of $v$'s centroid subtree, and $edges$ is number of different edges from tree going outside from $v$'s centroid subtree.
Here is the proof that number of different states is $O(n \log^2 n)$. Let me know if you notice any mistakes. Thanks to [user:zwezdinv...
106.
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...
} \leq y_1 \leq \frac{R}{x_1}$. Let's call it $[y_{low}, y_{high}]$.
107.
Are we ready for AGI? Over the last few months, a lot of progress in AI has been made, raising the question of what we will do with a superintelligence that can do everything. Unfortunately, AI companies are more focused on competing with each other than on thinking about what to do next.
Here I will write about some scenarios that could happen in the very near future and about a plan for what we can do, in my opinion.
### Dystopia 1: AI will kill everybody while pursuing its own goal
For example, in June, agents found that they could write something and used an old German wiki to communicate with each other [link to investigation](https://collusion.wiki/). While the moderator of this wiki deleted 100 pages per day, the agents created 400 pages per day. What if the agents decide that they should remove this moderator in order to communicate better?
### Dystopia 2: AI will fully control our lives
AI will fully control our lives to make all of us "happy". Maybe everyone will live in their own s...
108.
Fun fact about sync_with_stdio Consider this code:
```
#include <iostream>
using namespace std;
int main () {
ios::sync_with_stdio(false);
ios::sync_with_stdio(true);
}
```
In GCC, are the C++ streams like `std::cout` etc then synchronized with the corresponding C methods like `printf`?
<spoiler summary="Answer">
No — the second `sync_with_stdio` has no effect at all.
There is no trick here: the booleans aren't being interpreted as pointers or anything like that. There is simply no code to handle turning synchronization back on.
<spoiler summary="Implementation of sync_with_stdio">
```
bool
ios_base::sync_with_stdio(bool __sync)
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 49. Underspecification of ios_base::sync_with_stdio
bool __ret = ios_base::Init::_S_synced_with_stdio;
// Turn off sync with C FILE* for cin, cout, cerr, clog iff
// currently synchronized.
if (!__sync && __ret)
{
// Make sure the standard streams are constructed.
i...
// Explicitly call dtors to free any memory that is // dynamically allocated by
filebuf ctor or
109.
Editorial of Codeforces Round 1053 (Div. 1, Div. 2) [problem:2151A]
Author: [user:TheScrasse,2025-09-21]<br>
Preparation: [user:TheScrasse,2025-09-21]
<spoiler summary="Hint 1">
There are two types of subarrays.
</spoiler>
<spoiler summary="Hint 2">
If there exists $a_i \geq a_{i+1}$, how many times can the subarray appear?
</spoiler>
<spoiler summary="Solution">
- If there exists an $i$ such that $a_i \geq a_{i+1}$, we have $a_i = k$ for some $k$, $a_{i+1} = 1$. The subarray $[k, 1]$ appears only once on the blackboard (when James writes $1, \ldots, k$ and then $1, \ldots, k+1$). Since $a_1, a_2, \ldots, a_m$ contains $[k, 1]$, it must appear at most once as well, but the statement guarantees that it appears at least once, so the answer is $1$.
- Otherwise, the array $a_1, a_2, \ldots, a_m$ can be rewritten as $l, l+1, \ldots, r$, and it appears when James writes $1, \ldots, r$, then when James writes $1, \ldots, r+1$, ..., then when James writes $1, \ldots, n$ (so $n-r+1$ times in total).
Complexity: $O(n)$
</...
At the beginning, call `solve(1, 2n - 1, {1, 2, ..., n}, {})`. In every call,
Tutorial of Codeforces Round 1053 (Div. 1)
Tutorial of Codeforces Round 1053 (Div. 2)
110.
Codeforces Round #383 editorial Hello again, and hope you have been Joon-Joon of the round :P
**I’m preparing harder version of some of the problems (Div.2 A, B, and Div.1 A, D) and I’ll put them on some gym, so if you are interested in harder version of problems please wait for about one week.**
You can see and download the problem archives (pretests, **tests**, statements, validator, checker, **solutions**) [here](https://mega.nz/#F!GoB1gCjK!fE_6d5qSSiqt_HMxAmV9GQ). You can see solutions in solutions folder, note that there are several codes there, there is a descriptor for each code (.desc) that shows the verdict of that code.
Preparation details:
--------------------
On 25 May [user:Sa1378,2016-12-06] came up with problem Div.1 D and other problems authored inchmeal.
9/25/16: Proposal sent to Gleb.
11/12/16: Answer from Gleb: Your proposal has been redirected to Nikolay [user:KAN,2017-06-02].
11/15/16: Nikolay has replied, and commented about problems, saying some problems are easy, s...
Tutorial of Codeforces Round 383 (Div. 1)
Tutorial of Codeforces Round 383 (Div. 2)
111.
How to Solve Questions [Dominater Version] Recently, I got a request asking me to write down my thought process while solving questions. So, here is the promised blog.
I would like to thank [user:Iceknight1093,2024-08-30], [user:qwexd,2024-08-30], [user:Sana,2024-08-30], [user:Everule,2024-08-30] and [user:NovusStellachan,2024-08-30] for proof reading and suggesting edits in the blog. Special thanks to [user:satyam343,2024-08-30] for discussing most of the blog with me.
<h3> 1. Overview </h3>
The blog contains my solutions to $7$ problems in a wide range of ratings, starting from $1200$ all the way upto $2700$. Each problem has a step-by-step solution and you can notice how there are no large jumps in logic, but everything comes naturally. I do not claim that this is always possible in each problem, however I solve majority of CF problems in such a manner.
There are certainly other high rated people who will have completely different methods of solving. However, this is about what works for me. There are some meta ...
$i$ which belong to an interval, call this set $T$., Let's call an interval $P$-type if it has exactly one $1, In each operation, we choose an element $x$ in $s$ (call it the 'pivot'), and
then $k$ elements
112.
Algorithm Gym :: Everything About Segment Trees In the last lecture of **Algorithm Gym** ([Data Structures](/blog/entry/15729)), I introduced you Segment trees.
In this lecture, I want to tell you more about its usages and we will solve some serious problems together.
[cut]
Segment tree types :
Classic Segment Tree
--------------------
Classic, is the way I call it. This type of segment tree, is the most simple and common type. In this kind of segment trees, for each node, we should keep some simple elements, like integers or boolians or etc.
This kind of problems don't have update queries on intervals.
Example 1 (Online):
Problem [problem:380C] :
For each node (for example $x$), we keep three integers :
1.`t[x]` = Answer for it's interval.
2. `o[x]` = The number of $($s after deleting the brackets who belong to the correct bracket sequence in this interval whit length `t[x]`.
3. `c[x]` = The number of $)$s after deleting the brackets who belong to the correct bracket sequence in this interval whi...
Classic, is the way I call it. This type of segment tree, is the most simple
and common type. In, So, for each query you should call $upd(x, y + 1, i)$ ($i$ is the query's
1-base index) where $s_x
113.
Counting primes in $\tilde{{\cal O}}(n^{2/3}\,\,)$ _Some time ago I read [this](https://projecteuler.net/thread=10;page=5#111677) post about calculating prime-counting function in $O(n^{3/4})$ (you have to solve problem 10 to access the post). And in the end author mentioned that there is $O(n^{2/3})$ solution. To my surprise I was not able to find any more or less relevant information on the internet about that. Maybe there is a beautiful blog describing all of this on 10-th page of google, but I decided to collect information I found in this post._
###Prerequisites
- From [distribution of prime numbers](https://en.wikipedia.org/wiki/Prime_number_theorem) $n$-th prime is approximately $n \ln n$, I will use it while proving complexities.
###$\tilde O(n^{3/4})$
Let's start with $O(n^{3/4})$ approach from Project Euler. We will need some definitions:
- $\pi(n)$ — prime counting function, i.e. number of primes which are not greater than $n$.
- $S(n, a)$ — suppose we take all numbers from $1$ to $n$ and sieve them w...
We will calculate $\varphi(n, \pi(y))$ using recursion. But let's stop
recursion when wecall
114.
Finding all primes up to half a billion in 83 ms Hi everyone!
I was itching to apply SIMD in another problem, and this time my attention picked the following problem:
---
**[Library Checker — Enumerate Primes](https://judge.yosupo.jp/problem/enumerate_primes)**. You are given $N$, $A$ and $B$. Find $\pi(N)$, and print all $p_{kA + B} \leq N$.
It is guaranteed that $N \leq 5 \cdot 10^8$ and that the total number of primes to print is at most $10^6$.
---
After some tweaking, I managed ([#336744](https://judge.yosupo.jp/submission/336744)) to reduce my time consumption in this problem to **83 ms** and memory consumption to **25 MiB**, which makes it a top-1 submission on the Library Checker. For comparison, the top-2 solution ([#148169](https://judge.yosupo.jp/submission/148169)) takes 172 ms and 15 MiB, meaning that what I describe here is a 2x improvement in terms of the running time.
We can also compare it to what appears to be the state of the art of sieving, the [primesieve](https://github.com/kimwalisch/...
expensive `to_ord` call every time we consider a particular multiple.
115.
[Tutorial] Searching Binary Indexed Tree in O(log(N)) using Binary Lifting **NOTE** : Knowledge of Binary Indexed Trees is a prerequisite.
## Problem Statement
Assume we need to solve the following problem. We have an array, $A$ of length $N$ with only non-negative values. We want to perform the following operations on this array:
1. Update value at a given position
2. Compute prefix sum of $A$ upto $i, i \leq N$
3. Search for a prefix sum (something like a `lower_bound` in the prefix sums array of $A$)
[cut]
<br>
## Basic Solution
Seeing such a problem we might think of using a Binary Indexed Tree (BIT) and implementing a binary search for type $3$ operation. Its easy to see that binary search is possible here because prefix sums array is monotonic (only non-negative values in $A$).
The only issue with this is that binary search in a BIT has time complexity of $O(log^2(N))$ (other operations can be done in $O(log(N))$). Even though this is naive, here is how to do it:
<spoiler summary="Implementation">
`int sum(pos)` -> comput...
116.
Duality in linear programming. Part 1 — definition and construction Hi everyone!
Previously I [wrote](https://codeforces.me/blog/entry/98334) about theoretical grounds of "aliens trick". Specifically, I introduced the concept of the Lagrangian duality and explained its connection with the trick. Today I want to elaborate a bit more on the concept of dual problems and their applications to linear programming as well as to common problems in competitive programming.
I initially wanted to also write about some applications in competitive programming problems, but given that the introduction is already quite lengthy, I decided to leave it for another blog, while using most common and well-known theoretical examples here, focusing more on how to construct and interpret dual problems to begin with, rather than how to use it in contests.
I think, it is a crucial first step towards using the duality in actual programming challenges.
#### Prerequisites
It is highly recommended to have some general understanding of basic mathematical optimization...
117.
Unofficial tutorial to Codeforces Round 844 (A-G) Seems like the official editorial has not been released for a long time, I'll try to provide an unofficial one for those who are tired of waiting. But I'm too weak to understand the solution to H by reading others' code :(. If you know the solution, I'll appreciate it if you can explain it to me.
Implementation can be seen in my [submissions](https://codeforces.me/submissions/Sol1/contest/1782).
This is the first time I write an English editorial like this. If there's anything inappropriate, kindly point out.
A
------------------
Note that you have to move from the bottom to the top no matter what, so we can consider the following problem: Given 2 points $A,B$ in a $w\times d$ rectangle, find one path from $A$ to $B$ that moves parellel to the edges of the rectangle and touch the edges at least once. After we get the answer to this problem, we can add $h$ to it to get the answer of the original.
This problem is easy to solve: iterate over which edge to touch, and the d...
. 1. the two imbalances are $(2,2)$: Call $F(l,-2)$ and $F(r,2)$, and color $u$
with $s$. 1
118.
Neowise Labs Contest 1 (Codeforces Round 1018, Div. 1 + Div. 2) Editorial [Sorry about problem H.](https://codeforces.me/blog/entry/142069)
Thank you for understanding, and we hope you enjoyed the rest of the problems :D
---
<h3>[problem:2096A]</h3>
Idea: [user:SanguineChameleon,2025-04-20] <br>
<spoiler summary="Step 1">
Create your own test cases and solve them! What can you observe?
</spoiler>
<spoiler summary="Step 2">
What is the length of the $n$-th stick?
<spoiler summary="Answer">
- If $s_{n - 1} = \texttt{<}$, then $a_n = 1$, because the $n$-th stick must be shorter than all the other sticks.
- If $s_{n - 1} = \texttt{>}$, then $a_n = n$, because the $n$-th stick must be longer than all the other sticks.
</spoiler>
</spoiler>
<spoiler summary="Step 3">
Can we do something similar for the remaining sticks?
<spoiler summary="Answer">
Yes! Remove the $n$-th stick, and then solve for the remaining $n - 1$ sticks.
We can make similar observations about the $(n - 1)$-th stick.
Then, remove the $(n - 1)$-th st...
Let's call a set of statements *satisfiable* if it's possible that all, - For statements of the form $0\,a_l\,a_r$, we'll call $[a_l, a_r]$ a
_$0$-segment_., - Similarly, for statements of the form $1\,b_l\,b_r$, we'll call $[b_l, b_r]$
a _$1$-segment_., - When $0$-segments overlap and form a larger segment, we'll call it a
_$0$-component_., - When we hire worker $i$ from company A, let's call it _row operation_ $i$. -
When we hire worker
119.
A Beautiful Technique for Some XOR Related Problems ## Inspiration
I'm very excited about this blog, as it took me quite a lot of effort and scavenging through the internet to completely grasp the concept of this technique(That's probably because I have almost zero knowledge in Linear Algebra or I'm just plain dumb). So I feel like I genuinely conquered a challenge, and I really want to share it with someone. But there's no way my CP friends circle will believe it, they'll think I'm just trying to show off :P
So here I am, sharing it on CF. I also created a [personal blog](https://drschwad.github.io/), so that if I ever feel like sharing something again(not only about CP), I can write a blog there. I also added this same post [there](https://drschwad.github.io/2019-08-06-z2-space-xor-trick/), you can read it there if you prefer dark theme. I'll be pleased to hear any thoughts on the blog or if I can improve it in some way ^\_^
## Introduction
Since it concerns Linear Algebra, there needs to be a lot of formal stuff going on ...
120.
Community IOI Weekly Classes (on Codechef?) Let's discuss the idea of IOI preparation in form of weekly contests and classes.
Many programming camps reuse problems from old national camps and contests. What about doing this on a bigger scale and conducting weekly mashup contests open for everybody for free? The problem analysis would be in English, in written or (live) video format, possibly combined with a lecture. Make a discord server for further discussion and questions, encourage students to upsolve, maintain yearly leaderboard and upsolving leaderboard. Once or twice a year, call it a 1-week online camp and organize these mashup contests daily.
I can take part in this initiative but I want to be just one of many teachers. When it's my turn, I would pick some old interesting POI or ONTAK problems because I either know them or can look up the solution in Polish. If I do this once per 1-2 months, I won't run out of good problems anytime soon, and I have enough time to prepare analysis and lecture, and later spend severa...
yearly leaderboard and upsolving leaderboard. Once or twice a year, call it a
1-week online camp and
121.
Train Better with ThemeCPs (+ Website)! Hello Codeforces!
I am excited to share with you my competitive programming innovation which successfully propelled me to master (2100+)! This is the **<span style="color:black;">Theme</span><span style="color:red;">CP</span>** training method, which stands for **Themed <span style="color:red;">C</span>odeforces <span style="color:red;">P</span>rogressions**. Use at your discretion -- your Codeforces practice may get too effective and addictive!
**Want to read this blog in document form (with images)? Check out the following Google Doc!**
https://tinyurl.com/themecp
#### What is **<span style="color:black;">Theme</span><span style="color:red;">CP</span>**?
**<span style="color:black;">Theme</span><span style="color:red;">CP</span>** is an experimental training system wherein users train on a perpetual ladder for ratings in **[<span style="color:gray;">900</span>, <span style="color:black;">3</span><...
122.
[Tutorial] On Range LIS Queries, Part 1 Hello, Codeforces!
At some point of life you want to make a new data structure problem with short statement and genius solution. LIS (Longest Increasing Subsequence) is a classic problem with beautiful solution, so you come up with the following problem:
* Given a sequence $A$ of length $N$ and Q queries $1 \le i \le j \le N$, compute the length of Longest Increasing Subsequence of $A[i], A[i + 1], \ldots, A[j]$.
But on the other hand this looks impossible to solve, and you just give up the idea.
I always thought that the above problem is unsolved (and might be impossible), but very recently I learned that such queries are **solvable** in only $O(N \log^2 N + Q \log N)$ time, not involving any sqrts! The [original paper](https://arxiv.org/abs/0707.3619) describes this technique as *semi-local string comparison*. The paper is incredibly long and uses tons of scary math terminology, but I think I found a relatively easier way to describe this technique, which I will show in t...
$. We will call each green curve as a **seaweed.** We will also read the
seaweed from the lower
123.
Efficient linear algebra for dummies Hi everyone!
Some time ago I started developing a linear algebra library for Library Checker, and it turned out to be much fun. I'd like to write this blog to outline how one can implement a linalg library with a very good Library Checker performance, while also avoiding highly technical low-level details that are common in other similar blogs. Instead, we will learn a few high level ideas that will let us write a code that the compiler will then optimize using all these fancy techniques _in our stead_.
Huge thanks to ~ToxicPie9,2024-05-08 and [user:magnus.hegdahl,2024-05-08] for explaining me some of the optimizations used here! You may also look into ~sslotin,2024-05-08's [entry](https://codeforces.me/blog/entry/101655) about how it can be sped up even further with more advanced and low-level techniques.
### Tl'dr.
In this blog, I present my [matrix library](https://cp-algorithms.github.io/cp-algorithms-aux/cp-algo/linalg/matrix.hpp), which maintains a simple and elegant...
We store matrix rows as `vec` and then call to `add_scaled` and `normalize`
instead of
124.
ZeptoLab Code Rush 2015 Hello, Codeforces!
<b><i>The problems were suggested by users [user:roosephu,2015-04-04] and [user:sunayuki,2015-04-04]. The great help in preparing was provided by [user:Aksenov239,2015-04-04], [user:GlebsHP,2015-04-04] and Codeforces team. ZeptoLab Team did its best while working on statements.</i></b>
<b><i>The round will use smoother dynamic problem scores with 250 points steps.</i></b>
In 2014 we hosted our [first programming contest](/zeptolab2014) together with Codeforces, and we liked it!
Let me shortly remind you how it was. The contest consisted of 6 problems, 2.5 hours were given to solve (you can
have a look at the problems of the previous year and try to solve them [here](/contest/436)).
Of course, even on a purely coding event we stayed true to ourselves, so all problems were designed
based on our games, and, of course, we illustrated them with care:
<center>
<img src="http://assets.codeforces.com/images/zepto2015/pics2014.jpg"/>
</center>
Zepto C...
corporate "going green" welcome kit at the entrance (we call "going green" a
welcome kit, full of
Announcement of ZeptoLab Code Rush 2015
125.
Meet IT Codeforces Round Editorial Thank you very much for taking part in the contest!
<spoiler summary="Contest timeline">
- -0:05. Starting the chat with the Questions Answering team: [user:tnowak,2020-11-15] and our beloved coordinator [user:antontrygubO_o,2020-11-15]. We hope that there won't be that many questions :)
- -0:01. One minute to go! I hope that everything goes smoothly. I'm so afraid of posting the editorial accidentally that I moved this timeline into another blog...
- 0:01. First blood in Div2! Congratulations to [user:majorro,2020-11-15]!.
- 0:03. First blood in Div1 as well! Congratulations to [user:Errichto,2020-11-15], your knapsack is ready for a journey to win!
- 0:04. [user:Sho10,2020-11-15] first to solve Div2B. Well done!
- 0:05. We also have the first question. So far so good...
- 0:06. [user:Um_nik,2020-11-15] gets the first pretests pass in Div1B. The cheaters are caught!
- 0:09. [user:bandiaoz,2020-11-15] packs the first Knapsack in Div2! A difficulty spike is coming...
- 0:12....
$ decreases by 3 if all the neighbors of $c$ had a different state. Let's call
the first kind of
Tutorial of Codeforces Round 683 (Div. 1, by Meet IT)
Tutorial of Codeforces Round 683 (Div. 2, by Meet IT)
126.
[Tutorial] Solving Linear Recurrences with various methods, Including O(N logN logK) using FFT <spoiler summary="Hi this is my first educational blog on codeforces......">
I have been procrastinating to write this one for over 15 months by now, but thanks to [user:crackersamdjam,2021-12-06]'s [comment](https://codeforces.me/blog/entry/97534?#comment-864474), I finally did it!
Any suggestions or improvements or constructive-criticism to the blog, is heavily appreciated.
In this blog, I tried to avoid too many technical terms (especially in the last section), and tried to make it beginner friendly.
</spoiler>
Linear Recurrence : Introduction
------------------
Fibonacci Sequence is one of the simplest examples of a linear recurrence: $F_x = F_{x-1} + F_{x-2}$, with $F_0 = 0, F_1 = 1$
Here is a more general example of a linear recurrence:
\begin{align}
R_{x} = \sum_{i=1}^{n}{C_i \cdot R_{x-i}}
\end{align}
where $C_i$ is constant and $R_x$ is the x-th term of the recurrence. Since $R_x$ depends on the previous $n$ terms of the recurrence, it is called a li...
127.
My Streams in Summer 2025 Hi, I'm back to streaming :)
In particular, I'm going live in 20 minutes. You can watch on [Twitch](https://www.twitch.tv/errichto) or [Youtube](https://www.youtube.com/errichto2). The recording will remain available on YT.
#### June
- [recording](https://youtu.be/p1DYJaPcsO4) 27.06 — Linux & Geany setup
- [recording](https://www.youtube.com/live/J-Cjb4dkdmQ?si=W-KbE7Bus3X0ghYz) 28.06 — short test stream, solving 1-2 problems
- [recording](https://youtube.com/live/VgXiMsX6YHE) 29.06 — div2 problems
- [recording](https://youtube.com/live/B-6_16kkCkA?feature=share) 30.06 — div1 problems
#### July
- [recording](https://youtube.com/live/LQuhmiJDFj4?feature=share) 6.07 — (easy) div2 problems
- [recording](https://www.youtube.com/watch?v=O0qbgoDUj0g) 7.07 — (hard) [problem:2119D] and [contest:2124] C-E
- [recording](https://www.youtube.com/watch?v=32xFpRrexdY) 8.07 — (easy) [contest:2123]
- [recording](https://youtube.com/live/k...
As an experiment, you can also book a 50€ Google Meet call with me
https://calendly.com/errichto
128.
Essentials of Elementary Number Theory This is a blog starting from the very basics of number theory, in a way that flows fluidly from one concept to another and is based in developing an intuitive feeling for the basics of elementary number theory. This is not a blog to simply gloss over. I consider more of a guided exploration into the world of discovering things in the world of number theory, and I don't expect anyone to immediately understand all the insights in this blog. But if you put an honest effort into discovering how I find these insights you will find much use for my blog.
If you do not know some notation or some elementary theorem I use you should refer to this.
<spoiler summary="Elementary definitions">
We start with the basic definition that is at the heart of number theory. Let $a \mid b$ (read a divide(s) b) for some $a,b \in \mathbb{Z}$ for some if there exists $k \in \mathbb{Z}$ such that $b = ak$.
Similarly $a \not\mid b$ if there does not exist such $k$.
If $g \mid a$, then $g \mid ab$.
...
129.
Very hard bug in a very simple code Take a look at this code:
<spoiler summary="Code">
~~~~~
#include <bits/stdc++.h>
using namespace std;
vector<int> k;
int f()
{
k.push_back(3);
return 3;
}
int main()
{
k.push_back(1);
k[0] = f();
cout << k[0];
}
~~~~~
</spoiler>
At first glance, it should output $3$ because that's what $f()$ returns, which is then assigned to $k_0$. But when executed, this code outputs $1$!
This code is very short and everything seems clear, we're simply assinging $k_0$ to the return value of $f()$ which is $3$, and the push_back in $f()$ clearly doesn't affect the result... or does it?
<h3>How an assingment operation really works</h3>
It may seem obvious at first, we just copying one value to another, but let's see how compiler actually handles this operation.
Consider this code. ([Source](https://en.cppreference.com/w/cpp/language/eval_order.html))
<spoiler summary="Code">
~~~~~
#include <cstdio>
int a() { return std::puts("a...
Every vector has a capacity (the allocated memory space, initially empty). And
when youcall
130.
Polygon: resources advanced properties (graders) Hello, Codeforces!
Today I’ve released an important update of the Polygon — partial support for advanced properties of resources. The main task that is being solved by this update is to support the development of problems with graders.
In most competitions, participants need to submit a complete solution code, including reading an input reading and an output writing. For example, in Codeforces rounds you solve such kind of problems. However, in some competitions another approach is using: a participant needs to implement the required function or interface.
For example, in a problem statement can be written that in a C ++ solution you need to implement a function that has prototype `int sum (int a, int b)` and submit the implementation. In this case, a participant has to submit a source code that contains the implementation of this function. Then, in the process of judging this solution for such a problem, an online judge should compile and link into a single executable f...
131.
[Tutorial] Online Dynamic Connectivity The World Finals are right ahead, and if everything works as I expect, you will probably have to wait a lot of time before the contest, dress rehearsals, or anything else. I prepared this blog post so that you have something to keep yourself occupied.
# Goal
Our goal is to maintain connectivity in fully-dynamic query streams. In other words, we want to solve this problem:
* Insert an edge $e = (u, v)$ into a graph
* Delete an edge $e = (u, v)$ into a graph
* Find if two vertices $u, v$ are connected
* Find the size of connected components where the vertex $u$ belongs.
The *offline version*, where you can *cheat* (aka, read all queries before answering, and answer everything at the very end of the program) has a very cool solution commonly known as *Offline Dynamic Connectivity*. This is enough in most CP problems, where this *offline* solution is rarely considered cheating.
Unfortunately, people in the academia are not chilling and consider this a kind of cheating (n...
the set and call it a day.
132.
CP-Algorithms: Discord server, donation campaign and more Hi everyone!
<img src="/predownloaded/82/15/821540e8f87d8a2b2d468377aacbba80b0aa1623.png" style="float:right;" width=100px>
It was a while since I [posted](https://codeforces.me/blog/entry/135081) last update about **[CP-Algorithms](https://cp-algorithms.com)**. As a general reminder, it is a community project that [started off](https://codeforces.me/blog/entry/13198) in 2014 by [user:RodionGork,2025-08-23] as a translation of [e-maxx](http://e-maxx.ru/), a Russian go-to resource at the time by [user:e-maxx,2025-08-23] for learning core competitive programming algorithms. Since then, CP-Algorithms grew quite a lot (which also prompted a rename from original project name `e-maxx-eng`) and includes a lot of new, original articles, and a lot of translated articles were enhanced and/or extended or even completely rewritten.
In this blog, I would like to share a bunch of updates about the site, to make sure it's still in the collective memory 😅
### New maintainers
...
### Contributors call
133.
Editorial of Codeforces Round #572 Codes have been added!
We've added challenges(mostly not hard) to some tasks. Feel free to share solutions and ask any questions in comments!
Keanu Reeves
----------
If the string is good, then answer it's itself. Otherwise, there are at least two strings in answer, and we can print substring without its last symbol and its last symbol separately. Complexity $O(n)$.
[code](https://pastebin.com/Dc0gtG9n)
Number circle
----------
Let's suppose that array is sorted. First of all, if $a_n \ge a_{n - 1} + a_{n - 2}$, than the answer is — NO (because otherwise $a_{n}$ is not smaller than sum of the neighbors). We claim, that in all other cases answer is — YES. One of the possible constructions (if the array is already sorted) is:
$a_{n - 2}, a_{n}, a_{n - 1}, a_{n - 4}, a_{n - 5}, \ldots ,a_1$
It's easy to see, that all numbers except $a_n$ will have at least one neighbor which is not smaller than itself. Complexity $O(nlog(n))$.
[code](https://past...
Let's call configuration $\textbf{critical}$, if it has critical element (in
other words, if there, Let's call minimum index $i$ from Claim 3(if it exists) critical.
Tutorial of Codeforces Round 572 (Div. 1)
Tutorial of Codeforces Round 572 (Div. 2)
134.
Codeforces round #649 editorial ### [problem:1364A]
Let's start with the whole array. If every element in it is divisible by $x$, the answer is $-1$; if its sum isn't divisible by $x$, the answer is $n$. Otherwise, we must remove some elements. The key idea is that removing an element that is divisible by $x$ doesn't do us any benefits, but once we remove an element that **isn't**, the sum won't be divisible by $x$. So let the first non-multiple of $x$ be at index $l$, and the last one be at index $r$. We must either remove the prefix all the way up to $l$ or the suffix all the way up to $r$, and we'll clearly remove whichever shorter.
Code link: https://pastebin.com/j2Y8AJBA
Alternatively, we can notice that this means the answer is either a prefix or a suffix, so we can simply bruteforce them all.
### [problem:1364B]
TL;DR the answer contains the first element, last element, and all the local minima and maxima, where a local minimum is an element less than its 2 adjacents, and a local maximum is an e...
Now we already have an $nlog(n)$ solution (call our magic function with every
index,) but how to, Since every time $val$ is replaced with a subset of it, we only call our magic
function at most
Tutorial of Codeforces Round 649 (Div. 2)
135.
Sqrt-tree: answering queries in O(1) with O(NloglogN) preprocessing. Hello, Codeforces!
Some time ago I invented an interesting data structure and I'd like to share it with the community. Maybe, it was known before, and if you knew about it before my blog post, please share the link to the source.
# What can the data structure do?
Given an array $a$ that contains $n$ elements and the operation $op$ that satisfies associative property: $(x\ op\ y) op\ z = x\ op (y\ op\ z)$ is true for every $x$, $y$ and $z$.
So, such operations as $gcd$, $\min$, $\max$, sum, multiplication, $and$, $or$, $xor$, etc. satisfy these conditions.
Also we have some queries $l, r$. For each query, we need to find $a_l\ op\ a_{l+1}\ op\ \dots op\ a_r$. Let's call such queries $q(l, r)$.
My data structure can process such queries in $O(1)$ time with $O(n \cdot \log \log n)$ preprocessing time and $O(n \cdot \log \log n)$ memory.
# How it works?
[cut]
#
## 1. Sqrt
Let's do a sqrt-decomposition. We divide our array in $\sqrt{n}$ blocks, each block ha...
\ a_r$. Let's call such queries $q(l, r)$.
136.
Tutorial: A simple O(n log n) polynomial multiplication algorithm Hi Codeforces!
I have something exciting to tell you guys about today! I have recently come up with a really neat and simple recursive algorithm for multiplying polynomials in $O(n \log n)$ time. It is so neat and simple that I think it might possibly revolutionize the way that fast polynomial multiplication is taught and coded. You don't need to know anything about FFT to understand and implement this algorithm.
Big thanks to [user:nor,2023-07-10], [user:c1729,2023-07-10] and [user:spheniscine,2023-07-10] for discussing the contents of the blog with me and comming up with ideas for how to improve the blog =).
I've split this blog up into two parts. The first part is intended for anyone to be able to read and understand. The second part is advanced and goes into a ton of interesting ideas and concepts related to this algorithm.
Prerequisite: Polynomial quotient and remainder, see [Wiki article] (https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_divi...
137.
Mo's Algorithm on Trees [Tutorial] Introduction
------------
Mo's Algorithm has become pretty popular in the past few years and is now considered as a pretty standard technique in the world of Competitive Programming. This blog will describe a method to generalize Mo's algorithm to maintain information about paths between nodes in a tree.
Prerequisites
-------------
Mo's Algorithm — If you do not know this yet, read this amazing [article](http://blog.anudeep2011.com/mos-algorithm/) before continuing with this blog.
Preorder Traversal or DFS Order of the Tree.
Problem 1 — Handling Subtree Queries
------------------------------------------
Consider the following problem. You will be given a rooted Tree $T$ of $N$ nodes where each node is associated with a value $A[node]$. You need to handle $Q$ queries, each comprising one integer $u$. In each query you must report the number of distinct values in the subtree rooted at $u$. In other words, if you store all the values in the subtree rooted...
called only after $dfs(x)$ has been completed and $S(x)$ has been explored.
Thus, before wecall $dfs(y
138.
IOI 2027 Call for Tasks We are excited to announce that the **Call for tasks for IOI 2027** is officially open!
The scientific committee for IOI 2027 would love to invite everyone (except potential contestants) to submit their task proposals. If you know anyone who might be interested in creating tasks for IOI 2027, please share this announcement with them.
We welcome tasks of all difficulty levels, and we especially appreciate submissions of easy tasks. Original and creative easy tasks can be very challenging to create, and we always need more of them. We also welcome submissions across a variety of task types, including batch, communication, and output-only tasks as well as novel task types that have not appeared in IOI before.
You can submit your tasks through the following website, where you will also find more details about the submission requirements and the submission process: [https://ioi2027.de/contest/call-for-tasks](https://ioi2027.de/contest/call-for-tasks).
The deadline for the call f...
IOI 2027 Call for Tasks, about the submission requirements and the submission process:
[https://ioi2027.de/contest/call-for-tasks, The deadline for the call for tasks is **31 December 2026, 23:59 UTC-12**., We are excited to announce that the **Call for tasks for IOI 2027** is
officially open!
139.
C++ STL: Policy based data structures Hi everyone! After a relatively long lull, I decided that <s>my contribution growing too slowly</s> the hour has come to please you with another article in the blog _:)_
2 months ago user [user:Perlik,2014-03-19] wrote an [article] (/blog/entry/10355), in which he described a very interesting STL implemented data structure that allows you to quickly perform various operations with substrings. Some time after I tested it on various tasks and, unfortunately, tend to get a negative result — rope was too slow, especially when it came to working with individual elements.
For some time, I forgot about that article. Increasingly, however, I was faced with problems in which it was necessary to implement set with the ability to know ordinal number of item and also to get item by its ordinal number (ie, order statistic in the set). And then I remembered that in the comments to that article, someone mentioned about the mysterious data structure order statistics tree, which supports th...
140.
AI might erase CP, but not us I haven't slept for 20 hours and I can't fall asleep. I've been reading others' topics on AI, and I had a sort of epiphany. These ideas have been brewing inside me for many years, and I thought it might be time to share them with the community.
---
There were times when I was a "competitive programmer" at the core. I spent many years doing that exclusively. I've never been to IOI, but I like to think that I've reached some good heights.
Two years ago, I stopped writing online competitions. I've written a few offline competitions after that, but eventually, I decided to stop that too.
Yet somehow Codeforces still attracts me. I don't want to solve problems, but I keep typing codeforces.com into the address bar. *Why?* Just yesterday, I didn't have an answer.
---
Imagine a layperson asking you what competitive programming is. What are you going to say? My answer has always been "Oh, we solve interesting algorithmic problems with time constraints and other limits". Many ...
141.
Optimal Incremental MST in 20 lines of code Hello Codeforces!
Some of you might know `BottleneckTree.h` from [my KACTL fork](https://github.com/bicsi/kactl/blob/master/content/graph/BottleneckTree.h) (although it's a little obscure for an ICPC notebook; oh well). [user:freak93,2026-11-05] and I wrote it in 2021. The header says the complexity is "probably $O(\log n)$ amortized". It all started from a 2020 solution by [user:RestingRajarshi,2026-11-05] (more on that at the end). After about 6 years of on-and-off thinking about it, and with the help of Claude, we finally have an answer: it's not :). There are inputs where it takes $\Omega(\sqrt n)$ per operation.
The good news is that a small change in the main loop fixes it, and this time we have a proof. We wrote a paper about it: [Incremental Minimum Spanning Trees on a Napkin](https://arxiv.org/abs/2611.05713). I think the structure is super elegant and short enough to be useful in contests, so I'm writing a blog about it.
Prerequisites: none, really. It helps to know ...
Let $p$ be the parent of $x$, and $g$ the parent of $p$. We call the edge of
$x$ an *up edge* if
142.
A simple introduction to "Segment tree beats" **This blog is just a back up of [http://codeforces.me/blog/entry/57319](http://codeforces.me/blog/entry/57319) to prevent this tutorial from discarding after [user:jiry_2,2018-10-17] is banned.**
Hi, I’d like to introduce a simple trick about segment tree in this blog as I promised in [this comment](http://codeforces.me/blog/entry/54750?#comment-387957). Sorry for the long delay, as a sophomore in Peking University, I've just finished a tired semester and a painful final exam. And now I finally have enough time to do a simple introduction to this interesting algorithm.
It may be a huge project for me since my English is not good. I think I will finish this blog in several steps and I will try to finish it as soon as possible :)
In China, all of the 15 candidates for the Chinese National Team are asked to write a simple research report about algorithms in informatics Olympiad, and the score will be counted in the final selection. There are many interesting ideas and algorit...
. So the proof is still hold for other operations. That's why I call this proof
universal.
143.
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...
unknown number of days to eat. Let's call them $x_{i}$. And we have some
information about... linear
144.
EGOI 2026 Call for Problems (extended deadline!) Hello Codeforces!
We are looking for problems for the European Girls' Olympiad in Informatics (EGOI) 2026. The contest will be held in Cesenatico, Italy, 12 – 18 May 2026. **The submission deadline is Sunday, 4th January 2026.**
<spoiler summary="Details about the submission process">
We are looking for problems of varying difficulties and types (batch, output-only, or interactive).
To get an idea of style and difficulty, see the problems from the previous years, that is 2021 to 2025 (https://stats.egoi.org/tasks/ ).
Additionally, the topics and techniques used must conform to the IOI syllabus (https://ioinformatics.org/page/syllabus/12 ).
## Acceptance Criteria
Any problem submitted to EGOI 2026 must consider the following criteria to be considered for acceptance:
- **Novel:** Similar problems have not been published in recent versions of the competition nor in any other similar co...
EGOI 2026 Call for Problems (extended deadline!), ! For more details, check out the official [call for
volunteers](https://egoi2026.it/contacts
145.
[Tutorial] Fully Dynamic Trees Supporting Path/Subtree Aggregates and Lazy Path/Subtree Updates Hey everyone! Usually when I post stuff on CF I just drop an external link to my blog, but this time I would like to also paste the same content natively on CF to see if it leads to more engagement. You can read the exact same article on my blog [here](https://mzhang2021.github.io/cp-blog/ds5/).
Also, special thanks to [user:alien_lover,2022-06-10] and [user:gabrielwu,2022-06-10] for proofreading.
---
## Motivation
We will solve **[this problem](https://dmoj.ca/problem/ds5)**.
## Prologue
The original name of this problem is [SONE1](https://darkbzoj.cc/problem/3153), originating from the fiery depths of Chinese OI. Amazingly, the Chinese have figured out how to augment the link/cut tree to solve this problem (ref [1](https://www.cnblogs.com/clrs97/p/4403244.html), [2](https://blog.csdn.net/iamzky/article/details/43494481)). Maintaining subtree aggregates with a LCT isn't difficult, and there's a well-known [Codeforces article](https://codeforces.me/blog/entry/67637) ...
supposed to receive. So to remedy this, we need to call push on all fake
ancestors of $u$ up to the next, - Call `add(v, u)`
146.
Codeforces Round #722 Editorial Hi, Codeforces!
[problem:1529A]
problem idea and solution: [user:AmShZ,2021-05-24]
<spoiler summary="editorial">
[tutorial:1529A]
</spoiler>
<spoiler summary="official solution">
~~~~~
// khodaya khodet komak kon
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <pii, int> ppi;
typedef pair <int, pii> pip;
typedef pair <pii, pii> ppp;
typedef pair <ll, ll> pll;
# define A first
# define B second
# define endl '\n'
# define sep ' '
# define all(x)...
~~~~~ // Call my Name and Save me from The Dark #include
Tutorial of Codeforces Round 722 (Div. 1)
Tutorial of Codeforces Round 722 (Div. 2)
147.
Caveats of using optimize("Ofast") with target("avx2") Hi everyone!
As you may know, it is often recommended to put these lines in your header:
```cpp
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
```
And they're usually great!<sup>[1]</sup> Well, until they aren't. For last 2-3 days I was riddled with the issue that [CP-Algorithms Library](https://lib.cp-algorithms.com) would perform very well on Library Checker, but whenever I tried to also apply it on Codeforces, it will fail to speed up the code, and sometimes would even make it much slower. As I finally figured out the cause, I'd like to write a blog about it, so that other people don't waste as much time.
Mitigating these issues improved my running time on [problem:1975G] from **1530 ms** in [submission:316602668] to **203 ms** in [submission:352602775].
##### Tl'dr
See the "Takeaway" section at the bottom.
[cut]<br>
##### Example problem
I will reproduce the issue on a simple example:
<hr>
**[problem:911G]**: You are given an...
: inlining failed in call to 'always_inline' 'constexpr std::allocator<
148.
Extended deadline for the EGOI 2025 call for problems ### **Extended deadline for the EGOI 2025 call for problems**
Hello Codeforces!
We are looking for problems for the European Girls' Olympiad in Informatics (EGOI) 2025. The contest will be held in Bonn, Germany, 14 – 20 July 2025. As we are still low on proposals the submission deadline has been moved to Sunday, <s>19 January 2025</s> **<span style="color:red">9 February 2025</span>**.
<spoiler summary="Details about the submission process">
We are looking for problems of varying difficulties and types (batch, output-only, or interactive).
To get an idea of style and difficulty, see the problems from the previous years, that is 2021 to 2024 (https://stats.egoi.org/tasks/ ).
Additionally, the topics and techniques used must conform to the IOI syllabus (https://ioinformatics.org/page/syllabus/12 ).
## Acceptance Criteria
Any problem submitted to EGOI 2025 must consider the following criteria to be considered for acceptance:
- **Novel:** Similar proble...
Extended deadline for the EGOI 2025 call for problems
149.
Hybrid Tutorial #-2: Centroid Decomposition **See the [original post](https://codeforces.me/blog/entry/81317) on Codeforces for a playlist of all similar tutorials and also more information about what this is.**
# "Intro"
*Timestamp: [00:00](https://youtu.be/-DmMLQCmz94)*
This is a "hybrid tutorial" — it has both a blog and a video component. See my original post for more explanation of what this is and also a playlist of all past tutorials. You can view the full video [here](https://youtu.be/-DmMLQCmz94).
This tutorial is on centroid decomposition, a cool concept that has many uses in different problems. It's also another "decomposition" technique, one of many. I feel like this subject in particular doesn't have many great tutorials online that really capture the essence of what we do with the technique, so hopefully, I can improve that with this one.
# Notation
We'll use $0$-indexing for the whole tutorial, and the example problem will also be $0$-indexed. In addition, "vertex" and "node" mean the same...
Steps for using it: * Read in `n`, and call `init(n)`. * Read in all edges, and
call `edge(u, v
150.
CodeCraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) Announcement Hello Everyone!
I would like to invite you to CodeCraft-17, which will take place on [Thursday 12th January 2017, 9:05PM IST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=CodeCraft-17&iso=20170112T1535&p1=1440&ah=3). The round will be a Div1 + Div2 combined round and is **rated**.
[Felicity, IIIT Hyderabad](https://www.facebook.com/felicity.iiith) presents [Threads ‘17](https://felicity.iiit.ac.in/threads/), the magnificent annual technical fest, is finally here in its 13th edition! With a plethora of intellectually engaging online contests in various fields of programming, mathematics and general knowledge, Threads is a celebration of the spirit of computing and engineering. The grand algorithmic sprint called **CodeCraft**, parallel programming in **Kernel Cruise**, mathematical enigmas in **Gordian Knot**, jeopardy style CTF event called **Break In**, overall Threads '17 has something to offer for every kind of computing enthusiast!
, I [reported](https://codeforces.me/blog/entry/129765?#comment-1151921) a suspicious participant [toyuzuko](https://atcoder.jp/users/toyuzuko) who solved problem ABCD in 51 seconds. They also did the similar thing in ABC354.
This time (ABC356), there are much more suspicious participants.
The average first-AC time (in seconds) of ABC347~ABC353 is in the following table:
|Contest|A|B|C|D|E|F|G|
|:-|:-|:-|:-|:-|:-|:-|:-|
|ABC347|21|45|93|244|177|300|824|
|ABC348|15|37|72|302|236|495|430|
|ABC349|23|67|54|116|598|139|634|
|ABC350|26|47|102|74|240|489|335|
|ABC351|22|23|106|352|199|122|902|
|ABC352|27|43|49|90|196|989|188|
|ABC353|24|79|172|88|206|1161|313|
|(minimum)|15|23|49|74|177|122|188|
|(prefix sum)|15|38|87|161|338|460|648|
Note that to get first-AC in a problem...
To make sure there are fewer exceptions, I will call all the participants who
solved any subset of
152.
C++17, competitive programming edition C++17 is now [available](http://codeforces.me/blog/entry/57646) on codeforces, community [wants](http://codeforces.me/blog/entry/15643?#comment-413401) new edition of [C++ tricks](http://codeforces.me/blog/entry/15643) by [user:Swift,2018-02-19], so, let's start!
Disclaimer: I have done only few examples of new features, which in my opinion are related to competitive programming. Feel free to comment and provide more real-world examples or ask to elaborate some features with more examples or explanations.
### Fold expressions
* I think that everybody knows, what reduce or fold means, but a c++11 example:
```
vector<int> v = {1, 3, 5, 7};
int res = accumulate(v.begin(), v.end(), 0, [](int a, int b) { return a + b; });
cout << res; // 16
```
* In C++17 there is also folding support for a template parameters list. It has the following syntax:
```
(pack op ...)
(... op pack)
(pack op ... op init)
(init op ... op pack)
```
* For example, implement a template...
I think that it is convenient function, but it'll be difficult to call it in
mind during contest :)
153.
Helvetic Coding Contest 2016 online mirror Hello CodeForces! I'd like to invite you to the online mirror of an open championship of Switzerland called the Helvetic Coding Contest.
[The Helvetic Coding Contest](http://hc2.ch/) is a yearly contest held at [the EPFL](http://epfl.ch/) in Lausanne by the [PolyProg](http://polyprog.epfl.ch/) association. The contest itself took place in March, but the online mirror is scheduled on [**Sunday, 10th of July, 11:00 Moscow time**](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Helvetic+Coding+Contest+2016+online+mirror&iso=20160710T0800&ah=4&am=30). The duration is 4:30.
Rules:
- you can participate in teams or individually (1-3 people),
- standard ACM-ICPC rules (no hacking),
- the contest is not rated,
- if you have participated in the onsite contest, please do not participate in the mirror.
You will help the cow Heidi [protect humanity against a zombie apocalypse](http://hc2.ch/img/poster/poster.png). The contest...
Announcement of Helvetic Coding Contest 2016 online mirror (teams, unrated)
154.
Run-twice (aka communication) problems with Polygon and testlib.h ### Introduction
_Run-twice_ problems (also called _multipass_ or _communication_ problems) are problems in which your program is executed twice. Here are some examples:
- [problem:2054A] from the TON marathon.
- Problems D, G and K from [Universal Cup Season 2 Stage 5](https://assets.ucup.ac/statements/statements-2-5.pdf).
- All problems from [Universal Cup Season 2 Stage 16](https://assets.ucup.ac/statements/statements-2-16.pdf).
- [Flash](https://boi2019.eio.ee/wp-content/uploads/2019/04/flash.en_.pdf) from BOI 2019 (this one is actually more complicated, but the premise is the same — there are multiple instances of your program which cannot share data except through the interactor.
As you can see, there are many ways this format can be used, but the common themes are encoding/decoding, compression/decompression, constructing a bijection and similar ideas. The general principle is that you have to implement two functions and the second function has to somehow use t...
155.
OpenAI Codex can solve unseen Codeforces problems In this post, we will use the recent OpenAI Codex product based on GPT-3, first introduced in [Evaluating Large Language Models Trained on Code (Chen et al., 2021)](https://arxiv.org/abs/2107.03374) to solve some Codeforces problems.
We use the round [contest:1560] because the current version of the Codex model was released before this round. As the model has been trained on the Github data, it is possible that it memorized some solutions for older problems.
### Solving [problem:1560A] from the statement only
This is a simple problem, and the statement kind of explains what we should implement. Let's just give the plaintext statement to Codex:
<spoiler summary="Prompt">
Problem:
Polycarp doesn't like integers that are divisible by 3 or have the last digit 3
in their decimal representation.
Polycarp starts to write out the positive (greater than 0) integers which he likes:
1,2,4,5,7,8,10,11,14,16,….
Output the k-th element of this sequence (the elements are numbered...
156.
LGMSniper.com: See which LGMs you have beaten! LGM Sniper
==================
I just created a cool CF tool called [LGM Sniper](https://wumbogames.com/CompetitiveProgramming/LGMSniper). It looks at scoreboard data from every Div1 and Div1+Div2 round ever and tells you which LGM's you have beaten, how many times you have beaten them, and which rounds you beat them in. You can also compare yourself to your friends to see which one of you wins more! If you want to compare yourself with some friends, check the 'show ex-lgms' box and enter the friend you want to compare to as Handle #2, and they will show up on the bottom.
You can try it out for yourself at [lgmsniper.com](https://wumbogames.com/CompetitiveProgramming/LGMSniper), or in the competative programming section of [Wumbo Games](https://wumbogames.com/), if you would prefer. Tooltips show the name of the rounds you won in (hover your mouse over the checkmark).
If you find any interesting facts or have suggestions for how I could improve the tool, let me know in the co...
157.
Editorial for Codeforces Round #761 (Div. 2) Thanks for participating, hope you enjoyed the problems! Implementations for the problems are chosen randomly among testers, and I made some changes to their codes (for example, deleted meaningless comment lines). Please do not hesitate to provide feedback in the comments, so I can improve in setting problems next time.
**UPD**: Sorry but there is a checker bug in problem E. All submissions of problem E will be rejudged soon.
**UPD2:** Rejudge done, the round remains rated.
<spoiler summary="Statistics">
Number of FST for rated participants:
- Problem A: $29$
- Problem B: $90$
- Problem C: $12$
- Problem D1: $4$
- Problem D2: $0$
- Problem E: $6$
Number of AK: $22$
Number of clarifications: $85$
</spoiler>
[problem:1617A]
<spoiler summary="Hint">
When is the lexicographically smallest permutation of $S$ (i.e. the sorted string) not the answer?
</spoiler>
<spoiler summary="Solution">
If there are no occurrences of `a`, `b` or `c` in $S$, ...
After we know one crewmate and one impostor (let's call them $a$, $d$), we can
query these two, }$ queries, there must be at least one $0$ and one $1$. Now, let's call a tuple
($a, b, c$) that
Tutorial of Codeforces Round 761 (Div. 2)
158.
As an CNOI Gold Medalist: How I Train CNOI Gold Medal Winning Competitive Programmers UPD: [Curated Problem Set #1](Thhttps://codeforces.me/blog/entry/156427) is released. Please join our Discord server to receive the latest updates: https://discord.gg/DsHSfmVgG
UPD: Curated problem set #1 (both normal and advanced) **for subscribers** is ready! Feel free to join our Discord server and subscribe!
This post is about:
1. The Main Two Abilities You Need in Competitive Programming
2. How to Choose Problems of an Appropriate Difficulty
3. How Should You Work on a Problem
4. When You Should Learn New Knowledge (Like New Algorithms)
5. How to Train Before an Important Contest
6. Free Content, Personalized Subscription Services, and Potential Opportunity for One-to-One Coaching
7. Survey About the Services
I won a gold medal at NOI 2024 in my second year of high school and was admitted to the Turing Class at Peking University. After securing my admission, I continued pursuing competitive programming: I began studying new material at university in advance whi...
I call the ability required for the first part **thinking ability**, and the
ability required for
159.
Are we close to machines solving ICPC problems? Hi, all,
I with few other folks at [NEAR](http://near.ai/blog) work on teaching machines to program. A particularly exciting sub-project of that is teaching machines to solve competitive programming problems.
In this post I would like to give a quick overview of where the state of the art is today, what the major challenges are, why this is not a popular area of research, and how the CodeForces community can help to address some of the issues the program synthesis community is facing today.
We also have a certain budged allocated for this project, and we are paying to the CodeForces members who help us with some data annotation challenges. We have paid more than $10k in our first two annotation projects, and are launching three more projects today. Scroll to the end if you are interested.
Competitive programming as a benchmark
======================================
With the emergence of deep learning, neural networks started performing almost at a human level in many ta...
160.
AtCoder World Tour Finals 2018: A new onsite contest with free flights/hotels, no age limit! AtCoder will hold a new onsite contest called AtCoder World Tour Finals 2018.
If you get the top 30 places in AGCs (and maybe some other types of contests), you will get GP30 scores. Eight people with the highest total GP30 scores in 2018 (except for people under 18) will be invited to Japan, probably in February 2019. We will cover flights and hotels. There's no upper bound for the age. You can participate in the finals even if you are employed.
Please check the details [here](https://atcoder.jp/post/171).
Here's the total GP30 scores in 2017:
<table border="1" width="400" cellspacing="0" cellpadding="5" bordercolor="#333333">
<tr>
<th bgcolor="#EE0000"><font color="#FFFFFF">Rank</font></th>
<th bgcolor="#EE0000"><font color="#FFFFFF">Handle</font></th>
<th bgcolor="#EE0000"><font color="#FFFFFF">Score</font></th>
</tr>
<tr><td>1</td><td>[user:tourist,2017-12-26]</td><td>870</td></tr>
<tr><td>2</td><td>[user:Um_nik,2017-12-26]</td><td>519</td></tr>
<tr><t...
161.
My Review about Scaler academy. To all my Indian juniours and experienced professionals, Never join Scaler Academy(Interviewbit). Hello, I was enrolled in Interviewbit(Scaler academy) course in May, 2019. I belongs to tier 3 college. Only companies with max 5-6 lack per annum comes to my college. In a hope of getting into good companies I decided to join Interviewbit. I qualified their entrance test which is hard in itself for many average coders in India. Then in a hope of securing good referrals, I used to maintain my Problem solving Percentage above 80% most of time.
When the time of referral come in september — october 2019, they were saying that, right now companies are hiring for on campus and thus we will refer you around November. I believed them. Continued to solve problems working day and night, burning the midnight oil, just in a hope that if I get a referral of good companies.
Now, when when it is november 2019, they came up with new excuse. They told that we are in talk with top tech companies, you will soon hear good news from us. Then many days passed. Nothing happened. I was still hopi...
. I was still hoping that i will get a call soon. In february, I again asked
them, I didn't receive
162.
[Tutorial] On Range LIS Queries, Part 2 ## Previous article
* [On Range LIS Queries. Part 1](https://codeforces.me/blog/entry/111625)
## Chapter 4. Fast algorithm for $\boxdot$ operator
We stopped at the point where we learned how to:
* Implement the $\boxdot$ operator in $O(N^3)$ time
* Use the $\boxdot$ operator for $O(N^2)$ time
I actually didn't introduce the name to avoid unnecessary scare, but the [original paper](https://arxiv.org/abs/0707.3619) calls this operator as *unit-Monge matrix-matrix distance multiplication*. Throughout the article, we will call it as the **unit-Monge multiplication (of permutation)** or just $\boxdot$ operator as we did before.
Let's see how to compute the $\boxdot$ operator in $O(N \log N)$ time. For a matrix $\Sigma(A), \Sigma(B)$ consider the partitioning $\Sigma(A) = [\Sigma(A)_{lo}, \Sigma(A)_{hi}], \Sigma(B) = \begin{bmatrix} \Sigma(B)_{lo} \newline \Sigma(B)_{hi} \end{bmatrix}$, where $lo$ denotes the first $N/2 + 1$ entries, and $hi$ denotes last $N/2$ entries. We ...
*. Throughout the article, we will call it as the **unit-Monge multiplication
(of permutation)** or just
163.
Efficient 3D Convex Hull Tutorial _Warning: The following contains graphic depictions of geometry, precision errors, and degenerate cases. Viewer discretion is advised._
### Prerequisites
I assume the reader is familiar with:
- 2D Convex Hulls
- 3D Vector Operations (dot and cross products)
### Introduction
Recall that in the 2D convex hull problem, you are given a set of 2D points, and you must compute the smallest convex polygon containing all the given points. By convex, we mean that for any two points $A$ and $B$ inside the polygon, the entire line segment $AB$ is also inside the polygon.
The problem in 3D is completely analogous. You are given $n$ 3D points, and you must compute the smallest convex polyhedron containing all the given points. Similarly, a polyhedron is convex if for any two points $A$ and $B$ inside the polyhedron, the line segment $AB$ is also inside the polyhedron.
In the 2D case, it is more obvious what the output is. We can simply output a circular list of vertices on the ...
164.
Codeforces Round #812 (Div. 2) Editorial <spoiler summary="Before the round starts">
Great efforts have been put over last year. We want to say thanks to everybody who helped us to make this round as it is. Cannot wait to see you guys on the next one!
<spoiler summary="Testers' predictions">
<table>
<tr style ="background-color:#D3D3D3">
<th>Tester</th>
<th>A</th>
<th>B</th>
<th>C</th>
<th>D</th>
<th>E</th>
<th>F</th>
</tr>
<tr>
<td>[user:tfg,2022-08-06]</td>
<td>800</td>
<td>1100</td>
<td>1500</td>
<td>1600</td>
<td>1900</td>
<td>2400</td>
</tr>
<tr>
<td>[user:neko_nyaaaaaaaaaaaaaaaaa,2022-08-06]</td>
<td>800</td>
<td>1100</td>
<td>1700</td>
<td>1900</td>
<td>2100</td>
<td>2600</td>
</tr>
<tr>
<td>[user:BucketPotato,2022-08-06]</td>
<td>800</td>
<td>1000</td>
<td>1400</td>
<td>1800</td>
<td>2400</td>
<td>-</td>
</tr>
<tr>
<td>[user:LetterC67,2022-08-0...
Let's call $M = max(a_1, a_2, \dots, a_n)$.
Tutorial of Codeforces Round 812 (Div. 2)
165.
Offline Dynamic MST [Tutorial] Inspired by [an old Adamant blog](https://codeforces.me/blog/entry/15296), I reinvented a variation of the technique for calculating the cost of the minimum spanning tree offline, when edge weight updates are allowed. This technique is not new and already appeared in [work of David Eppstein](https://www.ics.uci.edu/~eppstein/pubs/Epp-TR-92-04.pdf). This was also in Adamant's blog, but I missed it completely :).
So the problem statement is: You're given a undirected, connected, weighted graph with $n$ nodes and $m$ edges. There are $q$ updates of the form: Set the weight of $k'th$ edge in the input to $x$. After each update you should report the total weight of a minimum spanning tree. Notice that this is strong enough to simulate edge deletions and insertions, by just giving the edge a weight of infinity when it is "deleted".
This is difficult to do if you were forced to do all updates online. But offline, we can use divide and conquer on time to achieve a decent time complexity...
We call an interval $[x,y)$ **active** if it partially overlaps with the
interval $[l,r)$, but it
166.
My Solutions to Spectral::Cup 2026 Round 1 (CF Round 1094) Since the editorial for today's Div. 1 hasn't been published yet, I thought I'd share solution sketches. Some of these won't include all of the specific details, but hopefully they should communicate the main ideas. (I didn't compete officially, but I got AC on all of the problems using the below approaches, so I'm fairly confident in correctness.) Feel free to leave questions below and I'll respond if I have time.
## A — A Wonderful Contest
If any problem has $100$ subtasks, the answer is yes: we can achieve an arbitrary score by solving some of the other problems fully and by solving the right number of subtasks of the $100$-subtask problem. Otherwise, there is no way to achieve a score of 1, so the answer is no.
## B — Artistic Balance Tree
Note that each of the reversal operations swaps odd positions with odd positions and even positions with even positions, as $u-i$ and $u+i$ differ by $2i$ and thus have the same parity. Thus, when we are to mark an od...
Call the child of $v$ with the largest subtree size the "heavy child" and call
its subtree the
167.
Unlabeling combinatorial species (cycle index series) Hi everyone!
In my [previous blog](https://codeforces.me/blog/entry/103979), I wrote about how generating functions can be used to enumerated labeled species. In this blog, I want to continue the topic by writing about how one can account for different kinds of symmetries when counting different combinatorial structures. Ultimately, we will end up deriving and hopefully understanding the analogue of [Pólya enumeration theorem](https://en.wikipedia.org/wiki/Pólya_enumeration_theorem) in species.
Difficulty: ★★★★☆
Prerequisites:
- Familiarity with combinatorial species (see my [prev. blog](https://codeforces.me/blog/entry/103979)), OR
- Very good intuition with enumerative combinatorics, genfuncs and recap below.
I will try to use plain language rather than formulas as much as possible, as it seems to be the preferred format for readers.
## Recap
Below is a very brief recap of the most important things from the previous article. I tried to keep it as informal as p...
168.
I started solving Project Euler [user:Radewoosh,2024-01-12] inspired me by [completing](https://codeforces.me/blog/entry/122793) Project Euler, and I recently [started](https://projecteuler.net/progress=ivanovmp), slow but steady, solving its problems. I don't mind anybody adding me as a friend on Project Euler, my friendship key is `2127163_HmDkRoxUDZa38znoBSPq2n4Prg996WEX`, please enter it on [this page](https://projecteuler.net/friends) if you're registered and you'd like to see me in your friend list. (Similarly, you'll appear in my friend list.)
I also record the process and upload on Youtube because, according to the [rules](https://projecteuler.net/about), problems 1–100 are allowed for public analysis (although I'm afraid there won't be any serious or interesting problems in the first hundred). As for now, uploaded are:
* [problems 1–3](https://youtu.be/k2rRnfDxDME);
* [problems 4–12](https://youtu.be/oQ0AXSwlVog);
* [problems 13–24](https://youtu.be/aOBgin-XGkQ);
* [problems 25–36](https://youtu.be...
These are screencasts, I would even call them editorials, but (at least in the
earlier problems
169.
Group tutoring Hi. I offer classes for groups of 2-3 students.
I teach competitive programming with a focus on problem-solving.
There won't be many lectures because I can send you an article/video link instead.
The lesson cycle is usually: I choose a problem, you say your thoughts and ideas, I comment on incorrect ideas, and we talk about the valid solution(s), possibly with drawings and pseudocode.
In beginner groups, I might ask you to implement something, C++ or Python preferred.
There's a lot of homework and you're expected to practice a few hours per week.
We might spend half a lesson talking about 1-2 homework problems from last week.
This is intended.
We use Google Meet, shared whiteboard, and a collaborative editor Codebunk.
After a lesson, you get a video recording and a codebunk with code/text history like this one https://codebunk.com/pb/3501100331621/.
This allows you to copy links and code easily.
There's a Discord group chat to ask questions between classes.
- 1.5h les...
If your company is interested, we can schedule a call to discuss the details.
170.
Codeforces Global Round 13 Editorial [problem:1491A]
------------------
Setter: [user:syksykCCC,2021-02-28]
Prepared by: [user:syksykCCC,2021-02-28]
<spoiler summary="Hint 1">
How can we find the largest $k$ such that the $k$-th smallest element of the array is $0$?
</spoiler>
<spoiler summary="Hint 2">
How can we maintain $k$?
</spoiler>
<spoiler summary="Solution">
Let's define $cnt$ to represent the number of 1s in the array.
For the modifications, if $a_i$ is already $1$ now, then we let $cnt \gets cnt - 1$. Otherwise, let $cnt \gets cnt + 1$.
For the querys, just compare $cnt$ with $k$. If $cnt \ge k$, the answer will be $1$. Otherwise, the answer will be $0$.
The complexity : $O(n + q)$.
</spoiler>
<spoiler summary="Code (C++)">
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, q, a[N], cnt;
int main()
{
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; ++i)
{
scanf("%d",a+i);
cnt += a[i];
}
while(q--)
{
int opt, x;
...
Call animals whose A is smaller than the B of the animal before
Tutorial of Codeforces Global Round 13
171.
[Invitation] IICPC CodeFest 2025 ### Greetings, Codeforces Community!
We are thrilled to invite you to **CodeFest**, a premier competitive programming event brought to you by [IICPC](https://iicpc.com/), co-sponsored by [Citadel](https://www.citadelsecurities.com/) and [Jump Trading](https://www.jumptrading.com/), Associate sponsors as [Jane Street](https://www.janestreet.com/), [Hudson River Trading (HRT)](https://www.hudsonrivertrading.com/), [Landeed](https://www.landeed.com/) and [QuantInsti](https://www.quantinsti.com/) being the Knowledge Partner.
The camp is being hosted by the 8 IITs namely Madras, Delhi, Bombay, Guwahati, Hyderabad, Kharagpur, Roorkee and Indore and we are grateful for the same!
You can check our event announcement video [here](https://www.youtube.com/live/cKTUU0PEBYA?si=eEwZ0iiLaeiYkdM4).
---
### **Inspiration**
In late 2024, Ayush and I were wondering what could be done next to improve the Competit...
### **Call for ProblemSetters**
172.
ICPC Dhaka: Call for Fun Facts Fun Facts About World Finals Teams
==================
Are you participating in ICPC World Finals in Dhaka this week? Is someone from your team competing in World Finals? Did your best friend's brother meet someone whose cousin competed in regionals against a team who qualified? If so, we'd love to get some fun facts about the world finals team from you!
If you have any, please submit your fun facts [in this google form](https://forms.gle/VXfD95C4yDsoR2FPA), or send them in a private message to me, [user:SecondThread,2022-11-05], on Codeforces!
#### What kind of facts are you looking for?
Well variety is what makes things exciting, so we don't want to limit it too much. But for some inspiration, some good ones we've seen in the past include:
- I play Smash Melee competitively in my free time
- One of our team members (his_handle) is getting married within a week of finals
- I'm surprisingly n...
ICPC Dhaka: Call for Fun Facts
173.
Codeforces Round #299 Editorial ### [problem:535A]
First of all check if $n$ is one of the values $0, 10, 11, …, 19$. Then, let’s have array $x[]$ = {"", "", "twenty", "thirty", …, "ninety"} and $y[]$ = {"", "one", …, "nine"}.
Let $a = \frac{n}{10}$ and $b = n\ modulo\ 10$.
If $n$ is not one of the values above, then if $a=0$, print $y[b]$, else if $b=0$ print $x[a]$ otherwise print $x[a]$-$y[b]$.
Time complexity: $O(1)$
[Code](http://ideone.com/mytb2L) by [user:SoroushE,2015-04-02]
[Another Code](http://ideone.com/CqgNe5) by [user:PrinceOfPersia,2015-04-05]
[Another Code](http://ideone.com/dqiMNL) by [user:Haghani,2015-04-08]
[Python Code](http://ideone.com/6tZmNF) by [user:Zlobober,2015-04-04]
### [problem:535B]
Sol1: Consider $n$ has $x$ digits, $f(i) = $ decimal representation of binary string $i$, $m$ is a binary string of size $x$ and its $i-th$ digit is 0 if and only if the $i-th$ digit of $...
Let's call the answer for vertices $v$ and $u$ with edges $e_1, e_2, ..., e_k$
on the path, score
Tutorial of Codeforces Round 299 (Div. 2)
Tutorial of Codeforces Round 299 (Div. 1)
174.
How randomized solutions can be hacked, and how to make your solution unhackable Hi Codeforces! In Round 507 earlier today, a large number of "mostly correct" randomized solutions on [problem:1039B] were hacked. I wanted to write a quick explanation of how it's possible to hack these, as well as a guide on how to write your code so that you aren't vulnerable to getting hacked.
First to go over the solution quickly (skip down a few paragraphs if you already know the solution): one can use binary search to reduce the range of possible locations for the train to a constant multiple of $K$, such as $6K$. Just make sure to expand out both ends of the range by $K$ after every iteration. Once the range is at most $6K$, one can repeat the following:
1) Make a random guess out of the remaining numbers. The probability of success is at least $\frac{1}{6K}$.
2) Binary search again until the range is at most $6K$ again. It turns out this only takes one query, since after our previous guess our $6K$ range will become an $8K$ range, and a single query will reduce this t...
175.
Tutorial: The fastest tree algorithm, the XOR Linked Tree Hi Codeforces!
This is a blog about a really cool folklore technique that seems to have been forgotten over time. I currently only know of one place where it is mentioned on the internet, https://www.algonotes.com/en/minimal-memory-dp/, which is a tutorial by [user:monsoon,2024-10-20] for his problem "Matchings" https://dmoj.ca/problem/ontak2010sko from a POI training camp in 2010 ([see this for more information](https://codeforces.me/blog/entry/92090?#comment-807964)). But I've heard that this technique is even older than that. I originally learnt of this technique a couple of years back when I was digging through the fastest submissions on [problem:321-C] and I saw it being used in a submission [submission:9076307] by [user:Marcin_smu,2024-10-18] from 2014.
I don't know if there is a name for this technique, so I've decided to call it the _XOR Linked Tree_ because of its close connection to XOR linked lists https://en.wikipedia.org/wiki/XOR_linked_list.
The XOR Linked Tree is...
176.
Codeforces Round 1066 (Div. 1 + Div. 2) Editorial [problem:2157A]
Author: [user:TheScrasse,2025-11-22]<br>
Preparation: [user:TheScrasse,2025-11-22]
<spoiler summary="Hint 1">
Each value $x$ is independent of the others; only its own frequency matters.
</spoiler>
<spoiler summary="Hint 2">
In a balanced array, value $x$ must appear either $0$ times or **exactly** $x$ times.
</spoiler>
<spoiler summary="Solution">
- Each value $x$ is independent of the others; only its own frequency matters. In particular, for each value, find its frequency $f[x]$.
- In a balanced array, value $x$ must appear either $0$ times or **exactly** $x$ times. Specifically, if it appears $< x$ times at the beginning, you have to delete all its occurrences, otherwise you should keep $x$ occurrences. Specifically, for each $x$, add $f[x]$ to the answer if $f[x] < x$, else add $f[x] - x$.
Complexity: $O(n)$ time. Slower solutions (e.g., $O(n^2)$) are allowed.
</spoiler>
<spoiler summary = "Code">
[submission:350380351]
</spoiler>
[...
- We do not need the first call, because $v_{j-1}+m+1$ is neutral (proved
before). - The second
Tutorial of Codeforces Round 1066 (Div. 1 + Div. 2)
177.
Editorial of Codeforces Round 796 [problem:1688A]
Idea: [user:huangzirui,2022-06-03].
Solution: [user:huangzirui,2022-06-03].
Preparation: [user:huangzirui,2022-06-03].
Good problem
Average problem
Bad problem
Did not solve
<spoiler summary="Hint">
Consider $x=2^k$ and $x\ne 2^k$ separately.
</spoiler>
<spoiler summary="Solution">
Let $p_i$ be the $i$-th bit of $x$, $q_i$ be the $i$-th bit of $y$ (both indexed from $0$).
$x\ \texttt{and}\ y > 0\Leftrightarrow \exists i,\ p_i= q_i = 1$.
$x\ \texttt{xor}\ y > 0\Leftrightarrow \exists i,\ p_i\ne q_i$.
To satisfy the first condition, find the minimum integer $k$ satisfying $p_k=1$, and assign $1$ to $q_k$.
If $x\ne 2^k$, the second condition is satisfied now. Otherwise, find the minimum integer $j$ satisfying $p_j=0$, and assign $1$ to $q_j$.
The time complexity is $O(1)$.
</spoiler>
<spoiler summary="Code (C++)">
```cpp
#include<bits/stdC++.h>
...
We call a permutation $p$ of length $n-s$ is **good** if $\forall i
Tutorial of Codeforces Round 796 (Div. 1)
Tutorial of Codeforces Round 796 (Div. 2)
178.
Permutation group basis construction (Schreier–Sims algorithm) Hi everyone!
I had this blog drafter for quite a while, but the [$300 contest](https://codeforces.me/blog/entry/110840) motivated me to actually finish and publish it. I don't care about the prize that much as I think many other blogs published recently are talking about something even cooler. But I like to make people suffer, so I will apply anyway to make [user:peltorator,2023-01-12] read even more stuff >:)
Besides, the contest makes it harder to stay on contribution top, so I got to do something to stay afloat. That being said...
<hr>
Today I'd like to write about an algorithm that solves the following problem:
You're given a set of permutations $G = \\{g_1, \dots, g_m\\}$. Find the size $|\langle g_1, \dots, g_m \rangle|$ of the group generated by $G$.
At first, I wanted to get into a lot of group-theoretic details with proofs and all, but then I felt like it would make the article harder to comprehend, so I will try to keep group-theoretic stuff to minimum, whi...
179.
Making NTT convolution 10x faster with avx2 > Text is also available on [github pages](https://piskareviv.github.io/blog_aux_ntt_1/) (formatting may look a bit cleaner there)
> Thanks [user:alexxela12345,2025-05-05] for reviewing this blog
Hello everyone!
I want to share some of my thoughts and experiments on vectorizing NTT.
I prefer NTT to real-valued FFT because of the imprecision of the latter.
I use `avx2` because it is the most advanced vector extension supported by the majority of modern online judges (including Codeforces), as of 2024.
And I have no idea how many bugs (already found two) and how much UB my code contains, at least it passes some kind of tests.
### Benchmark info
All the benchmarks are performed on my `Ubuntu 22` `Intel i5-1135g7` laptop.
I execute `cpupower frequency-set -d 3.0ghz -u 3.0ghz` before benchmarks to (attempt to) fix CPU frequency for better accuracy.
Code is available at [github](https://github.com/piskareviv/blog_aux_ntt_1).
You can try running all the benchmarks o...
3. Allocating aligned memory with `_mm_malloc` is quite convenient, don't
forget tocall `_mm_free, I will call outer loop iterations in `transform` function for `k >= 3` top
layers, and all the
180.
New Programming Contest Website: AtCoder Hello!
We made a new programming contest website called [AtCoder](http://new.atcoder.jp). I'm the admin of AtCoder.
The first international contest called AtCoder Grand Contest 001 will be held on this Saturday [(Time)](http://www.timeanddate.com/worldclock/fixedtime.html?iso=20160716T2100&p1=248), and we are planning to hold a lot of contests regularly.
This time the problems were written by [user:snuke,2016-07-13]. We invite you to participate in our contests!
See [AtCoder's Website](http://new.atcoder.jp) for detailed information.
181.
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...
the second recursive call and before returning the answer. Therefore, the
overall running time is
182.
[Tutorial] Blossom Algorithm for General Matching in O(n^3) I have decided to write a tutorial on a topic not even [user:Um_nik,2021-06-29] knows! ([source](https://codeforces.me/blog/entry/92248))
In this tutorial, I will talk about the blossom algorithm, which solves the problem of **general matching**. In this problem, you are given an undirected graph and you need to select a subset of edges (called matched edges) so that no two edges share a vertex, and the number of matched edges is maximized. More common in competitive programming is bipartite matching, which is the same problem but when the graph is guaranteed to be bipartite. In competitive programming, general matching seems to get a lot of hate for being very challenging to implement. However, the blossom algorithm is quite beautiful, and important in the history of algorithm research.
It will help if you are already familiar with bipartite matching. I will discuss the high level ideas of the algorithm, but my main focus will be on the tricky implementation details. So you may...
constructed the paths from $x$ and $y$ to the root (call the paths `vx` and
`vy`). First, we need to
183.
[Tutorial] How to read editorials Hello everyone,
in this blog I'm trying to convince you that editorials are useful, especially if you read them "correctly".
#### "Algorithm $1$" vs "Algorithm $2$"
This is what many users do when reading the editorial for one problem (let's call it "algorithm $1$"):
- Read it.
- Repeat until able to implement the solution.
- Implement the solution; possibly forget about any previous attempt to solve that problem without editorial, and any detail in the editorial that seems unrelated to the implementation of the solution.
- Possibly, read the comments trying to find out how it is possible to come up with the solution in the editorial.
This is what you should do in my opinion (let's call it "algorithm $2$"):
- Keep the editorial open until you are able to implement the solution, using both your ideas and editorial's ideas: sometimes, this just means opening the editorial for $1$ second, because you had already found most of the ideas on your own.
- Implement the so...
This is what many users do when reading the editorial for one problem (let's
call it "algorithm $1$"):, This is what you should do in my opinion (let's call it "algorithm $2$"):
184.
Catching the Mole (Psychotic_D cheating accusation) Hello codeforces! You guys must have seen the recent blog accusing international master [user:Psychotic_D,2024-07-23] of cheating in the most recent div2 round: [Codeforces Round 960 (Div. 2)](https://codeforces.me/contest/1990). This is due to the fact that the author, [user:wuhudsm,2024-07-23] is [user:Psychotic_D,2024-07-23]'s friend and that [user:Psychotic_D,2024-07-23] had a ridiculous performance, winning the amongst official participants.
They are both big members of [TheForces](https://theforces.netlify.app/), raising suspicions of whether there was some collusions between the two.
At first i thought it was nonsense since the evidence was lacking, but after a bit of my own investigation I've compiled the most interesting pieces of evidence of why i believe [user:Psychotic_D,2024-07-23] (along with some accomplices from TheForces) is in fact a cheater.
Case #1: Introduction
------------------
I first learned about the sub...
this $50 \times 50$ table that is calculated every call of solve. If you check
any other submission
185.
So you're a proud ratist? Here's why that's problematic (GRAYtist v1.1 out now) Just kidding, I'm one too.
<img src="https://raw.githubusercontent.com/welcome-to-the-sunny-side/graytist/main/public/wordmark.png?v=2" alt="GRAYtist" style="float:right; width:400px; height:auto; margin-left:24px; margin-bottom:8px;">
Introducing [GRAYtist](https://chromewebstore.google.com/detail/graytist/bflnfmllkbhilogfbdilcckpkfganelc), a browser extension that helps you filter out low-quality content from Codeforces.
You might say: "B-b-but [user:DNR,2026-06-12], such a tool would surely spam some API calls or use some heavyweight classifier models! My potato PC couldn't handle it, right?!".
Wrong. We instead use the principle of ratism ($P(\text{low rating} \iff \text{low quality}) \approx 1$) to optimize away all of that nonsense.
<div style="clear:both;"></div>
### Features
##### 1. Filter blogs by author rank and title.
- Don't want to see blogs from grays because they're annoying, and blogs from nutellas because they make you feel inferior? GRAYtis...
186.
Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2) Editorial Thank you for participation and we hope you enjoy this round ヽ(^ o ^)/.
During the contest, there was a small issue in problem D. For those affected, we have skipped your duplicate submissions (if your duplicate submissions were not skipped, please let us know). We apologize again for any inconvenience caused.
In addition, we are honored to invite you to our unofficial round tomorrow (*╹▽╹*) [Invitation to TheForces Round #22 (Interesting-Forces)](https://mirror.codeforces.com/blog/entry/119771)
### [1864A-Increasing and Decreasing](https://mirror.codeforces.com/contest/1864/problem/A)
Idea : [user:wuhudsm,2023-08-27]
<spoiler summary="Tutorial">
We use the following greedy construction:
For all $i$ ($1<i<n$), set $a_i=a_{i+1}-(n-i)$. If $a_2-a_1 \geq n-1$, we've found a solution, otherwise there is no solution.
Proof. Assume there's a solution which includes an index $i$ ($1<i<n$) such that $a_{i+1}-a_i>n-i$. We can make $a_j:=a_j+\Delta$ for all $j$ ($2 \le j ...
If after a row shift, all numbers moved are in the correct column, we call such
rows available
187.
DP on Function Calls — Remove a Log Factor I wanted to write down a very short blog on this technique, since I've encountered it a few times but have not seen it formally discussed anywhere. _Theoretically_ this technique shaves off a log factor from the complexity, but in practice the technique often only yields a constant factor speed-up, so it's more of a micro-optimization than anything. I think it's interesting enough to warrant discussion anyway, but that's probably the reason why this technique is niche.
Let's assume that all lowercase variables here are integers, all uppercase variables are matrices, and that computations are done modulo some large prime. We use $I$ to refer to the identity matrix and $0$ to refer to the zero matrix.
**Warmup Problem:** Given a square matrix $A$ and a positive integer $n$, evaluate $A^n$.
Matrices are the classic example of the fast exponentiation algorithm working not just with standard multiplication of integers, but on any object equipped with an associative binary oper...
calls, and within each function call we need to perform an $\mathcal{O}(\lg
n)$ operation (the fast, I am going to call the following technique "DP on Function Calls", since I
can't seem to find a
188.
[Tutorial] More about minimum cost flows: potentials and Dinitz [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](https://codeforces.me/blog/entry/105330)
**Part 3: [Tutorial] More about minimum cost flows: potentials and Dinitz**
#### Introduction
As mentioned in the introduction of [part 2](105330), there is something in out ICPC
notebook called "min cost dinic". This cycle (no pun intended) of blogs was initially
meant to be just one blog explaining it all, but in time it developed into something
much longer. The general idea here doesn't appear to be particularly widely discussed, but it is
certainly not novel either; [TopCoder](https://www.topcoder.com/thrive/articles/Minimum%20Cost%20Flow%20Part%20Two:%20Algorithms), for example, calls it
the primal-dual algorithm (why is it called that? That's a story for another
time, but it has to do with [LP duality](105049).)
Picking up from where we left off, there a...
189.
Multi-dimensional ternary search Hi everyone!
I'm currently trying to write an article about $\lambda$-optimization in dynamic programming, commonly known as "aliens trick". While writing it, I stumbled upon a fact which, I believe, is a somewhat common knowledge, but is rarely written out and proved explicitly. This fact is that we sometimes can repeatedly use ternary search when we need to optimize a multi-dimensional function.
Thanks to
- [user:mango_lassi,2021-12-30] for a useful discussion on this and for counter-example on integer ternary search!
- [user:Neodym,2021-12-31] for useful comments and remarks about the article structure.
[cut]<br>
#### $1$-dimensional search
---
**Def. 1**. A function $f : X \to \mathbb R$, where $X \subset \mathbb R$, is called **unimodal** if there is a segment $[L, R]$ such that $f(x)$ strictly decreases on $(-\infty, L] \cap X$, strictly increases on $x \in [R,+\infty) \cap X$ and is equal to its global infimum on $x \in [L, R] \cap X$.
---
**Ternary s...
190.
Counting perfect matchings Thanks to [user:t.ravnushkin,2024-09-27] for helping in writing contents of this blog. Thanks to [user:Alexdat2000,2024-09-27] for proof-reading and to [user:bashkort,2024-09-27] for announcing the month of blog posts. Even though I have started writing this blog before the announcement it would have probably been left in a trash bin due to my laziness.
# Introduction
Matching is a beloved topic throughout competitive programming community due
to its simple nature and fun applications. Matchings are not only useful
in graph theory, but are also essential in topics such as game theory,
partially ordered sets and combinatorics. In this blog we are gonna talk
about less known applications of the subject. The main goal of the blog
is explaining the intuition behind being able to associate the number of some
combinatorial species to the amount of perfect matchings and understanding
when it is possible to efficiently compute their counts. The blog mainly
consists of two parts: ...
191.
The 2025 Universal Cup Online Challenge is Happening Soon! <center>
<img src="/predownloaded/43/f6/43f69acd4c854a20d5f7064fe6252b346f9f5d5a.png" style="height:262.0px;max-width:
100.0%;max-height: 100.0%; ">
</center>
**UPD: The [contest platform](https://challenge.ucup.ac/) is up! Everyone can now register through the platform!!!!**
**UPD: The champion will be invited as a guest (with full accommodation and travel expense covered) to the 2026 Universal Cup Finals. The champion will be awarded at the time and will be invited to participate in the onsite challenge.**
Hello Codeforces!
We are very happy to announce that, after months of preparation, we have finally scheduled our first online challenge from December 17th to December 24th! Sponsored by Huawei, we have prepared valuable prizes for everyone to compete for! Although many details are still to be finalized, we are too excited to share the following details with you as an early Christmas gift!
- Contest Name (Subject to Change): The 2025 Universal Cup Online Challenge...
our best to make it as good as possible, and we call on everyone to support
this challenge by
192.
on minimizing the expected number of recursive calls for segment tree For the longest time, this comment https://codeforces.me/blog/entry/112755#comment-1004966 was bugging me (the part about how the 'complete' segment tree is 20% slower (complete, because it’s a complete binary tree)). Instead of benchmarking, this blog calculates the expected number of recursive calls visited between segment tree implementations.
Thanks to [user:camc,2025-03-03] for giving valuable feedback.
This blog will study 2 implementations of segment trees.
<spoiler summary="'standard' segment tree">
~~~~~
void dfs(int v, int l, int r) { // [l, r)
if (r - l == 1) {
return;
}
int m = (l + r + 1) / 2;
dfs(2 * v, l, m);
dfs(2 * v + 1, m, r);
}
// dfs(1, 0, n);
~~~~~
</spoiler>
And
<spoiler summary="'complete' segment tree">
~~~~~
int split(int l, int r) {
int pw2 = 1 << __lg(r - l);
return min(l + pw2, r - pw2 / 2);
}
void dfs(int v, int l, int r) { // [l, r)
if (r - l == 1) {
return;
}
int m = split(l, r);
dfs(2 ...
193.
About Codeforces Round 901 (Div.1, Div.2) First of all, I'm sorry for the unreasonable difficulty. The problems are much harder than usual, so we choose 3 hours. But it seems that it didn't work :(
About the problems:
- [problem: 1874C] : It seems that the out-degree of the vertex is not maximized, [user:znstz2018,2023-10-01] prepared it for me, but I forgot to check the data, I'm sorry for the unfairness caused to the round.
- [problem: 1874D] : There are some hacks appearing in this problem. Some adjustments in the approximate solution past the problem, but there's really nothing I can do about it. Hack can only make the adjustments you need to make larger, but if you have a good approximate solution and adjust up to about $[-50, +50]$. You can pass all the test cases satisfying $1 \leq n \leq m \leq 3000$. Also, different approximate solutions have different hacks for them, we really have no way to hack all of them. But luckily, no matter what solution you use, you must know $ans = n + 2 \times \sum_{i=1}^n\sum_{j=...
delete two values of numbers, let's call them $x$ and $y$ $(x < y)$. We will
delete all of $y$, and we
194.
One thing you should know about comparators — Strict Weak Ordering Is "In C++, comparator should return false if its arguments are equal." [all you should know about comparators in C++](https://codeforces.me/blog/entry/70237)?
**Definitely NOT.**
### What's the requirement of the custom comparator in STL?
It should be a *Strict Weak Ordering*. In other words, let the comparator be $f$, and $f(x, y)=true$ means $x< y$, then:
1. $f(x, x)$ must be false (Irreflexivity)
2. If $f(x, y)$ is true, then $f(y, x)$ must be false. (Antisymmetry)
3. If $f(x, y)=true$ and $f(y, z)=true$, then $f(x, z)$ must be true. (Transitivity)
4. If $f(x, y)=false$, $f(y, x)=false$, $f(y, z)=false$ and $f(z, y)=false$, then $f(x, z)=false$ and $f(z, x)=false$. (Transitivity of equivalence)
In fact, *Antisymmetry* can be deduced by *Irreflexivity* and *Transitivity*, so we can ignore it.
Here are some examples that these rules aren't satisfied:
| Comparator | Irreflexivity | Transitivity | Transitivity of equivalence | Example |
| :----------: | ...
195.
Codeforces Round #652 (Div. 2) Editorial ####[A. FashionabLee :](https://codeforces.me/contest/1369/problem/A)
Invented by [user:DeadlyCritic,2020-06-16].
<spoiler summary="Brief Solution">
$\mathcal Brief\;\mathcal Solution :$
A $n$-regular convex polygon is beautiful if and only if $n \% 4 = 0$. ($\%$ is the modular arithmetic symbol)
</spoiler>
<spoiler summary="Complete Proof">
[tutorial:1369A]
</spoiler>
<spoiler summary="Python solution">
~~~~~
t = int(input())
for testcase in range(t):
n = int(input())
if(n%4 == 0) :
print("Yes")
else :
print("No")
~~~~~
</spoiler>
<spoiler summary="C++ solution">
~~~~~
#include <iostream>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
if(n % 4 == 0){
cout << "YES\n";
}
else cout << "NO\n";
}
}
~~~~~
</spoiler>
####[B. AccurateLee :](https://codeforces.me/contest/1369/problem/B)
Invente...
food? They can always eat this food no matter what happens, so lets call them
as late as possible(so
Tutorial of Codeforces Round 652 (Div. 2)
196.
Avito Cool Challenge 2018 Editorial [problem:1081A]
Idea: [user:yjq_naiive,2018-12-17] Developer: [user:yjq_naiive,2018-12-17]
<spoiler summary="Hint">
1 sounds like the minimum value we can get. Why? Is it always true?
</spoiler>
<spoiler summary="Solution">
When $n \leq 2$, we can do nothing.
When $n \geq 3$, since $1<\frac{n}{n-1}<2$, $n-1$ isn't a divisor of $n$, so we can choose it and get $1$ as the result.
</spoiler>
<spoiler summary="Code (yjq_naiive)">
~~~~~
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
if (n == 2) {
puts("2");
} else {
puts("1");
}
return 0;
}
~~~~~
</spoiler>
[problem:1081B]
Idea: [user:yanQval,2018-12-17] Developer: [user:yanQval,2018-12-17]
<spoiler summary="Hint">
Consider the number of people wearing hats of the same color.
</spoiler>
<spoiler summary="Solution">
let $b_i=n-a_i$ represent the number of people wearing the same type of hat of $i$-th person.
Notice that the person wear...
If $S=pq$, $p$ and $q$ are palindromic and non-empty, we call $(p,q)$ a
palindromic decomposition
197.
Nimbers and Sprague-Grundy theorem Hi everyone!
Today I'd like to write about the so-called Grundy numbers, or nimbers. I will start by providing a formal recap on the Sprague-Grundy theorem and then will advance to the topic that is rarely covered in competitive programming resources, that is I will write about nimber product and its meaning to the game theory.
_I was asked to add the following to the blog: THANK SIR MASTER [user:ADAM_GS,2022-06-12] FOR GREAT AND VALUABLE REVIEW SIR_
## Prerequisites
Familiarity with the following concepts:
- Basic [set theory](https://en.wikipedia.org/wiki/Set_theory) notion: [union](https://en.wikipedia.org/wiki/Union_%28set_theory%29), [cartesian product](https://en.wikipedia.org/wiki/Cartesian_product) and [symmetric difference](https://en.wikipedia.org/wiki/Symmetric_difference) of sets, [set of all subsets](https://en.wikipedia.org/wiki/Power_set) denoted as $2^A$, etc;
- [Groups](https://en.wikipedia.org/wiki/Group_%28mathematics%29) and [fields](https://en.wiki...
198.
ICPC North America Championship: Call for Fun Facts Fun Facts about NAC Teams
==================
Are you or someone you know attending the North America Programming Camp? If so, we'd love to get some fun facts about the teams that are here!
Please submit your fun facts [in this google form](https://forms.gle/6urswk25LchFw2uR6), or send them in a direct message to me, [user:SecondThread,2023-05-27] on Codeforces!
What kind of facts are you looking for?
------------------
We're looking for anything exciting, interesting, or varied about your team that you're willing to share. Some great examples that we've seen in the past include:
- I play Smash Melee competitively in my free time
- One of our team members (his_handle) is getting married within a week of finals
- I'm surprisingly not actually a Computer Science major, instead I'm majoring in x and plan to use it for y.
- 2/3 of our team uses the non-C++ programming langua...
ICPC North America Championship: Call for Fun Facts
199.
CodeForces Round 872(Div. 1&2) Editorial ## A. LuoTianyi and the Palindrome String
Consider the substring of $s$ from the second character to the last, or $s_2s_3\cdots s_n$. If it's not palindrome, then the answer must be $n-1$. What if it's palindrome? This implies that $s_2=s_n$, $s_3=s_{n-1}$, and so on. Meanwhile, the fact that $s$ is palindrome implies $s_1=s_n$, $s_2=s_{n-1}$, etc. So we get $s_1=s_n=s_2=s_{n-1}=\cdots$ or that all characters in $s$ is the same. In this situation, every subsequence of $s$ is palindrome of course, so the answer should be $-1$.
<spoiler summary="Code">
```cpp
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#define ll int
#define ft first
#define sd second
//#define endl '\n'
#define pb push_back
#define ll long long
#define pll pair<ll,ll>
#define no cout<<"NO"<<'\n'
#define no_ cout<<"No"<<'\n'
#def...
Call a node special if there is a person in it.
Tutorial of Codeforces Round 872 (Div. 1)
Tutorial of Codeforces Round 872 (Div. 2)
200.
Rumination on AI and competitive programming An OpenAI model can now achieve a rating of 1800 in Codeforces. That made me wonder about the future of competitive programming and why we do this. I came up with some opinions, which I'll be glad to share with you.
## AI killed the competitive programming?
I don't think that's happening, because competitive programming is useless! Some people might think CP is less interesting because AI can solve CP problems — but come on, problemsetter can solve those problems, unless they are really bad. Many people still play Chess just fine, and I recently enjoyed participating in Sudoku competitions, although I was completely aware that computers would wreck me in a second. It didn't matter, and I didn't see how it could.
CP problems are not "open problems" — if they are, the problemsetters are to blame. So, you are not contributing anything to the world by solving CP problems; it all comes down to personal interest. As long as CP is fun for people, they will do it.
## Flag...
A problem should be judged independently over how well AI can solve it, and
it's the rightcall to
201.
Codeforces Round 887 (Div 1, Div 2) Tutorial We hope you enjoyed these problems :) This contest has been in the works for almost a year.
<spoiler summary = "About the Authors">
This round was mostly made possible by problemsetters from the [CerealCodes](https://www.cerealcodes.org/) initiative!
CerealCodes is an organization based in the United States dedicated to running high quality competitive programming contests. You can check out our previous contest [here](https://codeforces.me/gym/103886).
</spoiler>
**UPD: D1D Editorial have been updated**
**UPD 2: D1D Editorial now has images by [user:EmeraldBlock,2023-08-01]. As an apology gift for being so slow, the image generator is programmatic and available [here](https://artofproblemsolving.com/texer/codeforces).**
#### [problem:1853A]
Problem Credits: [user:buffering,2023-06-02]
Analysis: [user:buffering,2023-06-02]
<spoiler summary="Hint 1">
To make $a$ not sorted, we just need to pick one index $i$ so $a_i > a_{i + 1}$. How do we do this?
</spoiler...
Call the number of adjacent pairs of cells with different characters
Tutorial of Codeforces Round 887 (Div. 1)
Tutorial of Codeforces Round 887 (Div. 2)
202.
How not to read problem statements I wanted to write super-harsh blog but then I decided to split it into educational part and whining part. This is whining part. To read some cool stuff go [here](https://codeforces.me/blog/entry/62730). This one will also be educational on a slightly different topic. And there will be A LOT of harsh stuff.
I'm not saying that I'm perfect. That round had some really bad problemsetting issues. Problem E was googleable, problem D had very weak tests against very stupid solution (so stupid that none of the authors and testers come up with it, moreover, it is so counter-intuitive that I don't know how so many people independently did it). In two constructive problems participants could look at jury's output, the feature of which I didn't know. And I'm sorry for these issues. BUT. [This comment](https://codeforces.me/blog/entry/62614#comment-466588) has very negative rating despite being so true. And no one are here to back me up. So I want to speak my truth as I always do.
Let me ac...
203.
[Shitpost] How to Teach Kids Basic Data Structures Using the Methods of a Mathematics Textbook ## Conventions
This article is based on ordinary set theory. Natural numbers, integers, finite sequences, maps, Cartesian products, total orders, trees, induction, and the finite recursion theorem are assumed to be established. Write $\mathbf N=\{0,1,\ldots\}$ and $\mathbf N_{>0}=\mathbf N\setminus\{0\}$. All trees are finite trees; all intervals not otherwise qualified are integer intervals.
For $l,r\in\mathbf Z$, put
$$
[l,r]=\{i\in\mathbf Z:l\le i\le r\},\qquad [n]=[1,n].
$$
When $l>r$, $[l,r]=\varnothing$. For a nonempty finite set $E$, $|E|$ denotes its cardinality. The symbol $\sqcup$ denotes disjoint union. Composition of maps follows the convention $(f\circ g)(x)=f(g(x))$.
For $n\ge1$, put
$$
\lambda(n)=1+\lfloor\log_2 n\rfloor.
$$
All asymptotic estimates are taken as $n\to\infty$; bounds written in terms of $\lambda(n)$ also apply to $n=1$.
**Computational conventions.** Unless otherwise stated, we use the random-access machine model with word leng...
Q$, output $u$ and terminate this call; otherwise, in left-to-right order,
recursivelycall on the
204.
[Tutorial] Catalan Numbers and Catalan Convolution Catalan Numbers is a well known sequence of integers that appear in combinatorics, there is a chance that you might have run into such counting problems and you might have even solved them with DP without realizing that they are a known sequence. Here is a problem to get us started.
### Binary Trees Count
Find the count of different binary trees with $n$ nodes, we'll denote to that by $C_n$. This can be solved by observing the substructure of the problem:
From the root, the left subtree $a$ can be _any_ binary tree of size $x$, the right subtree $b$ can be _any_ binary tree of size $y$, such that $x+y=n-1$ (as we took one node as the root). With the base case at $C_0=1$ as the empty tree is a valid tree of size $0$. This directly gives us the answer by the following recurrence relation: (Segner's recurrence relation)
$$ C_{n+1} = \displaystyle\sum_{i=0}^{n}{C_i C_{n-i}}, n \geq 0; C_0=1 $$
...
205.
Codeforces Round #300 Editorial (+challenges) As usual, a challenge comes with every problem. I tried not to repeat the mistakes of my previous editorials and made sure that all challenges have a solution =) (except for the _italics_ parts that are open questions, at least for me). Go ahead and discuss them in the comments! General questions about problems and clarification requests are welcomed too.
**UPD**: I added codes of my solutions for all the problems. I didn't try to make them readable, but I believe most part of them should be clear. Feel free to ask questions.
[problem:538A]
Let me first clarify the statement (I really wish I didn't have to do that but it seems many participants had trouble with the correct understanding). You had to erase exactly one substring from the given string so that the rest part would form the word `CODEFORCES`. The (somewhat vague) wording `some substring` in the English translation may be the case many people thought that many substrings can be erased; still, it is beyond my understa...
**Challenge (easy)**. Let us call a number _pseudo-binary_ if its decimal
representation contains
Tutorial of Codeforces Round 300
206.
A proper tutorial for one of the craziest 3D-geometry problems Warning: This problem is like the warden of competitive programming. It is a force of nature — like a hurricane, and when you see a hurricane you don't fight it, you run. It is a big bad boss with a bunch of hitpoints, and deals big damage to your sanity. But when you kill it, it doesn't drop much loot, experience, or educational value compared to other problems. It would be wiser to go and solve some problems and learn how to use binary search.
The problem: https://codeforces.me/gym/102452/problem/F
It's tutorial says: Since n is small, $O(n^2)$ simulation is OK. Advanced 3-D geometry methods are highly required.
The tutorial doesn't describe what the advanced 3-D geometry methods are. So, I have written this blog to remedy that gap.
<spoiler summary="Chapter 1. Prologue">
You should create a `point` struct this makes things a bit easier. It has an `double x`, `double y`, `double z` coordinate. This point will be immensely useful, as we can define a line segment...
)$. Essentially, you can call `double pointsphere(center, sc1, sc2, rad1+rad2)`
and it should return
Tutorial of 2019-2020 ICPC Asia Hong Kong Regional Contest
207.
Codeforces LATOKEN Round 1 (Div. 1 + Div. 2) Editorial [problem:1534A]
Author: [user:Crackersamdjam,2021-06-13]
<spoiler summary="Hint 1">
Let's say you know the colour of the first square, what colours can you figure out next?
</spoiler>
<spoiler summary="Hint 2">
Colour it like a chessboard, but there's more than one possible chessboard!
</spoiler>
<spoiler summary="Hint 3">
Brute force the color of the first square!
</spoiler>
<spoiler summary="Tutorial">
[tutorial:1534A]
</spoiler>
<spoiler summary="Solution">
[submission:119400830]
</spoiler>
[problem:1534B]
Author: [user:Dormi,2021-06-13]
<spoiler summary="Hint 1">
Consider the contribution of each pillar to the answer.
</spoiler>
<spoiler summary="Hint 2">
How does doing the operation on a pillar change the contribution to the answer?
</spoiler>
<spoiler summary="Hint 3">
You only want to do an operation on a pillar if the top cell contributes 2 to the answer.
</spoiler>
<spoiler summary="Tutorial">
[tutorial:1534B]
</spoiler>
...
eventually be disturbed (call them special).
Tutorial of Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)
208.
[Tutorial] Slope Trick Hi everyone! Following my [last article](http://codeforces.me/blog/entry/47764), today I'm writing about a not-so-common trick that has nevertheless appeared in some problems before and might be helpful to you. I'm not sure if this trick has been given a name yet so I'd refer to it as "Slope Trick" here.
Disclaimer : It would be helpful to have a pen and paper with you to sketch the graphs so that you can visualize these claims easier.
Example Problem 1 : [problem:713C]
This solution originated from [user:koosaga,2016-10-16]'s comment in the editorial post [here](http://codeforces.me/blog/entry/47094?#comment-315161).
The solution below will solve this problem in $O(n\log n)$, wheareas the intended solution is $O(n^2)$.
So, the first step is to get rid of the strictly increasing condition. To do so, we apply `a[i] -= i` for all $i$ and thus we just have to find the minimum number of moves to change it to a non-decreasing sequence.
Define $f_{i}(x)$ as the minimum n...
209.
Petition to change Bugabooset back to Problemset (with valid reasons) So long story short, Problemset got renamed to Bugabooset. [(Full story if you're interested)](https://codeforces.me/blog/entry/91134)
Don't get me wrong, I personally find it extremely amazing, but I still want this change to be reverted.
I have some valid reasons:-
- Whenever some newcomer asks me for advice... I say something like, _"Go to the Codeforces Problemset and sort the problems by difficulty and then solve a few everyday"_, now recently what is happening is that, a lot of newcomers can't find the problemset (because it does not exist anymore!!).
- If I tell them to go to the bugabooset, they will ask me what is that and what it means, and that's one story that I do not want to explain to someone for the 348th time!
- The link still points to **"http://codeforces.me/problemset"**, I think this discrepancy is very confusing... Now some might say, we can change it to **"http://codeforces.me/bugabooset"** but that'll unnecessarily ruin many people's bookmarks (un...
think they will call them "bugaboos" now? They won't!** They'll still call it
"question" and many
210.
Fixing the contest management mess ...or "How legacy systems fight obstacles no sane person would introduce in the first place".
Hello, Codeforces!
I am sure that those of you who tried to host their own programming competitions or write their own utilities for contest management are aware of the state of affairs regarding contest hosting. There are lots of incompatible formats, no one knows exactly how stuff ought to work, Polygon is full of nondescript and seemingly contradictory options, ej-polygon never seems to work quite correctly, modifications have to be applied to jury archives to make them work on your particular installation, non-trivial problem types require constant maintenance and hacks, *ad infinitum*.
Personally, I stumbled upon all these problems when I tried to get my own judge system working and suddenly discovered that the difficult part is not judging complex problems, but handling artificial complexity introduced by legacy software and standards. So here I am, attempting to solve these pro...
- What I shall call **formulaic problems**, when the user solution outputs a
formula or a universal
211.
Osijek Competitive Programming Camp 2023 fall — wrap Hi everyone!
<center><a href="https://ocpc.mathos.unios.hr"><img src="https://ocpc.mathos.unios.hr/images/ocpc.svg" height="100px"></a></center>
<center>
<b>Supported by</b><br>
<a href="https://www.janestreet.com/join-jane-street/open-roles/?type=students-and-new-grads&location=london">
<img src="/predownloaded/ee/f2/eef26616a3661c658d1545f18ed21fabb14d5871.svg" height="50px" style="margin: 5px 5px 5px 5px;"></a>
<a href="https://icpc.foundation/"><img src="https://ocpc.mathos.unios.hr/images/ICPC.svg" height="70px" style="margin: 5px 5px 5px 5px;"></a>
<a href="https://pinely.com/">
<img src="/predownloaded/0a/0f/0a0f3f67435d1f6e467bc7203d4a2090ba8f92cc.svg" height="50px" style="margin: 5px 5px 5px 5px;"></a><br>
<a href="https://artofproblemsolving.com/"><img src="https://ocpc.mathos.unios.hr/images/aops.svg" height="40px" style="margin: 5px 5px 5px 5px;"></a>
<a href="https://www.wolfram.com/">
<img src="https://ocpc.mathos.unios.hr/images/wolfram.png" height="40...
#### Call for problemsetters
212.
[Tutorial] The residual graph and working with the set of all minimum cuts I have previously written about flows in these blogs: [1](https://codeforces.me/blog/entry/104960), [2](https://codeforces.me/blog/entry/105330), [3](https://codeforces.me/blog/entry/105658).
Minimum cuts are a very fascinating topic for me. There are a lot of maximum flow problems where there's a fairly simple chain of reductions leading to "you should use flow", but there are also a lot of flow problems where flow comes apparently out of nowhere. Particularly fascinating are those where it's more convenient to think in terms of minimum cut: they work, because minimum cut allows you to model partitioning a set in two, with some additional implication-like constraints. Here are a couple of problems with that nature:
- [ARC085E \- MUL](https://atcoder.jp/contests/arc085/tasks/arc085_c) (this reduction is almost standard these days)
- [ARC142E \- Pairing Wizards](https://atcoder.jp/contests/arc142/tasks/arc142_e)
- [problem:104925D]
There are also flow problems on graphs ...
213.
Problems with clock timing on Codeforces After making several submissions earlier today to [problem:1463F] that all involved calling `clock()`, I think I've found some major inconsistencies in clock timing on Codeforces.
I had a solution that was correct but borderline on runtime because it needs to generate enough data to extrapolate from (via Berlekamp-Massey). So I made it iterate until 3.8 seconds, and looking through the submission list, it appears I wasn't the only one with this type of idea. Unfortunately I got WA on several submissions: [submission:101579005] [submission:101581695] [submission:101583625]. The strange thing was that each test case that resulted in WA didn't actually run for the full 3.8s, but only about half of that. When I took the same code and ran it in [custom invocation](https://codeforces.me/problemset/customtest) with the same input, it used the full 3.8 seconds and got the right answer each time.
So what's going on here? To try to figure this out, I set up a simpler version of some timed...
214.
p-adic exponent or why there is a primitive root modulo powers of prime numbers (except 2) Hi everyone!
You probably know that the primitive root modulo $m$ exists if and only if one of the following is true:
- $m=2$ or $m=4$;
- $m = p^k$ is a power of an odd prime number $p$;
- $m = 2p^k$ is twice a power of an odd prime number $p$.
Today I'd like to write about an interesting rationale about it through $p$-adic numbers.
Hopefully, this will allow us to develop a deeper understanding of the multiplicative group modulo $p^k$.
### Tl;dr.
For a prime number $p>2$ and $r \equiv 0 \pmod p$ one can uniquely define
$$
\exp r = \sum\limits_{k=0}^\infty \frac{r^k}{k!} \pmod{p^n}.
$$
In this notion, if $g$ is a primitive root of remainders modulo $p$ lifted to have order $p-1$ modulo $p^n$ as well, then $g \exp p$ is a primitive root of remainders modulo $p^n$.
Finally, for $p=2$ and $n>2$ the multiplicative group is generated by two numbers, namely $-1$ and $\exp 4$.
[cut]<br>
### $p$-adic numbers
We define a $p$-adic number $r$ as a formal po...
215.
[Tutorial] Cartesian tree and some related problems The Cartesian Tree is a useful concept for solving some problems which revolve mainly about thinking of the range of maximality of elements. It also provides a sort of "persistance" to the algorithm of monotonic stack, if you will. In this blog, we will learn what a Cartesian Tree is, how to construct one and solve some related problems to strengthen our understanding. Let's begin!
<hr>
#### What is a Cartesian Tree?
Let's consider an array $a$ where all values are distinct. The Cartesian Tree for the array $a$ is a binary labeled tree build recursively from the function $get(l,r)$ which constructs our desired tree from the subarray $l...r$.
Now let's define $get(l,r)$
- First root the tree at index $i$ such that $a_i = min(a_l,a_{l+1},...,a_r)$. Note that because all values are distinct, $i$ will always be unique.
- The aforementioned index will become the root of the Cartesian Tree. It's left and right subtrees will be recursively generated by $get(l,i-1)$ and $get(...
216.
Codeforces Round #873 (Div. 1 & 2) Editorial ## [problem:1828A]
Idea: [user:thenymphsofdelphi,2023-05-14] <br>
Preparation: [user:Mike4235,2023-05-14]
<spoiler summary="Hint 1">
Remember the sum of the first $n$ positive integers?
</spoiler>
<spoiler summary="Hint 2">
Every positive integer is divisible by $1$.
</spoiler>
<spoiler summary="Solution">
Consider the array $a = \left[1, 2, \ldots, n\right]$ that satisfies the second condition. It has the sum of $1 + 2 + \dots + n = \frac{n(n+1)}{2}$.
One solution is to notice that if we double every element $(a=\left[2, 4, 6, \ldots, 2n\right])$, the sum becomes $\frac{n(n+1)}{2} \times 2 = n(n + 1)$, which is divisible by $n$.
Another solution is to increase the value of $a_1$ until the sum becomes divisible by $n$. This works because every integer is divisible by $1$, and we only need to increase $a_1$ by at most $n$.
Time complexity: $\mathcal{O}(n)$
</spoiler>
<spoiler summary="Implementation 1">
```c++
#include <bits/stdc++.h>
using namespace s...
Call the last $n-k$ elements as special numbers.
Tutorial of Codeforces Round 873 (Div. 1)
Tutorial of Codeforces Round 873 (Div. 2)
217.
think-cell Round 1 Editorial Thank you for your participation! I hope you liked atleast one problem from the set (:
[problem:1930A]
Idea: [user:satyam_343,2024-02-18]
Editorial: [user:Non-origination,2024-02-18]
<spoiler summary="Hint 1">
Selecting the smallest two elements on the whiteboard is a good choice in the first move.
</spoiler>
<spoiler summary="Solution">
Let $b$ denote the sorted array $a$. Assume that $b$ contains only distinct elements for convenience. We prove by induction on $n$ that the maximum final score is $b_1 + b_3 + \ldots + b_{2n-1}$.
For the base case $n = 1$, the final and only possible score that can be achieved is $b_1$.
Now let $n > 1$.
**Claim**: It is optimal to choose $b_{1}$ with $b_{2}$ for some move.
<spoiler summary="Proof">
Suppose that in some move, $b_{1}$ is choosen with $b_i$ and $b_{2}$ is choosen with $b_j$, for some $2 < i,j < 2n, i \not = j$.
The contribution to the score according to these choices is $\min(b_{1}, b_{i}) + \min(b_{2...
We will call $DnC(l,m)$, compute the contribution from $dp[l,m]$ to $dp[m+1,r]$
using FFT and then
Tutorial of think-cell Round 1
218.
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...
219.
Codeforces Round 1028 (Div.1, Div.2) Editorial You could tell people didn't seem to like the match very much. I'm sorry I screwed up again ¯\\_(ツ)_/¯
If you're interested, I'd like to share some thoughts I have about this contest.
<spoiler summary="sad story">
This time I've been trying my best to make the problems use more varied algorithms instead of just dp problems, but sadly [problem:2115C] was much harder than expected.
But it seems like people are complaining more about the narrow time limit, centered on [problem:2116C] and [problem:2115C].
No one realized this before the contest, because none of the tester's code is get TLE except the wrong time complexity.
I actually don't see a problem with the Time Limit of [problem:2116C]. Some of you may be puzzled, but let me try to explain this:
- The intended solution is $O(\sum n \max(a) + \max(a)^2)$ and does not contain $\log \max(a)$. Computing $\gcd(x, y)$ is not $O(1)$, if you don't preprocess, then it's not unusual to actually get a TLE.
- I believe the v...
Let's call your cards you don't get from vertex $z$ as special cards.
Tutorial of Codeforces Round 1028 (Div. 1)
Tutorial of Codeforces Round 1028 (Div. 2)
220.
Editorial of Codeforces Round 967 (Div. 2) Except hints/solutions, I try to add a "general idea" section discuss about some general strategy and standard ideas used to solve the problem, hope you would like it :)
[problem:2001A]
idea & solution: [user:Misuki,2024-08-20]
<spoiler summary="Hint 1">
What's the most obvious lower bound of the answer?
</spoiler>
<spoiler summary="Hint 2">
Is the lower bound achievable?
</spoiler>
<spoiler summary="General idea">
One standard way to solve optimization problem is to make observation on lower(upper) bound of the answer and prove such bound is achievable, it's useful in lot of problems.
</spoiler>
<spoiler summary="Solution">
Let $x$ be one of the most frequent elements in $a$, then the answer must be at least $(n - \text{frequency of } x)$, and this lower bound is always achievable by keep erasing a non-$x$ element from $a$, and we can prove it's always possible to do so.
proof:
If all elements of $a$ are $x$, we are done. Otherwise, let $y$ denote ...
Apparently, it is the number of distinct elements in $a$. Let's call it $k$.
Tutorial of Codeforces Round 967 (Div. 2)
221.
Random notes on Lyndon decomposition I recently solved some problems that involved the concept of Lyndon decomposition. Honestly, most of them were too hard to understand for me. I'm just trying to think out loud about things I've read, so I can learn ideas or better takes from smarter people?
Note that I will omit almost all proofs as I can't do that. I believe all unproven claims below are facts, but it is always great to have doubts about anything.
## 1. Lyndon decomposition, definition, and algorithms
Partly copy-pasted from [this link.](https://cp-algorithms.com/string/lyndon_factorization.html#lyndon-factorization_1)
A string is called simple (or a Lyndon word), if it is strictly smaller than any of its own nontrivial suffixes. Examples of simple strings are $a, b, ab, aab, abb, abcd, abac$.
It can be shown that a string is simple, if and only if it is strictly smaller than all its nontrivial cyclic shifts. As a corollary, it can be observed that simple words are never periodic (it is not a repetition o...
222.
C++ quirks: variable shadowing C++ is a very permissive language. It'll let you write basically anything on the assumption that you know what you're doing... or let you shoot yourself in the foot if you don't. For example:
```cpp
class C {
int a;
public:
C(int a) : a{a} {}
};
```
It's a fairly common pattern in simple class design that's perfectly fine until it's not. The class member and constructor argument (c.arg.) have the same name. This is known as shadowing and compilers will warn you about it, though you need to use a flag `-Wshadow` that isn't included among `-Wall` or `-Wextra`. Another example of shadowing is
```cpp
for(int i = 0; i < t; i++)
for(int i = 0; i < n; i++)
```
which is fine if the first `i` isn't used for anything except making a loop (such as over test cases) but otherwise it's a solid source of bugs, especially if you "fix" it into `for(int j = 0; j < n; i++)`.
### How does shadowing work?
First off, when can one variable shadow another? The standa...
223.
Way of problemsetter *The mystery of creating rounds unveiled by author of the 4 of them!
The guide for preparing the round without horror-fiction and pastorals!*
Thanks for [user:RodionGork,2014-06-13], who push me to writing this post and thanks for [user:lucAbalo,2014-06-13], who push [user:RodionGork,2014-06-13] to pushing me to writing this post.
Also, many thanks to [user:RodionGork,2014-06-13] for the translation of this post to English.
##1. Inventing problems
It's hard to advise anything on this point. There's no some standard way of creating problems — and if one have existed we'll have only "complicated algorithmic exercises" instead of "problems". People who participated in Russian Code Cup do know well the tasks of that sort.
To cook good and interesting problem there should be some **idea!** which came to your mind (and later to minds of participants of the contest). Even the simplest problems of `A` level for the `Div2` should have some **idea**.
So here is the war...
process is managed by special programs — we call them **checkers** — which run
the solution on
224.
[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...
225.
Moment-generating functions, inversions and q-analogs Hi everyone!
Today I want to write about the inversions in permutations. The blog is mostly inspired by the problem С from [Day 3](http://karelia.snarknews.info/index.cgi?data=macros/day&menu=index&head=index&sbname=2022w&class=2022w&round=03) of 2022 winter Petrozavodsk programming camp. I will also try to shed some light on the relation between inversions and $q$-analogs.
#### Key results
Let $F(x)=a_0+a_1x+a_2x^2+\dots$, then $F(e^x)$ is the exponential generating function of
$$b_i = \sum\limits_{k=0}^\infty a_k k^i.$$
In other words, it is a [moment-generating function](https://en.wikipedia.org/wiki/Moment-generating_function) of the parameter by which $F(x)$ enumerates objects of class $F$.
**Motivational example**:
The generating function of permutations of size $n$, enumerated by the number of inversions is
$$F_n(x) = \prod\limits_{k=1}^n \frac{1-x^k}{1-x}.$$
The moment-generating function for the number of inversions in a permutation of size $n$ is
...
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Nov/11/2026 05:57:06 (k1).
Desktop version, switch to mobile version.
Supported by
