→ Pay attention
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | maspy | 150 |
| 3 | Um_nik | 145 |
| 4 | Errichto | 139 |
| 5 | adamant | 136 |
| 6 | maroonrk | 134 |
| 7 | DNR | 133 |
| 8 | nik_exists | 132 |
| 9 | AmShZ | 130 |
| 10 | Dominater069 | 129 |
→ Find user
→ Recent actions
You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:
305— search for 305, most probably it will find blogs about the Round 305andrew stankevich contests— search for words "andrew", "stankevich" and "contests" at the same timeuser:mikemirzayanov title:testlib— search containing "testlib" in title by MikeMirzayanov"vk cup"— use quotes to find phrase as istitle:educational— search in title
Results
1.
number
Last visit:
12 years ago
Registered:
13 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 ...
the number of edges whose both endpoints are deleted. In particular, there
must be at least two, If $y=0$, then the parity of the edges at the end is determined only by the
number of edges whose, Now we fix the number of white columns as $i$, and try to find a $j$ that
maximizes $|I|$. If we
Tutorial of Codeforces Round 810 (Div. 1)
Tutorial of Codeforces Round 810 (Div. 2)
4.
New Year's Eve Update: Random Problems for Mashups Hello, Codeforces!
Only a couple of days remain until 2025. To wrap up the year, I'm bringing an update — I hope you'll find it useful.
Now, you can automatically find and add random problems for your mashup based on a range of criteria and restrictions.
The problems are sourced from the archive, and unusual problems are automatically excluded.
So, click the "Add random problems" link under the problem list and proceed to the addition form.
<center>
<img style="zoom:75%;" src="/predownloaded/b9/25/b925e4d00215ff2e408cc81c2629936df72dce38.png"/>
</center>
Here's what you can do:
* Exclude problems that registered mashup participants have solved/attempted/authored (a problem will be excluded if at least one registered participant is familiar with it),
* If the mashup belongs to a group (e.g., your training group), exclude all problems from other contests in that group,
* Exclude problems with subtasks — such problems are often interconnected or referenc...
special format. The "Problem Requirements" field describes the number and
properties of the problems, , ratings:3000-, or ratings:-1000: leaving the number on the left or, The "Problem Requirements" field describes the number and properties of the
problems you want to
5.
Rounding 2025 Hi Codeforces!
2025 comes to an end. However square the year was, we held a number of rounds: 29 Div. 1 and 31 Div. 2-only contests, to be precise! Additionally, 18 Div. 3, 4 Div. 4, and 13 Educational rounds made the schedule even more congested.
<img src="/predownloaded/c8/54/c854d6a423b830263449cca6ff841c8e4e02e024.png" style="width:1400px; float:center; margin: 1em 1em 1em 1em"/>
December is not only the <strike>perfect</strike> [only](/blog/entry/149140?#comment-1332941) time to wrap the year, but also to celebrate and thank all the people who made this year possible. That's why I want to highlight with this post the people whose efforts shaped Codeforces contests.
I'd like to say a huge thank you to every active community member who created and/or prepared problems for Codeforces rounds! Without your ideas and creativity, it would be impossible to hold so fun and interesting competitions. There are so many of you from every corner of the world, so that it's impossible...
2025 comes to an end. However square the year was, we held a number of rounds:
29 Div. 1 and 31 Div, Hi Codeforces! 2025 comes to an end. However square the year was, we held a
number of rounds: 29
6.
Goodbye 2020. Hello 2021! <img src="/predownloaded/f4/1f/f41ff0beb745fb2f84a55d9f2cc451273efc6267.jpg" style="width:300px; float:right; margin: 0 1em 1em 1em"/>
Hello Codeforces!
This unusual and difficult 2020 has come to an end! What will the new year be like?
I wish all of us that we have the opportunity to meet in person so that the contests take place not only online.
I ask you to think of something important and good. Let this wish come true!
We have had a large number of rounds this year. I hope we have pleased you with interesting problems.
Thanks to the round coordinators and writers! You make our community richer. Please make us happy in 2021!
I wish the participants victories over yourself (and over problems!) and development of your skills, interest and curiosity!
Hello, 2021!
And we have traditional gifts!
#### <img src="https://assets.codeforces.com/images/wand.png"/> Change Handle Feature
Hurry! Only until the 10th of January, you can change your handle (<b>but only onc...
and good. Let this wish come true! We have had a large number of rounds this
year. I hope we, We have had a large number of rounds this year. I hope we have pleased you with
interesting
7.
Blogewoosh #1 Hello, codeforces!
The community wants so the community gets it! :D Here it is, my very first blog about tasks and algorithms. At the beginning I've decided to post my entries on codeforces, maybe I'll switch to something different if it becomes uncomfortable.
To pour the first blood I decided to choose a task from one of the old ONTAK camps. Task's name is "different words" ([you can submit here](https://szkopul.edu.pl/problemset/problem/wTy-sxQCIKry0Ml-6RvM0L78/site/?key=statement)). The statement goes as follows:
You are given $n$ words ($2 \leq n \leq 50\,000$), every of length exactly $5$ characters. Each character can be a lowercase letter, an uppercase letter, a digit, a comma... basically, it can be any character with ASCII code between $48$ and $122$ (let's say that $k$ is the number of possible characters). A task is to find all pairs of indexes of words which are $\textbf{really different}$. Two words are $\textbf{really different}$ if they differ at all $5$ corres...
character with ASCII code between $48$ and $122$ (let's say that $k$ is the
number of possible, $ is the number of possible characters). A task is to find all pairs of indexes
of words which are, What's the number of needed runs? Looking at limits we can guess that it could
be a few hundred
8.
Goodbye A2 Online Judge :( I'm sadly announcing that [a2oj.com](https://a2oj.com/) ([A2 Online Judge](https://www.facebook.com/A2OnlineJudge/)) will be retiring by end of 2019, I'll shut it down at midnight on New Year's Eve. It was something I took care of for about 10 years.
I'm really sorry, but I prefer not to explain my reasons, so please don't ask me why I'm doing this, it was hard enough for me to make this decision, and also please don't try to convince me to change my mind.
I'd like to say thank you to everyone who used it, and please accept my sincere apologies for shutting it down.
If you have something good to say about A2OJ (how you used it or how it helped you in any way), I'd love to read that, please send it to the following email (or in a comment here): [email protected]
Also please feel free to take a copy of any data you can access, and if you need some data in a specific format, please send your request to the following email: [email protected] (if the data isn't public, make sure to send f...
- 24,012,628 total number of database rows. - 99,242 registered users. - 33,133
created contests, : Database numbers: - 24,012,628 total number of database rows. - 99,242
registered users
9.
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]...
-changes.png?v=3" style="max-width: 600px; width: 600px;"/>
Total number of rating changes (in, -registrations.png?v=3" style="max-width: 600px; width: 600px;"/>
Total number of contest, -submissions.png?v=3" style="max-width: 600px; width: 600px;"/>
Total number of submissions
10.
Good Bye 2025 <div style="overflow:hidden;">
<img src="/predownloaded/a2/4f/a24f8db165991fb983fc766d223782cbf2785f7f.png"
style="float:right; width:200px; height:auto; margin-left:50px; margin-right:50px; border-radius:0px;" />
<h2>Merry Christmas, Codeforces! 🎄 🎄 🎄</h2>
<p>
We are glad to invite you to take part in [contest:2178], which will start on [contest_time:2178]. You will be
given <b>9 problems</b> and <b>3 hours</b> to solve them. <b>At least one problem will be interactive</b>, so please make sure to read the <a href="https://codeforces.me/blog/entry/45307">guide for interactive problems</a> before the contest. This round is open and rated for everyone.
</p>
<p>
Problems are authored by [user:conqueror_of_tourist,2025-12-25], [user:twosquares,2025-12-25], and [user:YuukiS,2025-12-25].
</p>
<p>
We would like to thank:
</p>
</div>
<div style="clear:both;"></div>
- [user:Error_Yuan,2025-12-...
nonnegative number of problems on the round. We hope you have a Happy New Year
(both on CF and irl... maybe go, We sincerely hope you enjoyed a nonnegative number of problems on the round. We
hope you have a
Announcement of Good Bye 2025
11.
Good Bye 2019 Hello again, Codeforces!
We are glad to invite you to <s>Mathforces</s> <s>Thinkforces</s> [Good Bye 2019](https://codeforces.me/contests/1270), which will take place on [contest_time:1270].
Some information about the round:
<ul>
<li>Rated for all participants!</li>
<li>3 hours!</li>
<li> <strong> No subtasks! </strong> </li>
<li>There will be an <strong> interactive problem </strong> in this round. You can read the guide for interactive problems [here](https://codeforces.me/blog/entry/45307)</li>
<li> Editorial will be published right after the system testing </li>
</ul>
All problems in this round were prepared by us, [user:antontrygubO_o,2019-12-28] and [user:kefaa2,2019-12-28]. We worked on this round for a long time and tried to make all the problems very interesting. We hope that you will enjoy the round!
We would like to thank:
<ul>
<li> [user:arsijo,2019-12-24] for coordination of the round </li>
<li> [user:GandalfTheGrey,2019-12-24] fo...
advices. If this a record number of testers? O_o
* [user:MikeMirzayanov,2019-12-24] for, testing and invaluable advices. If this a record number of testers? O_o
* [user:MikeMirzayanov, The number of the problems and point distribution will be announced shortly
before the round (or
Announcement of Good Bye 2019
12.
AtCoder Library Recently, the number of algorithms and data structures we use in competitive programming are rapidly growing.
It's a nice thing: by using more algorithms, the variety of possible problems gets wider, and we can enjoy more problems.
On the other hand, before reaching adhoc, thinking-oriented part of this competition, we have to spend more and more time to learn algorithms.
Sometimes a problem asks matching on general graphs; you have to find a paper describing it, read it, and implement its really complicated algorithm. Or sometimes you have to spend time tuning your library by a constant factor. Or sometimes you use multiple pre-written codes together, the variable names collide, and get annoyed.
Until now, I basically rejected all problems that require pre-written codes of complicated algorithms because I don't like these things. For example, we never used segment trees with lazy propagation in our contests.
However this way we can't use otherwise interesting problems and it ...
Recently, the number of algorithms and data structures we use in competitive
programming are
13.
[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...
comparing coefficients we get $f(n) = f_{n+1}$, the $(n+1)$-th Fibonacci number
!, easier to count. For a fixed subset of white cells $S$, denote $N(S)$ as the
number of ways to place $n, generating function for one "component" in the item we need to count. Let
$d_{n}$ denote thenumber, (x))$ because we need to sum over all values of $k$ (number of cycles), which
can also be computed, **Definition.** Let $r$ be any complex number and $n$ be a nonnegative integer.
Then, $\binom{r}{n, **Example.** Let $b_{n}$ denote the $n$-th Bell number, which counts the number
of ways to, **Problem**. Prove that the number of partitions of $n$ into parts of size not
divisible by $k+1, **Problem.** Count the number of permutations of length $n$ such that all cycle
lengths are in a, **Problem.** Count the number of permutations of length $n$ with $k$ cycles., **Problem.** Find the expected number of cycles of a permutation of length $n$., **Problem.** Find the number of bipartite vertex-labeled graphs with $n$
vertices., **Problem.** Find the number of vertex-labeled undirected graphs with $n$
vertices so that each, **Problem.** Find the number of ways to partition the set $\\{1,2,...,n\\}$
into $k$ subsets., **Theorem.** Let $r$ be a real number and $n$ be a nonnegative integer, then, . Observe that choosing a partition is the same as choosing the number of times
we use each integer in, . Suppose we magically know the sequence $r_{k}$, the number of ways to place
$k$ non-attacking rooks, Clearly, $f_{n}$ is the $n$-th Fibonacci number. We will use the recurrence
relation to find the, Finally, let $d_{n}$ be the number of bipartite graphs on $n$ vertices and
$D(x)$ be its EGF. Then, Instead, let us color each vertex of the graph with red or blue, and count the
number of **colored, It is tempting to try a similar approach as the previous problem. We can relate
thenumber of, Let $c(a)$ denote the number of permutations of length $n = a_{1}+2a_{2}+...$
with cycle type $a, Let $c_{n} = (n-1)!$ be the number of permutations of length $n$ which is a
cycle. Let $C(x, Let $f_{n}$ denote the $n$-th Fibonacci number (with $f_{0}=0$, $f_{1}=1$,
$f_{n}=f_{n-1}+f_{n-2, Returning to our original problem, our next step is to count the number of
connected bipartite, The next step is to relate the number of colored bipartite graphs with the
number of colored, Thus, $[x^{n}]G(x) = 1+\frac{1}{2}+...+\frac{1}{n}$. Since $\frac{g_n}{n!}$ is
the expectednumber, To compute the expected number of cycles, we count the sum of number of cycles
over all, You might have heard of the well-known problem of proving that the number of
partitions of $n$ into, number. We will use the recurrence relation to find the OGF of $f_{n}$.
Firstly, we need to
14.
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...
, Ningxia, Xuzhou) onsite competition without going through the autumn online
qualifiers. Thenumber of, number of places is the number of teams participating in Ningxia, and the
competition in Ningxia
15.
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...
, due to a number of circumstances, are not reproduced at local launch, but are
reproduced at launch on, , the program contains mistakes that, due to a number of circumstances, are not
reproduced at local
16.
Good Bye 2015 Hi everybody.
The last round of the 2015 will take place on the 30-th of December ([starting time](http://www.timeanddate.com/worldclock/fixedtime.html?day=30&month=12&year=2015&hour=18&min=5&sec=0&p1=166)).
The contest will last 3 hours.
It won't be a usual round.
Both divisions will compete together.
You will get 8 problems to solve in 3 hours.
Points will decrease slower than usually — otherwise you would get eps for solving a problem at the end.
Scoring will be announced just before a contest.
So will the speed of the points/minute loss.
My goal was to provide you a diverse problemset with interesting problems for all contestants.
During a contest you should consider reading not only the next problem but the few next ones.
You will get this round thanks to work of many people.
I am a problem setter.
[user:GlebsHP,2015-12-28] helps me with everything (a lot).
[user:AlexFetisov,2015-12-29], [user:johnasselta,2015-12-29] and [user:Zlobober,2015-12-29] are t...
problem at the end would give you the same number of points as in standard
2-hours rounds. Points, I'm amazed by the number of high-rated participants today. Fight was really
tough and winners, number of points as in standard 2-hours rounds. Points for problems are
500-750-1250-1750-2500
Announcement of Good Bye 2015
17.
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...
Implementation](https://codeforces.me/blog/entry/67149) - [[Insight] Number
of Topological Orderings of a, . Thank you. # Mathematics Stuff - [Number Theory in Competitive Programming
[Tutorial, ://codeforces.com/blog/entry/91137) - [Counting the number of bitmasks in a
given array that are submasks
18.
Codeforces Round #651 (Div. 2) Hi everyone!
I would like to invite you to another one of our rounds, that I set with my friends [user:FastestFinger,2020-06-05], [user:smartnj,2020-06-19], [user:the_hyp0cr1t3,2020-06-19] and [user:ridbit10,2020-06-05].
The round [contest:1370] will take place on [contest_time:1370]. If your rating is less than **2100**, this round will be rated for you; otherwise, you can participate out of competition.
I would really like to thank my co-setters and:
- [user:isaf27,2020-06-05] for coordinating our round.
- [user:cerberus97,2020-06-19], [user:Devil,2020-06-19], [user:Taran_1407,2020-06-19], [user:Alireza_Keshavarz,2020-06-19], [user:Vivek1998299,2020-06-19], [user:KonaeAkira,2020-06-19], [user:demoralizer,2020-06-19], [user:Dragnoid99,2020-06-19], [user:agtxdy,2020-06-19], [user:Rajdeep,2020-06-19], [user:aryanc403,2020-06-19], [user:lavish315,2020-06-19], [user:DeadlyCritic,2020-06-19], [user:Utkarsh.25dec,2020-06-19], [user:AmShZ,2020-06-19], [user:_Aaryan_,2020-06-19]...
make the difficulty gradient a bit better - Reduced the number of AdHoc
problems and made the, - Tried to make A easier and make the difficulty gradient a bit better -
Reduced thenumber of
Announcement of Codeforces Round 651 (Div. 2)
19.
Pro Tips - get them while they are free More tips to use while studying under my tutoring [here](https://um-nik.notion.site/Pro-Tips-8b923b0dc7c94770824bdf4184afc43c).
## 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...
bunch of rating points knowing that I solved everything I could. Because
rating is just anumber, that I solved everything I could. Because rating is just a number. It is
highly volatile and it, And besides, rating is just a number. Your sole goal during the contest should
be to solve as much, Rating is just a number. Do not be afraid to lose your colour. You’ll get it
back in no time if you
20.
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...
/blog/entry/133113), and the low number of complaints (which I do read and use
to adjust settings
21.
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...
one edge) and end at some node. He is wondering the number of ways if he's
going on several travels, . He is wondering the number of ways if he's going on several travels, making
$x$ steps at total, and
22.
Codeforces: summing up 2016 year <center>
<img src="http://assets.codeforces.com/images/Happy-New-Year-HD-Wallpapers.jpg"/>
</center>
Somehow it turns out that for me, each coming the New Year means more and more. This is an excellent opportunity to take stock, to breathe fresh air and to go through a kind of catharsis. This is a rare opportunity to be with the family, dress up in Santa Claus and just have fun.
Holidays give me a clear criterion that I do the right things. If during the holidays, I begin to think about it, to recall some deferred ideas, eager to implement something new. So I’m doing right things. My things. And now exactly the same as in several recent years: during New Year holidays I write code for Codeforces, trying new technology or simply I’m making minor changes in testlib. It is necessary to me: at this moment are no deadlines, do not press the obligation. Just now, at 3 am, I can not break away from being able to do something new. I would like to take a moment and realize that spun in ...
my head the whole year. I'm insanely happy to huge number (9144!) of
registrations on Good Bye, short, we have a fun live. The system load become higher, large number of
improvements have been made, , having at least +100 votes. The total number of posts is not interesting,
because a lot of trash/spam, I'm insanely happy to huge number (9144!) of registrations on Good Bye 2016.
Your desire to grow
23.
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...
Don't use rand(): a guide to random number generators in C++, that the code seeds the random number generator using a high-precision clock.
This is important for, ### What's the solution? Don't worry, as of C++11 there are **much better**
randomnumber, ., `rand() % 10000` is more likely to give you a number between 0 and 999 than a
number between 9000 and, ? Don't worry, as of C++11 there are **much better** random number generators
available in C++. The, If you want even faster, higher-quality random number generators, take a look
at [this site by
24.
Blogewoosh #6 Hello, codeforces!
Sorry for the long break, but the last weeks of holidays and the first weeks of academic year took my attention. I hope today's trick will make you forgive me. :P
I invented this trick a few years ago, but for sure I wasn't first, and some of you already know it. Let's consider the following **interactive** task. There are $n$ ($1 \leq n \leq 10^5$) hidden integers $a_i$, each of them from range $[1, 10^{18}]$. You are allowed to ask at most $103000$ queries. In one query you can choose two integers $x$ and $y$ ($1 \leq x \leq n, 1 \leq y \leq 10^{18}$) and ask a question ''Is $a_x \geq y$?'' The task is to find the value of the greatest element in the hidden array. The checker **isn't** adaptive.
Unfortunately, this task is only theoretical, and you cannot solve it anywhere, but it'll turn out, that solution can be handy in many other, much more complicated problems.
[cut]
$ $
Even beginners should be able to quickly come up with a solution which ask...
$O(log(n))$ times! A total number of queries will be equal to $n+O(log(n)
\cdot log(d))$, which, decrease the number of binary searches that we would do, but how much? Let's
consider the following, they wouldn't work on a first random max-test. The limit on the number of
queries slightly higher, A filled circle means that we do the binary search, an empty circle means that
we skip thisnumber., The limit on the number of queries slightly higher than the limit on $n$ should
give us a hint: for
25.
Self-deception: maybe why you're still grey after practicing every day I generally don't like to give much advice on "how to practice", but recently I have been thinking a lot about this and I realized that there is something that I believe affects a lot of people (though it is admittedly hard to tell) that barely gets talked about: self-deception.
Self-deception is a devious thing. It can be very hard to detect, yet can be fatal to improvement.
This blog is mainly directed to greys, greens and cyans that can't get out of these categories. Most examples are given with that in mind. That being said, I believe others have something to think about as well.
This is my first blog on such "psychological issues" and I don't know if I'll ever make another one. It's certainly a difficult topic to write about because for most of the blog, the message is "your practice is not as good as you think it is" or even "you aren't as good as you think you are" which can of course be a hard thing to hear. Thus, I have to somehow be very gentle while getting the poin...
on the appearance of the website): you can only see a small number of problems
at a time. You HAVE to, people that do CP for this reason). A relatively small number of people even
get a stipend or, number of people even get a stipend or similar for CP. That kind of motivation
can serve as a kind of
26.
A problem collection of ODE and differential technique ##A problem collection of ODE and differential technique
*This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them.*
For those who are interested in well-known problems in China.
Thank [user:Elegia,2020-04-23] and [user:djq_cpp,2020-04-23] for developing this technique. Thank [user:tEMMIE.w.,2020-04-23] for reviewing this article.
####[Chain Reaction](http://uoj.ac/problem/50) in UOJ Round 3 By [user:vfleaking,2020-04-23]
**Statement**
You are given a set $A$, you need to compute $g_{i} = \frac{1}{2} \sum_{j,k}{i-1 \choose j}{i-1-j \choose k} g_jg_k$ where $i-1-j-k \in A$.
**Solution**
Let the EGF of $g$ be $x(t)$ and EGF of $A$ be $a(t)$. Thus $x'(t)=\frac{1}{2} a(t) x^2(t)+1$. We can solve this equation by D&C and FFT in $O(n\log^2 n)$. But there is a <s>slower</s> solution in $O(n\log n)$.
For a polynomial equation $f(x(t))=0$, we can use the Newton's method to solve it. If we find ...
Find the number of binary matrixes with $n$ rows and $m$ columns that there
are at most $2$ ones, You are given a number theory function $g$ and $k$, you need to find a
function $f$ such that $g, good application is to compute the number of [simple
permutations](http://oeis.org/A111111) (a.k.a, into univariate EGFs directly. For odd chains, we know the number of chains
starting in the left part, replace $\ln n$ with $\Omega(n)$, which is the number of prime factors of $n$
counted with, the expected value of the number of variables that are equal to $a$., ) in EC Final By [user:MiFaFaOvO,2020-04-23] **Statement** You are given a
number theory
27.
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">
![ ](https://s3.us-west-2.amazonaws.com/secure.notion-static.com/677e0ae2-a8df-4874-aff...
="color:purple">problem solving ability is also a number on the same scale. But
it doesn’t
28.
Codeforces: Results of 2017 <img src="/predownloaded/e4/09/e40915ee54c5991b91098756a90270d94be893b3.jpg"/>
Happy New Year, Codeforces!
I hasten to wish the whole community (and including me) correct programs, sudden insights, beautiful ideas and interesting problems!
I hope that you have met the new year at least as fun as I am. Have you had enough sleep after New Year's Eve? This year, the traditional post summarizing the past year, I sat down to write only on January 1, 2018. I hope that I will not have to sum up the whole year.
This post is important to me, since it draws a line to all the work done by the Codeforces team and the entire community in 2017. Many thanks to the team: all of the achievements listed below are the result of joint efforts. We did an excellent job! The community must know its heroes. In 2017, [user:MikeMirzayanov,2018-01-02], [user:KAN,2018-01-02] (problem coordinator), ~gritukan,2018-01-02 (second problem coordinator), ~netman,2018-01-02 (ex-second problem coordinator), ~k...
* number of hosted rounds, * number of new problems, * number of new trainings
in Codeforces::Gym., , having at least +100 votes. The total number of posts is not interesting,
because a lot of trash/spam, -months.png?v=1"/>
The growth in the number of registered users. More than 600 thousand, > The growth in the number of registered users. More than 600 thousand
registrations!
29.
Testing Round #16 (Unrated) Hello, Codeforces!
Paul [user:stingray,2020-05-07] Komkoff is my hero! He found some issues in the network configuration. The most important of them was about flow control auto-negotiation: in case of our network routers the number of dropped packets reduced in times. Thanks!
To be sure that it really helped to fix the issue I ask you to take part in [contest:1351]. It will start on [contest_time:1351]. Probably, it will contain 3 easy problems which are not prepared for now (I'll use some old problems, I think). The only reason to host the round is to check the system under a load. It will be an unrated round.
I am upset about what happened with the last round. Once again, I apologize to both the participants and the writer, coordinator and testers. I wrote [user:Monogon,2020-05-07] about the incident and apologized.
I am sure that the only way to **absolutely** prevent unrated rounds is just don't host them. And this is not my way. The most popular rounds were hosted with...
case of our network routers the number of dropped packets reduced in times.
Thanks! To be sure that, routers the number of dropped packets reduced in times. Thanks!
Announcement of Testing Round 16 (Unrated)
30.
Codeforces Round #668 Hello Codeforces!
We are glad to invite you to [contest:1404] and [contest:1405], which will take place on [contest_time:1404].
The problems were created by [user:Ari,2020-09-04], [user:Kuroni,2020-09-04], [user:Maripium,2020-09-04], [user:Monogon,2020-09-04], [user:antontrygubO_o,2020-09-04] and [user:hugopm,2020-09-04].
We would like to thank:
- [user:dorijanlendvaj,2020-09-04], [user:Jatana,2020-09-04] and [user:MrDecomposition,2020-09-04] for helping with the preparation of the tasks.
- [user:gamegame,2020-09-04] for always being nice and supportive.
- [user:DatVu,2020-09-04], [user:Maripium,2020-09-04], [user:MofK,2020-09-04] and [user:atoiz,2020-09-04] for stealing the round #666, forcing us to retheme around ponies.
- [user:Monogon,2020-09-04] for making the author list more colorful.
- [user:TwentyFour,2020-09-04], [user:thenymphsofdelphi,2020-09-04], [user:qlf9,2020-09-04], [user:mcfr,2020-09-04], [user:Tlatoani,2020-09-04], [user:i_love_Lisa,2020-09-04...
**UPD:** The number of problems is now 5 in each division.
Announcement of Codeforces Round 668 (Div. 1)
Announcement of Codeforces Round 668 (Div. 2)
31.
Codeforces Round #300 (with prizes!) Hello, Codeforces!
[On Sunday, April 26th at 19:00 MSK](http://www.timeanddate.com/worldclock/fixedtime.html?day=26&month=4&year=2015&hour=19&min=0&sec=0&p1=166) the 300'th regular Codeforces Round will take place.
I would like to congratulate all Codeforces members and administration on this remarkable milestone. The platform has grown hugely in size and quality since its foundation, has hosted lots of exciting competitions, and has been providing the opportunity to everyone to hone their problem solving and algorithmic mastery. For this we thank the Codeforces platform creator [user:MikeMirzayanov,2015-04-24] and all the Codeforces crew. Keep up the incredible job, guys!
That being said, I'm excited to announce that the problems on the jubilee three-hundredth Codeforces Round will be set by me, Mikhail Tikhomirov ([user:Endagorion,2015-04-24]). You may remember the past rounds with my problems: [#99](http://codeforces.me/contests/138,139), [#109](http://codeforces.me/contest...
random generator, this integer should be equal to the last submission number
that happened during the
Announcement of Codeforces Round 300
32.
Competitive Programming Hall of Fame — cphof.org Hi Codeforces!
Today I'd like to introduce the new [Competitive Programming Hall of Fame](https://cphof.org) project that is available at [cphof.org](https://cphof.org)
#### Background
A long time ago I've noticed that there is no single source of information with the results of previously held large programming competitions. Moreover, plenty of older championships don't maintain their websites anymore, and it becomes hard or even impossible to find any details about them, which is pretty sad. So I've decided to create [Competitive Programming Hall of Fame](https://cphof.org).
#### About the project
Competitive Programming Hall Of Fame is a project created to preserve the history of international championships in competitive programming. This website collects the results of the final stages for both worldwide and regional contests. By international championship we mean a contest consisting ...
ICPC World Finals 2005 and earlier; - Standings (with the number of problems
solved and penalty, different limits on the number of local and international finalists, like
Bayan Programming Contest, finals). Contests that have different limits on the number of local and
international finalists, like
33.
Codeforces: Results of 2020 [list some changes and improvements] Hello, Codeforces!
I understand that 2021 has been going on for a long time, but here I have picked up a subset of some of the improvements that the Codeforces team made in 2020. Soon I will publish numbers (no, charts) with statistics for 2020. In the meantime, I bring to your attention a list of changes and improvements.
By the way, this is a decent list. This is about half to a quarter of all changes. It's just that other changes are more often somewhere in the internals of the system and are not visible to users. Please read this list. Each item is the effort of someone from the team. Thanks to [user:geranazavr555,2021-03-14], [user:kuviman,2021-03-14] and [user:cannor147,2021-03-14] for their efforts. You've made our platform better! Well, by the way, I don't quit programming and many improvements were made by me.
The items on the list are written in a concise and informal form, many of the items I just copied from commit messages from git. If you want more details &mdash...
34.
Codeforces: Results of 2019 <a style="float:right; display: inline-block; margin:0 1em 1em 2em; max-width: 60%;" href="https://codeforces.me/10years"/>
<img style="max-width:100%" src="https://assets.codeforces.com/images/codeforces-10-years-300.png"/>
</a>
Hi Codeforces!
The platform recently turned 10 years old. We accept your congratulations at <a href="https://codeforces.me/10years">https://codeforces.me/10years</a>.
Please review the progress in 2019 and support the anniversary crowdfunding campaign. Your donation will be a contribution to the future of Codeforces, will
help its development and work. We need resources to continue to host rounds, not to stop developing,
to innovate and to maintain the existing infrastructure.
In 2019, together with numerous writers the coordinators worked on problems: [user:KAN,2020-02-06], [user:300iq,2020-02-06], [user:cdkrot,2020-02-06], [user:arsijo,2020-02-06] and recently joined [user:isaf27,2020-02-06]. And this year,
rounds coordinated by other exper...
least +100 votes. The total number of posts is not interesting, because a lot
of trash/spam, which, "/>
The number of page views, +31% in 2019!, "/>
The number of visitors, +15% in 2019!, "/>
The number of visits (browser sessions), +32% in 2019!, , having at least +100 votes. The total number of posts is not interesting,
because a lot of trash/spam, They were not included in the pictures, but there is a noticeable increase in
thenumber of hosted
35.
Hello, ITMO! <img src="https://assets.codeforces.com/images/itmo-logo.png" style="margin:1em 1em 1em 1em; float:right;"/>
Hi Codeforces!
For you, perhaps it was yet another Codeforces round. But not for me. [contest:1066] is the first round tested on new judging servers at ITMO University. And this is not just an update of location. Ta-dam! Now your solutions will be judged on the new Intel i3-8100 processors. And this is not all news. The number of judging servers has increased, which means fewer queues during rounds!
I am pleased to announce that now I live in St. Petersburg, I work at ITMO, and Codeforces is gradually moving from the walls of dear to me Saratov University to ITMO University. The decision to move was not easy for me. My plan is that, based on ITMO, I can focus more on Codeforces development and work on the platform. The number of world champions per square meter is simply overwhelming, and working with a large team of such enthusiasts (and professionals!) of sports pro...
news. The number of judging servers has increased, which means fewer queues
during rounds!, processors. And this is not all news. The number of judging servers has
increased, which means fewer, work on the platform. The number of world champions per square meter is simply
overwhelming, and
36.
About Gift Distribution Hello everyone!
<img alt="Packages" src="https://codeforces.me/predownloaded/a7/ce/a7ce52909464af02e2f922990c8c7e4418b98f67.jpg" style="float:right; height: 500px; margin: 10px; max-width:50%;"/>
“My name is Una and I am from the Codeforces team” — this is usually how my messages to users of the site begin. One of the reasons why I write a message is very joyful — sending out gifts to the winners of the competitions and now also to participants of crowdfunding dedicated to the 10th anniversary of Codeforces.
That’s what I’d like to talk about a little bit.
Everyone knows where it all starts — there is a round with gifts, in the comments to which after the ending the coordinators or Mike post a list of winners.
Then, in a short time, all winners receive a system message asking them to update the data about the size of the T-shirt and address. In some special cases, such as crowdfunding, for example, all participants receive an email. For various reasons...
everyone receives a system message with a tracking number of the packages.
37.
Worst-Case Graphs for Maximum Flow Algorithms Maximum flow algorithms are known to perform significantly better in practice than their worst-case time complexities would suggest. So in this blog, I will present graphs on which the following maximum flow algorithms actually achieve their worst-case running time:
| Algorithm | Time Complexity |
| ----------------------- | ------------------------------ |
| Ford-Fulkerson with DFS | $\mathcal{O}\big(m^2 \cdot U)$ |
| Edmonds-Karp | $\mathcal{O}\big(n \cdot m^2\big)$ |
| Dinic | $\mathcal{O}\big(n^2 \cdot m\big)$ |
| DFS with Scaling | $\mathcal{O}\big(m^2 \cdot \log(U)\big)$ |
| Dinic with Scaling | $\mathcal{O}\big(n \cdot m \cdot \log(U)\big)$ |
| Most Improving Augmenting Paths | $\mathcal{O}\big(m \cdot \log(U) \cdot (m + n \cdot \log(n))\big)$ |
| FIFO Preflow Push | $\mathcal{O}\big(n^3\big)$ |
| Highest-Label Preflow Push | $\mathcal{O}\big(n^2 \cdot \sqrt{m}\big)$ |
Here and in the rest of this blog:
- $n =$ number of vertices,
...
$i \geq 2$). Since the Fibonacci numbers grow exponentially, the number of
augmenting paths will be, the total number of pushes is $\Omega(k^2) = \Omega(n^2)$., $ times. In total the number of augmenting paths is $l\cdot k^2$. So by
choosing $k = \Theta(\sqrt{m, - $n =$ number of vertices, - $m =$ number of edges, - $U =$ maximum edge
capacity., For testing, I always set the maximum number of edges twice as high as the
maximumnumber of
38.
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...
Conjecture and better with Prime Number
<https://en.wikipedia.org/wiki/Prime_number_theorem>, a problem is familiar to somebody. It is important to understand, that huge
number of problems have, fact of the use of the Goldbach's conjecture (and more prime number theorem)
is not a reason for me to, ">Prime Number Theorem. These facts are medium-popular in the world of
programming contests, Taking into account large number of participants who didn't notice the issue,
who solved problems
39.
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...
decent number of new sources, we will consider to open the UCup Olympiad
Track. But for now, it’s, ### On the Number of Stages, Last year, we had 40 stages, which is a huge number, especially compared to the
28 from Season 2, Now, I'm more seriously considering how to adjust the number of stages.
Starting from Season 4, I, The biggest issue? We simply can not find a decent number of problem sets to
use. Unlike ICPC-style
40.
Remove Virtual Contestants from Contest Leaderboards As most of you are likely aware, cheating in virtual contests (typically by submitting prewritten or copied solutions in order to appear at the top of the leaderboard) is very common. Most recently, [user:wannabecandidatemaster,2020-05-28] submitted solutions to all problems in [this round](https://codeforces.me/contest/1358/standings) in order to take first place in the standings, and [user:bemandrei,2020-05-28] competed virtually in [this round](https://codeforces.me/contest/1360/standings) after competing in the round officially, and ended up in second place on the leaderboard.
In response to the rise of VC cheating (as well as some other issues with the VC system I'll describe below), I'd like to make a simple proposal: **Remove all virtual participants from the contest leaderboards.** The one exception is that you should see your own name on leaderboards for contests you VCed (that is, virtual contestants should be visible only to themselves). Similarly, virtual participan...
compete officially, so it has an exceptionally broad scope and affects a large
number of users., the absence of cheating, they should not appear on the leaderboards. There are
anumber of reasons, , so it has an exceptionally broad scope and affects a large number of users.
Second, and more
41.
[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...
42.
C++ Tricks I see lots of programmers write code like this one:
~~~~~
pair<int, int> p;
vector<int> v;
// ...
p = make_pair(3, 4);
v.push_back(4); v.push_back(5);
~~~~~
while you can just do this:
~~~~~
pair<int, int> p;
vector<int> v;
// ...
p = {3, 4};
v = {4, 5};
~~~~~
[cut]
[This](http://codeforces.me/blog/entry/10124) is a great C++11 tutorial for those who want to know more about C++11.
#### 1. Assign value by a pair of {} to a container
I see lots of programmers write code like this one:
~~~~~
pair<int, int> p;
// ...
p = make_pair(3, 4);
~~~~~
while you can just do this:
~~~~~
pair<int, int> p;
// ...
p = {3, 4};
~~~~~
even a more complex `pair`
~~~~~
pair<int, pair<char, long long> > p;
// ...
p = {3, {'a', 8ll}};
~~~~~
What about `vector`, `deque`, `set` and other containers?
~~~~~
vector<int> v;
v = {1, 2, 5, 2};
for (auto i: v)
cout << i << ' ';
cout << '\n';
// prints "1 2 5 2"
deque<vector<pair<in...
**e.g.** __builtin_clz(16) = 27 because 16 is ' **...** 10000'. Number of bits
in a `unsigned int, **e.g.** __builtin_ctz(16) = 4 because 16 is '...1 **0000** '. Number of
trailing 0-bits is 4., This function returns number of 1-bits of x. x is `unsigned int` and like
previous function this, This function returns number of leading 0-bits of x which starts from most
significant bit position, This function returns number of trailing 0-bits of x which starts from least
significant bit, We can have a variadic function. I want to write a sum function which gets a
number of ints, and
43.
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...
okay, but I still feel something wrong. The number of slots is decreasing, as
well as the power of, something wrong. The number of slots is decreasing, as well as the power of
those multifarious bonus are
44.
I've (also) completed Project Euler ###_I've been dreaming of writing this for so long._
---
About 2 years ago, [user:Radewoosh,2025-10-22] posted a [blog](https://codeforces.me/blog/entry/122793) celebrating that he had solved all 865 problems on Project Euler.
As a (naively optimistic) high-schooler back then, I thought to myself: _"Surely it can't be that hard, right?"_
2 years later, there are now 965 problems, and I've solved all of them!!
---
I can’t even begin to describe how happy I am, and how wonderful the journey has been. Maybe I’ll write about it in another blog sometime. For now, I’ll answer some questions you might be thinking...
####_Literally, who asked?_
No one, of course. But this achievement means a lot to me, and I hope that this post inspires someone out there.
####_How long did it take?_
Kind of a difficult question to ans...
to solve X number of tasks within Y hours. Also, some of the techniques are
more standardized.
45.
About Problemsetting (for AtCoder and Codeforces) Since the amount of information available about the preparation of a competitive programming contest for AtCoder/Codeforces is very little, I decided to collect here what was my experience.
I will try to both describe my experiences and give some general advice to wannabe problemsetters.
I hope that this will be useful to future problemsetters who are "out of the loop". Moreover, participants might be curious to know what happens behind the scenes (and maybe the platforms may consider this as a form of constructive feedback).
*Acronyms*:
- AGC = Atcoder Grand Contest
- GR = Codeforces Global Round
### Why I know something about problemsetting?
I am in the competitive programming world since ~8 years: I have participated in IOI/ICPC/GCJ and a number of contests on AtCoder/Codeforces (and lately Codechef).
I am not a top participant but, being in this world for so long, I know, more or less, all the standard tricks.
Recently, I was the author of the *flagship conte...
coordinator). In both cases, I was expecting a large number of questions but
the real amount was, feeling). In the past I was also the author of a number of tasks for the
Italian Olympiads in, received a message from [user:MikeMirzayanov,2020-12-09] asking to propose
rounds (it was sent to anumber, 1. The number of participants was much larger, which is cool. 2. I was not
stressed by the fact, For AGC44, the final check lasted an immense number of hours (I cannot check
since my slack account, For the Global Round there was a large number of testers. The issue here was
that some of the, I made a number of preparation mistakes but, in hindsight, I consider all of
them minor. After, number of contests on AtCoder/Codeforces (and lately Codechef). I am not a top
participant but
46.
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...
- ### Print a binary representation of a number, Also, if you want to print an octal or a hexadecimal representation of a number
, you can simply, Assume you want to use a function which maps 0 to 0 and every non-zero number
to 1 (for example, to, However, you need to fix the number of bits to show (which is usually not a
problem because in most, If you want to print, say, last 20 bits of a number, it's not necessary to
write smth like, Imagine you want to quickly write a lambda which calculates the number of ways
to choose $2
47.
[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...
improves the constant factor but article referenced in links under number $3$
contains this:, measure running time of some algorithms as the number of _oracle calls_.
(However, in practice we cannot, of circuit $L$ which is $(3-11-1-2-12-4)$. Increasing the number of elements
in $C$ not included in, of ground set in any form, it only cares about number of taken elements. All
subsets of size $k, the number of problems that can be reduced to intersection of multiple
matroids. In fact this stuff, to choose exactly one number from each box. Colorful matroid can do the trick:
assign the same color, $ element at the same time. Number of different colors cannot exceed $n$, we
can use count array that, **Truncated matroid.** We can limit rank of any matroid by some number $k$
without breaking matroid, Shortly, problem gives us few boxes with numbers and asks us to choose exactly
onenumber from each, So, there is no way to restrict number of ways to include circuit $C$ to $1$ by
edges of exchange
48.
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...
complex number, and estimate $|\delta|=\sqrt{\delta_x^2+\delta_y^2}$, the
complex absolute value of, is to pick a random number $k$, and then multiply $a_i$ and $b_i$ by $k^i$,
and correspondingly, it would be useful to someone, and maybe would reignite interest in complex
number based FFT at least, performed in a way as if we had infinite precision, but rounded to the nearest
representablenumber in, to infinite relative error, while the error for the complex number as a whole
will be finite. Thus, when the reduced number is initially 64-bit., , where we need to do 3 inverse transformations. With "2-in-1" approach this
will only reduce thenumber, -precision.md). There, it is suggested to multiply the first array with a random
number $x$, the second array, /types/numeric_limits/epsilon) `std::numeric_limits::epsilon()`. This number
typically, By _relative_ precision here we mean that if the exact number is $x$, the
resultingnumber would be, number into $\pm \sqrt{c}$, so we will have:, number of intrinsics; - If the instruction set is unavailable, I trust compiler
to do the next best
49.
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...
add the same fixed number to every input to the function. But if two numbers a
and b satisfy a = b, can easily generate a large number of different inputs that all collide, thus
causing an $O(n^2, mods by a prime number, and the result is used as the appropriate position in
the hash table., phase). In particular, if they know our hash function, they can easily
generate a largenumber of, produce a large number of collisions, so the first thing we should do is add
some non-determinism
50.
Blogewoosh #2 Hello, codeforces!
All signs in the sky and on the ground indicate that you've enjoyed my first blog, so here is the second one. I've decided to choose a Polish task again, as there are plenty of interesting ones. This time we'll take a look at the "plot purchase" ([you can submit here](https://szkopul.edu.pl/problemset/problem/hwbyoUkNFPXQLOPcw3x5huTR/site/?key=statement)), which is a bit easier, but a few years ago I was very proud of myself when I solved it. The statement goes as follows:
You are given a square $n \times n$ grid ($1 \leq n \leq 2000$). In every cell, there is a number from the range $[1, 2 \cdot 10^9]$. You are also given an integer $k$ ($1 \leq k \leq 10^9$). A task is to find a subrectangle of this grid such that the sum of values in this subrectangle lies in the range $[k, 2\cdot k]$ (or report that there is no such subrectangle). Just print coordinates of its opposite corners.
[cut]
$ $
If the problem would be more difficult, and we'd be asked to fi...
You are given a square $n \times n$ grid ($1 \leq n \leq 2000$). In every cell,
there is anumber, number from the range $[1, 2 \cdot 10^9]$. You are also given an integer $k$
($1 \leq k \leq 10^9$). A
51.
PinkieRabbit Cheated in Div. 1 Contest on Apr 27 I am writing to report an incident of cheating by PinkieRabbit during the recent contest 1965 on Codeforces. **PinkieRabbit asked help about problem D from others during the contest,** which is definitely against the contest rules.
I have attached the evidence of the cheating behavior in the appendix, please read it. This evidence clearly shows the communications PinkieRabbit had with another person during the contest. It is a contest recording video published after contest by himself. As a former fan of PinkieRabbit, after seeing this video, I was shocked by how dishonest PinkieRabbit was. I believe such actions undermine the integrity of the competition and the platform as a whole. [user:win114514,2024-05-05] cheated by grouping up in contest 1905, finally punished by skipping. Therefore, I respectfully request that Codeforces take appropriate action against PinkieRabbit to maintain the fairness of the contests on Codeforces.
He only cheated in one problem this round, so I sugg...
appear an odd number of times, right?, P: What? Let me see... But, which part is extra... oh, it's the number 6,
right? 6 is the extra, P:Yeah I have, but obviously number 6 have an extra one remaining, that that
that that that that, The number after ?t= is the time in the video counted by seconds., number in order to be displayed. If you are still unable to access it, I will
send you an offline
52.
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";
}
}
...
$(-1, 1)$ into the array to fix the number of occurrences of prefix sum
starting from the largest value, insert $(-1, 1)$ right after it $k$ times to increase the number of
occurrences of prefix sum with value, p_n$ and sum up the number of ways for each possible sum. , We continue using a similar idea to fix the number of occurrences of $p_n - 2,
p_n - 3, \ldots, p_1, [n] * ifact[r] % MOD * ifact[n - r] % MOD; } // count number of a_1 + a_2 + ...
+ a_n = x inline
Tutorial of Hello 2024
53.
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...
new multigraph, with every edge having multiplicity equal to the number of
times it is used in $W$., **Lemma 2**: There is an even number of odd degree vertices, Let $r(e) \geq 1$ be the number of times edge $e \in E(G)$ is used in $W$.
Define a multiset $F$:, number of cycles, such that the endpoints of the paths are precisely the odd
degree vertices.
54.
April Fools Day Contest 2026 Hello, Codefoolers!
We, [user:AlperenT,2026-03-29], [user:Ari,2026-03-29], [user:ToxicPie9,2026-03-29], [user:flamestorm,2026-03-29], [user:prvocislo,2026-03-29], [user:temporary1,2026-03-29], and [user:willy108,2026-03-29] would like to invite everyone on Codeforces to [contest:2214]! The 14th April Fools Day Contest will take place on [contest_time:2214]. This is a joke competition in which solving the problem is often easier than figuring out what the actual task is.
In this round, you will be given $n$ problems where $n$ is the number of different AI models I used today and **2** hours to solve them. The contest will use extended ICPC rules (no hacks, the standings are decided by the number of solved problems and penalty time earned on them). You can submit solutions in any language allowed by Codeforces, unless the problem says otherwise.
There will be at least one non-interactive problem. In case you do not care about those problems, [here](https://codeforces.me/blog/e...
In this round, you will be given $n$ problems where $n$ is the number of
different AI models I used
Announcement of April Fools Day Contest 2026
55.
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...
of the number of pips rolled on a 6-sided die is $3.5$:, remaining number. Well, the implementation is hard because of precision issues., year? Find EV of the number of days when at least one student has birthday.
Bonus/fact: Birthday, , expectation) is the average value of an event/experiment. For example, EV of
thenumber of pips rolled on, . (The size of CH is the number of its vertices.)., . Find EV of the number of matches won by Poland. Find EV of the number of
matches won by Poland, 1. **Aces** We choose 10 cards at random from a standard deck of 52 cards. Find
EV of thenumber, 6. **First heads** Find EV of the number of coin tosses until you get heads.
How to check your, 7. **Two heads** Find EV of the number of coin tosses until you get heads two
times in total., 8. **Two heads in a row** Find EV of the number of coin tosses until you get
heads two times in a, number, or a pair or an edge) and count how many times it will be added to the
answer.
56.
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...
original algorithm). 4. Change the $\text{Fib}_{2n}$-th number to $0$., sequence. But at that time, this Cartesian tree didn't consider `1 2` size
relationships, so thenumber, $. The middle two steps will reduce the number of distinct values., . My first step was to think about the properties of the change in the "number
of distinct values, Change the $8$-th number to $0$., The total number of range addition and global $\text{chkmax}$ operations is
$O(n^{\frac{1}{3}}+\log, We know that $\log\text{Fib}_{2n+1}=O(n)$, so the number of effective
$\text{chkmax}$ operations in, number of roots became reasonable, but the chkmax operation still caused
strange changes to the tree's
57.
Codeforces Global Round 21 Hello Codeforces!
On [contest_time:1696] we will hold [contest:1696]. **<img src="/predownloaded/2e/e2/2ee2f0f95f05aae6ca6f47812dae2dc2aabf277b.png" style="width: 200.0px;float: right;margin: 0 1.0em 1.0em 1.0em;max-width: 100.0%;max-height: 100.0%;">**
It is the third round of a 2022 series of [Codeforces Global Rounds](https://codeforces.me/blog/entry/65002). The rounds are open and rated for everybody.
The prizes for this round:
- 30 best participants get a t-shirt.
- 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.
The prizes for the 6-round series in 2022:
- In each round top-100 participants get points according to the [table](https://pastebin.com/QT5sXEaT).
- The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
- The best 20 participants over all series get sweatshirts and place certificates.
Thanks to XTX, which in 2022 supported the global ...
- duration: **2 hours and 15 minutes** - number of problems: 8 - score
distribution: **500-1000
Announcement of Codeforces Global Round 21
58.
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:...
(SDAEIOU). Thin edges on the right represent the second letter of a string and
thenumber there should, _order_), which is equal to the number of states (variables) you need in
space-efficient dp. We had $s=2, exponentiation. This dp is easy — for length from $1$ to $n$ compute the number
of strings, Let's visualize that by drawing vertices representing the two moods, and edges
with thenumber of, Now, try to find the $n$-th Fibonacci number for $n \leq 10^{18}$ ([problem
link](https, number of paths from vertex $i$ to vertex $j$. , ~~~~~ for(int i = 0; i < s; i++) { // s is the number of states, s=2 in the
String Mood problem
59.
Cheater Report in Global Round 15 In the last contest, both [user:tourist,2021-07-26] and [user:ko_osaga,2021-07-26] copied the author's solution from the problem Matrix from Petrozavodsk Winter Camp 2013 Warsaw U contest: [submission:123723552] and [submission:123727448] respectively. You can easily verify that they didn't write this code themselves by looking at the comments in these solutions (written in Polish).
This is **against the Codeforces rules**. According to [this post](https://codeforces.me/blog/entry/8790), we have the following rules:
> Solutions and test generators can only use source code completely written by you, with the following two exceptions:
>
> 1. the code was written and published/distributed before the start of the round,
> 2. the code is generated using tools that were written and published/distributed before the start of the round.
and
> Currently, the only reliable proof is the presence of code on the Internet and the presence of the used edition in the cache of well-kn...
second category (same as team reference code), as only a small number of
people have access to this
60.
Editorial of Global Round 11 #### General comments
Broadly speaking, problems A-B-C-D were "div2 problems", while F-G-H were "strong grandmaster problems" (with E staying in the middle). I did not expect anyone to solve all the problems and thus I decided to give the scoring F+G=H (so that maybe someone would have solved H).
<br><br>
Many of the problems (A, C, D, E, G) admit multiple solutions. Sometimes the core of the solution is the same (C, D) and sometimes the solutions are truly different (A, E, G).
<br><br>
If you are an experienced participant, I would like to hear your opinion on the problems. Feel free to comment on this post or send me a private message.
<br><br>
<spoiler summary="Overview of the problemset" >
The easiest problem of the contest, *A-Avoiding Zero*, is about rearranging an array of numbers. It is intended as a very easy problem that still requires to think.
Then, in *B-Chess Cheater* an intuitive (but nontrivial to prove) greedy approach is the way to go.
*C-The Hard Work of P...
* asks to produce the number $1$ (starting from a given number) using only the
addition and the xor. A
Tutorial of Codeforces Global Round 11
61.
[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...
for the number formed from the first $10$ bits (until the number is greater
than $K$). Then, we can, letter 'S' and large numbers with the letter 'L'. For each L, it increases the
number of inversions by, precomputation already takes $O(K^2)$), to obtain the number of pairs of
permutations of $\{1, 2, ..., n, seen this trick appeared some number of times., the number of filled spaces adjacent to an empty space., we add a new number we increase the values of the $?$ and update the cost
accordingly., 1. We place the current number $a_{i}$ in its own group : Then, $dp[i][j][val]
+= v$., 2. We place the current number $a_{i}$ in one of the open groups, but **not
close it** : Then, $dp, Abridged Statement : Find the number of permutations of length $N$ with exactly
$K$ inversions. ($K, Abridged Statement : Given $a_1, a_2, ..., a_n$, find the number of
permutations of these numbers, How? We will find the number of permutations using $1, 2, ..., n$ and $n + 1, n
+ 2, ..., 2n$ and, Let $dp[i][j]$ be the number of permutations of length $i$ with $j$ inversions.
Then, $dp[i][j, Let $dp[i][j][k]$ be the number of ways such that when we inserted the first
$i$ elements, there, Let $dp[i][j][k][l]$ be the number of ways to insert the first $i$ elements
such that :, Now, let $dp[i]$ be the number of ways to reach the $i$-th blocked cell
(assuming it is not blocked, Now, let $g_{0}, g_{1}, g_{2}, ..., g_{K}$ be the number of permutations of
length $n$ withnumber, Now, we have to subtract the number of paths that reach some of the blocked
cells. Assume we, The base case, $dp[1]$ can be calculated as the number of ways to reach $S_{1}$
from the starting, The number of ways from square $(x_{1}, y_{1})$ to $(x_{2}, y_{2})$ without any
blocked cells is, number of ways to reach the $i$-th blocked cell if $i < j$. (There is no path
that visits the $j$-th
62.
Confession: I sent problem H to goodbye Going to be 100% honest here, I sent problem H to goodbye. I feel really bad to authors of Goodbye 2023 for ruining their round, it seems the round would have been better by just removing H. As much as the community is out here roasting [user:74TrAkToR,2023-12-31], I also had a part to play in this contest. I wish to be as transparent as I can here without saying any classified information (apologies to [user:KAN,2023-12-31] and [user:74TrAkToR,2023-12-31] if anything here shouldn't be disclosed).
To give some context, here is what went down in goodbye round from my perspective:
- 13 days before contest: KAN asks me if I can source a 1E for goodbye. I asked traktor to send me the testing gym so that I could gauge how hard the 1E should be. He told me he will send me after he translates the statements. (UPD: Note that the IMO 1986 problem was already removed before this stage which is why a new 1E was needed, I never saw this IMO problem)
- 11 days before contest: traktor send it...
number of needed rounds (recently it is pinely 3, goodbye, hello and I predict
that there might not be
63.
1st Universal Cup Announcement Hello everyone, we are happy to announce that the 1st Universal Cup is started officially.
Universal Cup is a non-profit organization dedicated to providing training for competitive programming teams. Our website is [https://ucup.ac/](https://ucup.ac/) (in English and Chinese).
In recent years, Chinese problem-setter teams have created a great number of high-quality contests. We have reached an agreement with most of these setters, that they agree to provide contest materials to Universal Cup for hosting mirror contests before publishing the set in public. We believe that such an arrangement can provide good opportunities to teams who want to do better in the future competing.
Every year, with the permission of the problem setter team and without involving copyright disputes, the Universal Cup will hold mirror contests for some undisclosed competition sets. It is expected to hold at least 10 contests a year. We will simulate the actual situation in the competition, using the ...
In recent years, Chinese problem-setter teams have created a great number of
high-quality contests
64.
Polygon Updates (June — August 2021) Hello, Codeforces.
I and [user:DK318,2021-08-19] joined the Codeforces team in June. These three months we mainly dealt with the development of the Polygon platform. In this post, we would like to present to you a list of what we have done during this time. Most of the changes were made to attain easier problem creation. This list does not include minor bug fixes or any improvements that are invisible to users.
#### Tables support when rendering statements in HTML
Now it's possible to insert the most basic tables in your HTML statements. For example, you can show the scoring system of your problem or insert several images side by side. Only column text alignment and border specification are supported now.
<img src="/predownloaded/4a/4a/4a4a6c726e96df40929803a1276a448947d6ebed.png" style="width: 800px; margin-left: auto; margin-right: auto; display: block"/>
#### A brief manual for writing statements
We bet a lot of users who wrote statements were confused by the fact ...
revision number also doesn't change so the reverted changes will become the
latest revision after
65.
Codeforces Round #812 (Div.2) Hi Codeforces!
==================
[user:_dlbm17,2022-06-25], [user:Demen100ns,2022-06-25], [user:Spyofgame,2022-06-25] and I are delighted to invite you to participate in [Codeforces Round #812 (Div. 2)](https://codeforces.me/contests/1713).
- Start time: [contest_time:1713]
- Duration: **120 minutes**.
- Number of tasks: **6**, including at least **one interactive** problem. Make sure to read [this blog](https://codeforces.me/blog/entry/45307) and familiarize yourself with these types of problem before the round!
<spoiler summary="This contest is brought to you by:">
- <a href = "https://www.facebook.com/HocvienPTIT">PTIT</a>, my university.
- <a href = "https://discord.gg/vKjE9xan">Code Mely</a>, a Vietnamese fanpage for Computer Science.
</spoiler>
<img align="right" src="https://i.ibb.co/VLCYnxH/received-1102672770650793-1.png" width="60%" height="60%">
Special thanks to:
- <span>[user:errorgorn,2022-08-02] for wonderful coordination</span><span style="col...
- Start time: [contest_time:1713] - Duration: **120 minutes**. - Number of
tasks: **6
Announcement of Codeforces Round 812 (Div. 2)
66.
On AI ruining "solving math problems with computer" [a year later] I guess you were right in the part "a year from now LLMs will solve problems on your level". You were also saying something along the lines of "you'll change your mind when it starts affecting you". In this part, you were wrong.
Cheaters always existed, and they always will. LLMs make it easier to cheat, true. There is no way of completely preventing LLM cheating (or any other kind of cheating) in online competitions.
I just coordinated the round everyone is buzzing about, so I can with confidence say that in the CF rules for coordinators and authors, there isn't anything about making problems LLM-proof. Not for easy problems, not for hard problems, nothing. And I doubt any such rules will appear. LLMs are forbidden by the rules, that's that.
So we, as honest participants (yes, I will assume that you are an honest participant, otherwise this blog is not applicable to you and I don't care about you), will have to accept that some problems in the future rounds will be LLM-able, ...
everyone solves G in 5 minutes, but then you open it and it is a scary number
theory in which you need 10
67.
Codeforces: Results of 2018 Hi Codeforces!
February 2019 is already on the calendar, which means that I was late with the report for 2018. Better late than
never! Let's remember last year.
In 2018, [user:_kun_,2019-02-05], [user:300iq,2019-02-05] and [user:arsijo,2019-02-05] joined the team of coordinators. The work of the coordinators is headed
(and is the coordinator of the coordinators) [user:KAN,2019-02-05]. I really hope that a more measured schedule of preparing rounds by
a large team of coordinators will give a better insight into the contests. The main innovations in the platform are implemented
by me and the developers [user:kuviman,2019-02-05], [user:fcspartakm,2019-02-05], [user:MaximShipko,2019-02-05]. Great work on the organization of events and
prizes mailing was done by [user:gKseni,2019-02-05].
Special thanks to the writers of the problems and testers. It is your content that charges the community with life and unites
all of us. Thank you for the problems!
And now let's summarize...
"/>
The number of browser sessions did almost + 30% in 2018! , "/>
The number of page views, almost + 35% in 2018! , "/>
The number of visitors, almost + 25% in 2018, the year! , Not included in the images, but there is a significant increase in the number
of hosted rounds (70
68.
Happy Birthday, Codeforces! Dear Codeforces, <img src="/predownloaded/32/a6/32a6b841dd1f306d9f2f1b232ef710ed9a27c350.jpeg" style="float:right; margin:0 1em 1em 1em;"/>
Happy 10th anniversary from Yandex! Over the past ten years, you have become more than just a platform for competitions having developed into a community hub where people can socialize, discuss interesting tasks and make useful contacts — a large part of life for every competitive programmer. Keep it up – continue growing and developing!
Codeforces, with its immense contribution to competitive programming, is very important to the entire community of sport programmers around the world. Yandex actively supports programming contests and competitions and appreciates what Codeforces does, having benefitted from a large number of talented employees with a background in competitive programming. It wouldn’t be the same without this community.
We would also like to use this opportunity to thank [user:MikeMirzayanov,2020-04-01] for Polygon, which ...
and competitions and appreciates what Codeforces does, having benefitted from
a largenumber of
69.
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...
"add a number to the first kind values in some intervals". Keep the meanings
of each kinds of values, $A_{a,i}$ to $A_{a,i} + x$, $x$ can be a negative number 3. Query for the max
$A_{1,i} + A_{2,i, $\Phi(x)$ be the sum of $d(t)$ for all existing tags. And since $d(t)$ is
$O(\log n)$ and thenumber, $\min(A_i, x)$ 3. For all $i \in [l,r]$, change $A_i$ to $A_i + x$, $x$ can be
a negativenumber, **Task 1**. In this task, we can maintain the number of the first kind of
values inside each node, 1. For all $i \in [l,r]$, change $A_{i}$ to $A_{i} + x$, $x$ can be a negative
number. 2. Query, Then, let $w(T)$ ($T$ is a tag class) be the number of nodes which has at least
one tag in $T, When we are doing the interval min operation for number $x$. let
`break_condition` be `l > rr || r, {i}$ to $A_{i} + x$, $x$ can be a negative number. 3. Query for the sum of
$B_i$ in $[l,r]$.
70.
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$.
...
Essentials of Elementary Number Theory, Let us now define a prime number. A prime, Theorem"> This function is at the heart of most elementary number theory.
$\gcd(x,y)$ is defined as the, element $g^t$ with some $\gcd(t, \phi(n))$ is $\frac{\phi(n)}{\gcd(t,
\phi(n)}$. Thenumber of, of number theory. Let $a \mid b$ (read a divide(s) b) for some $a,b \in
\mathbb{Z}$ for some if, of this blog. Let $\pi(n)$ be the prime counting function, which tells you the
number of primes less, property. These are known as carmichael numbers. For a number to carmichael it
must be square free, sense having multiples of a number that is not coprime to $n$ is akin to
partially multiplying by $0, those while looking for contradicting information. However this requires us to
factor anumber which, whose order is $\phi(p)$. Let $f(d)$ be number of elements with an order of
exactly $d$. Then $d, $ is $x \equiv 1,-1 \mod p$. If a number passes this test as well its
considered a base $a$ strong, $ such that $a^k \equiv 1 \mod m$. This is concisely written as $k = ord_m(a)$.
If we had anumber $g, If $\gcd(x,y) = 1$, then in a sense you can tell that $y$ does not help a number
divide something, If we use this to solve for all $n$, $\mu(n)$ is $0$ if some $p^2 \mid n$, $-1$
if an oddnumber of, Let $\pi_{x,m}(n)$ tell us the number of primes that are less than $n$ and are
$x \mod m$ for some, Let us now look at the additive structure of some number mod $n$. Let $1 \le a
\le n$ such that, This is a blog starting from the very basics of number theory, in a way that
flows fluidly from one, This set of elements is called a "Reduced residue system(RRS)". The number of
elements in the RRS, }$. Examples of these function are $\phi(n)$ the number of coprime residues mod
$n$, $\sigma(n)$, the sum of
71.
Good Bye 2025 Editorial We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated!
<!-- You lost the game. -->
<spoiler summary="Rate the contest">
- Great contest:
- Good contest:
- Average contest:
- Bad contest:
</spoiler>
---
<spoiler summary="Did Franklin (from problem D) succeed in massacring a village of innocent elves like Frieren and Dilhan (from problem E)?">
The official lore is that he got lost in a forest of oddly colored Christmas trees (from problem F) and decided instead to write this editorial.
</spoiler>
<!-- ########### -->
<!-- #PROBLEM A# -->
<!-- ########### -->
<h2>[problem:2178A]</h2>
<spoiler summary="Did you like the problem?">
- Great problem:
- Good problem:
- Average problem:
- Bad problem:
- Did not solve:
...
Consider the number of 'Yes's in the string, and what happens to this, Figure out how to count the number of chains containing a specific, Figure out how we can compute the number of chains ending at chord $1, Find an upper bound on the number of elves that can survive., For a given chord $j$, the number of chains ending at $j$ is the, In addition to storing the parity of number of chains ending at chord, The number of white vertices does not change. It also seems a lot of, What can we say about the number of 'Yes's. , number of chains is [number of chains ending at the chord] x [number of chains
starting at the chord
Tutorial of Good Bye 2025
72.
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...
Define the dp state $f_{l,s,d}$ as the number of the permutaion length of $l$
with exactly $d$ such, If two numbers $a,b$ satisfying $a+bnumber not less than $\lceil \frac{m
Tutorial of Codeforces Round 745 (Div. 1)
Tutorial of Codeforces Round 745 (Div. 2)
73.
How to come up with the solutions: techniques As I work with students I often face the situation when if a problem doesn't seem clear to a student at the first sight, it makes them unable to solve it. Indeed, you always hear about specific methods and techniques. But you don't hear about how to think in order to apply them. In this note I'll try to sum up my experience of solving programming contest problems. However, some pieces of advice will also be applicable for olympiads in mathematics and your first steps in academic research.
So you've read a problem and you don't know how to solve it. Try the following techniques, some of them can often come handy.
##### Technique 1: "Total Recall"
Try to remember some similar problems that you had to solve. Quite many problems do not have a brand new idea. So probably, you can use your experience of solving a similar problem to solve this one.
##### Technique 2: "From Specific to General"
Let's say that you've found the solution for the problem (hurray!). Let's consider ...
* the solution always exists; * item the number of states isn't large.
74.
April Fools Day Contest 2024 Hello, <s>April Fools lovers</s> Codeforces!
We, [user:AlperenT,2024-03-26], [user:flamestorm,2024-03-26], [user:toxicpie9,2024-03-26], and [user:willy108,2024-03-26], would like to invite everyone on Codeforces to [contest:1952]! The 12th April Fools Day Contest will take place on [contest_time:1952]. This is a joke competition in which solving the problem is often easier than figuring out what the actual task is.
In this round, you will be given $n$ cool bugaboos where $-1 \le n \le \textbf{[REDACTED]}$ and **2** hours to solve them. The contest will use extended ICPC rules (no hacks, the standings are decided by the number of solved problems and penalty time earned on them). You can submit solutions in any language allowed by Codeforces, unless the problem says otherwise.
Please note that the round is **unrated** and that the penalty for a **wrong submission** is **10** minutes.
To get an idea of what the contest will look like, you can check out the contests of the pas...
decided by the number of solved problems and penalty time earned on them). You
can submit solutions in any
Announcement of April Fools Day Contest 2024
75.
[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...
negative number // better way: (a - b + mod) % mod cout << sub << '\n';, Also, if you want to check if a number exists in a multiset use the `find()`
function instead of, Why? Because the time complexity is logarithmic in the size of the container +
linear in thenumber
76.
Codeforces Global Round 25 Xin chào Codeforces (・ω・)ﾉ
We are pleased to announce the resumption of the Global Rounds. Thanks to XTX Markets for supporting the initiative! In 2024, we will hold 4 such rounds. The series results will take into account the best 3 participations out of 4.
On [contest_time:1951] we will host [contest:1951]. **<img src="/predownloaded/2e/e2/2ee2f0f95f05aae6ca6f47812dae2dc2aabf277b.png" style="width: 200.0px;float: right;margin: 0 1.0em 1.0em 1.0em;max-width: 100.0%;max-height: 100.0%;">**
Codeforces Global Round 25 marks the first round in the 2024 series of Codeforces Global Rounds. These rounds are open and rated for everyone.
The prizes for this round are as follows:
- The top 30 participants will receive a t-shirt.
- 20 t-shirts will be randomly distributed among participants ranked between 31 and 500, inclusive.
The prizes for the 4-round series in 2024:
- In each round, the top-100 participants get points according to the [table](https://pastebin.com...
- Duration: $3$ hours. - Number of problems: $9$ problems. - Score
distribution: $500 - 1000
Announcement of Codeforces Global Round 25
77.
Petition to revoke unrated account permissions to post comments/blogs Unrated Account Disaster
==================
Recently there have been an obscene number of unrated accounts showing up. Several of them have inappropriate names, so I won't give examples because I want to keep this post clean, but I'm sure you have seen them in the comments. They are likely all by the same individual, possibly with a few copy-cat troublemakers as well.
Recently, certain ones have begun to spam useless comments on old posts to clog up the recent actions, effectively hiding all relevant conversations except on the blog posts they spam on. For whatever reason, these are overwhelmingly on [user:Errichto,2020-07-10]'s old blog posts. Occasionally there are also a flood of obscene blog posts made by the user themselves.
Here's an example of what I mean:
#### This is obnoxious and I would like to see it stop.
The current solution clearly doesn't work. As soon as they get banned or muted or whatever, they c...
Recently there have been an obscene number of unrated accounts showing up.
Several of them have
78.
CPIdeas: use AI to generate competitive programming ideas Hello Codeforces!
Being asked to propose competitive programming questions is pretty haunting. When you're out of fresh ideas, I used to do one of the two things. One, is to search in the old pile of problems, hoping to find some room of modifications and improvements. The second, is to come up with random words, like "chessboard inversion counting", and hopefully resemble interesting problems from them.
This process is pretty boring, so I have been trying to use machine learning to generate ideas and even complete competitive programming problems. The result is *CPIdeas*! Check it out here: https://fjzzq2002.github.io/cpideas/.
*How was it made?* I collected problems from AtCoder (ABC, ARC, AGC) and used these problems to fine-tune GPT-3, the OpenAI model. It's quite tricky to get things right though and it's still far from perfect.
*How should I use it?* Look through these ideas. Scroll down. Be tolerant and creative. That's it.
*How should I use these ideas?* For the ...
operation on A any number of times: choose an integer i such that 1<=i<=N-1,
and replace the last element of, You are given a string S of length N. Let the number of occurrences of each
character in S be num1
79.
2nd Universal Cup Announcement Hello everyone, we are happy to announce that the 2nd Universal Cup has started officially.
The Universal Cup is a non-profit organization dedicated to offering training resources for competitive programming teams. Our website is [https://ucup.ac/](https://ucup.ac/) (in English and Chinese).
In the previous season, over 750 teams from more than 300 affiliations all over the world, registered and participated in a total of 22 stages, encompassing contests from Asia, Europe, and America.
With the permission of contest setters and without involving copyright disputes, the Universal Cup will hold mirror contests for some undisclosed competition sets. It is expected to hold at least 20 contests in this season. We will simulate the actual situation in the competition, executing the board freeze in the last hour. At the same time, we will provide an overall rating board, which will help the team to make a reasonable assessment of itself.
Over the past few weeks, the committee has...
/). For a great number of Chinese teams, we believe this will be a good
practice to prepare for the
80.
How to use Codeforces [GUIDE] I see a lot of newcomers struggling to use the website to it's fullest, so I decided to write a blog that has all important information about how to use Codeforces in a single place. I will update it with time, so feel free to write your suggestions/questions in case I missed something and I will be glad to add it to the post!
I would like to thank [user:_Vanilla_,2022-02-05] and [user:mesanu,2022-02-05] for helping me write the blog, and [user:Monogon,2022-02-05], [user:down,2022-02-05] and [user:AlperenT,2022-02-05] for proofreading and giving suggestions.
#### Navigating through pages
It's possible to navigate through most pages of Codeforces using the bar on the top, I will talk about what each tab does more in depth below:
#### The Help Page
The help page contains the answer to a lot of questions about Codeforces, such as rati...
, an expert's value would count as 3. This number changes some time after
upvoting, not instantly, so, The contribution number is the amount you contribute to the community. You get
contribution by, To view a solution click the Source (the long number in the first column of the
table). To select
81.
[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, ...
$v$, it is not that easy to count the number of sets $S$ of size $k$ such that
$t(S)$ contains $v, #### Number of $2$-edge connected graphs, **Problem.** Count the number of labelled trees on $n$ vertices (number of
trees where vertices are, Let us count the number of **rooted** trees on $n$ vertices. Call this number
$t(n)$. If we remove, number of labelled connected graphs on $n$ vertices. There are different ways
to compute this, but
82.
Blogewoosh #3 Hello, codeforces!
This time I've decided to choose a task from my own contest which took place last April and was known as the Grand Prix of Poland. If you want to write this contest virtually in the future, then consider not reading this blog. If you've participated in this contest and maybe even solved this task, then anyway I recommend reading it, cause this task has many very different solutions, each of them being very interesting (in my opinion). It's also a reason why this blog is longer than previous ones.
I'll write about task C "cutting tree" (not uploaded to the ejudge yet :/). The statement goes as follows:
You are given a tree with $n$ vertices ($1 \leq n \leq 2 \cdot 10^5$). The task is to calculate $f(k)$ for each integer $k$ from the range $[1, n]$ where $f(k)$ is defined as the maximum number of connected components of size $k$ which we can "cut off" from the tree. A connected component of size $k$ is a set of $k$ vertices such that it's possible to traverse ...
(k)$ for each integer $k$ from the range $[1, n]$ where $f(k)$ is defined as
the maximumnumber of
83.
Codeforces Global Rounds Hello!
It is always satisfying and important for me when former contest participants offer their help to the community and support the development of programming competitions. And now I am in a hurry to share the news that thanks to the support of <a href="https://www.xtxmarkets.com/">XTX Markets</a> and the personal participation of Yuri Bedny and Alexander Gerko, we are launching a new line of Codeforces Global Rounds. Hooray!
<img src="/predownloaded/2e/e2/2ee2f0f95f05aae6ca6f47812dae2dc2aabf277b.png" style="width:200px; float:right; margin: 0 1em 1em 1em"/>
Like many of you, I had never heard of <a href="https://www.xtxmarkets.com/">XTX Markets</a> before but it is one of the largest quantitative-driven electronic liquidity providers in the world. I understand little about the financial sector, but with their 34,148 cores and 42 petabytes of usable storage in their research cluster, XTX’s rapid growth and strong market share globally speak for themselves.
So, in 2019, w...
rounds will be 2-3 hours, depending on the number and complexity of the
problems. All such rounds will be
84.
Blogewoosh #7 Hello, codeforces!
Long time no see, right? So maybe it's a good idea to try to return to my blogs slowly. This time the blog will be about a trick, which usually isn't necessary to solve a task, but can be useful to make implementation much more comfortable.
Let's look at [this](https://codeforces.me/contest/932/problem/F) 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
85.
Codeforces: results of 2014 <img src="http://assets.codeforces.com/images/statistics-2014/snowman-en.png" style="float:right; margin:0 1em 1em 1em;"/>
Hello 2015! Hello Codeforces!
It seems it is time to take stock. Frankly, I was almost feared to start summing statistics of 2014. In 2013 Codeforces showed rapid growth so that it would not be surprising to look bad on the background of 2013. Certainly not! I was pleasantly surprised by the statistics and reports!
Just below is a list of major events and achievements of Codeforces over the year. For you, it's just a list, but please note — every item includes hard work of multi-day Codeforces team, writers of problems, the organizers of contests and tournaments, problem testers and volunteers. Yay! Together we have done all of this:
* introduced Codeforces API
* added (and sometimes improved) all Andrew [user:andrewzta,2015-01-03] Stankevich contests
* Codeforces supported mode to work as iframe-widget, and Codeforces helped Google to run https...
://assets.codeforces.com/images/statistics-2014/2014-pageviews.png"/>
Number of pageviews (from, ://assets.codeforces.com/images/statistics-2014/2014-registered-users.png"/>
Number of registered users, ://assets.codeforces.com/images/statistics-2014/2014-submissions.png"/>
Number of submissions (attempts, ://assets.codeforces.com/images/statistics-2014/2014-visitors.png"/>
Number of unique visitors (from, ://assets.codeforces.com/images/statistics-2014/2014-visits.png"/>
Number of visits (sessions) (from
86.
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...
####Speak in a language the receiver will understand It's surprising but I have
received anumber
87.
One-letter variables Complete shitpost, don't take it seriously. We were discussing `#define int long long` and I suggested defining it to one letter if you want to save on typing so desperately. [user:jeroenodb,2025-10-11] said that those are reserved for variables, which prompted me to think, "Is there a letter I don't standardly use for some particular purpose?" Then I compiled the following list, and then I thought, "Well, I already wrote it, let's put it on cf", so here we are.
~~~~~
a - array, but also all sorts of stuff
b - second array
c - third array / count
d - delta / divisor
e - event / edge
f - flag
g - graph / second flag
h - third iterator / third flag / height
i - iterator
j - second iterator
k - third input size / some parameter (i know, those are all parameters, but for some reason k is parameter)
l - left
m - number of edges / second input size
n - input size
o - ???
p - permutation / position
q - number of queries / query / second permutation / second position
r - r...
all parameters, but for some reason k is parameter) l - left m - number of
edges / second input
88.
Sometimes it's not their fault. Hello!
It's 2023 now, and everyone is happy and hoping for a good year, which many good contests to come. So I want to say about one thing that I saw in most of the contests from last year, which I was pretty much annoyed about it and decided to speak about so that this year we will hope to have a better experience doing contests here.
I have been in this community for more than 3 years now, not very long, but definitely enough to say that although the number of participants did increase, the number of users increase dramatically, but the number of people that respond to the contests positively don't. It actually did decrease though. I still remember that 500+ upvotes for a contest announcement are a normal thing back then, but I rarely see them now. And a common thing right now, every single contest that is over will have some comments criticizing it, but not in a good way at all. So I will make this quick for certain types of comments like that.
I don't know if you do but I ...
say that although the number of participants did increase, the number of users
increase dramatically
89.
Codeforces Round #333 — editorial ### Hints:
[div2A](#div2A): Try conversions between bases.
[div2B](#div2B): Solve a simpler version of the problem where $A_{i+1} \neq A_i$ for all $i$.
[div1A](#div1A): What are the shortest paths of the vehicles? what's the shorter of those paths?
[div1B](#div1B): Forget about the ceiling function. Draw points $(i,A[i])$ and lines between them — what's the Lipschitz constant geometrically?
[div1C](#div1C): Some dynamic programming. Definitely not for the exp. score of one person — look at fixed scores instead.
[div1D](#div1D): Compute $dif(v)$ in $O(N)$ (without hashing) and then solve the problem in $O(N^2)$. You need some smart merges.
[div1E](#div1E): Can you solve the problem without events of type 1 or 2? Also, how about solving it offline — as queries on subsets.
### <a name="div2A"></a>Div. 2 A: Two Bases
------------------------------------
It's easy to compare two numbers if the same bas...
currently processed number.
Tutorial of Codeforces Round 333 (Div. 1)
Tutorial of Codeforces Round 333 (Div. 2)
90.
How to sweep like a Sir ### Cutting to the chase
Clearly you don't need a PhD in Computing to sweep in the yard , but one might be useful in order to know linear and radial sweep algorithms. So , what's all about ? It's just what it sounds it is , sweeping linear ( up to down , for example ) or radial ( making a 360 degrees loop ).
How this can help? [cut] Well...
### Linear sweep
Suppose you a set of objects in an Euclidean plane. We need to extract information about some objects. The method of linear sweeping takes a line and moves it on a fixed direction. Usually the line taken would be vertical and the direction would be left to right or up to down.
Quite abstract for the moment , huh ? Let's go to a more specific example.
#### Rectangle union area
This example is well known. You have a set of rectangles with edges parallel to the OX and OY axes. What is their union area.
Well , first of all , let'...
#### Maximum number of points on a line
91.
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...
Calculate number of $m \le n$ such that $gcd(a^{2}+m^{2}, 4(a+m, ? Number of vertices is exactly $1$ bigger than number of edges. OK, so number
of components in a
92.
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...
`w` is an optional edge label. You do **not** need to enter `n m`,
representing thenumber of nodes
93.
For contest writers: proposal tracking system <i>In 2021, some details (including requirements for problem writers) were changed. Read <a href="https://codeforces.me/blog/entry/85259">the link</a> for details.</i>
Hello, Codeforces!
New year brings changes to the Codeforces team. <a href="/blog/entry/49466">As you probably know</a> [user:GlebsHP,2017-01-04] completed his work as the chief coordinator of Codeforces. Gleb, thanks a lot! You did an excellent job and coordinated a lot of interesting rounds. You're a professional, an interesting person, you have impeccable taste to problems, and you proved to be brilliant and talented writer. Thank you that you were with us!
Hope to see your tasks on Codeforces many times again!
Nikolay [user:KAN,2017-01-04] Kalinin came to Gleb's place. He is also an experienced participant, Nikolay has already held several rounds as a coordinator. [user:KAN,2017-01-04] seriously engaged in programming contests since he was 12 years old. His major achievements: he won twice All-Russian Scho...
> Codeforces rounds attract record number of participants from around the world
(the next frontier is, color | the minimum number of rating contests ------------- | ---------- blue |
25 violet | 15
94.
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...
choose "odd" or "even", and then choose from each bucket an odd (even) number
of elements to negate
95.
Blogewoosh #4 Hello, codeforces!
It's time to continue the series of Polish tasks. I've decided to write about my own task one more time. Its name is "cook" ([you can submit here](https://szkopul.edu.pl/problemset/problem/9NFtPM59qGWa7wdn570ifuP0/site/?key=statement)). The task isn't very hard, but it uses cute (in my opinion) trick. The statement goes as follows:
There is a cook in a restaurant. He has $n$ ($1 \leq n \leq 10^6$) orders which he must fill. Every order is a piece of paper, and all orders are speared on a spindle (sharp stick with pierced pieces of paper) in a fixed order which cannot be changed. Normal cook would just take orders one by one from the top of the spindle and fill them in this order, but the cook in this task has supernatural cooking powers and can combine orders to fill them faster. In particular, if at some moment there are $k$ out of $n$ orders still on the spindle, he can choose one of three options:
$---$ He can take the topmost piece of paper and fill this...
It's easy to observe that in each moment our situation can be described by the
number of orders on
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Sep/03/2026 23:35:41 (h1).
Desktop version, switch to mobile version.
Supported by
