Rating changes for last rounds are temporarily rolled back. They will be returned soon.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | jiangly | 3640 |
| 2 | Benq | 3593 |
| 3 | tourist | 3572 |
| 4 | orzdevinwang | 3561 |
| 5 | cnnfls_csy | 3539 |
| 6 | ecnerwala | 3534 |
| 7 | Radewoosh | 3532 |
| 8 | gyh20 | 3447 |
| 9 | Rebelz | 3409 |
| 10 | Geothermal | 3408 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 151 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ 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.
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...
2.
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 ...
A problem collection of ODE and differential technique, I'm thinking to generalize this technique to other problems. But I don't find
amazing results, Thank [user:Elegia,2020-04-23] and [user:djq_cpp,2020-04-23] for developing this
technique. Thank
3.
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">
 you should ask them “Do I have to know some standard technique to
solve this?” Pay attention: not, them “Do I have to know some standard technique to solve this?” Pay attention:
not ask how to solve
4.
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...
5.
Some thoughts on recent discussions Hello everyone!
I finally decided to write some response/explain my view after all recent discussions of my problems and rounds I coordinate, and I would like to make a few points.
**1.** After some recent contests there were a lot of comments saying that Data structure problems should appear as easy problems (say, D2A-D2D in a Div2 of $6$ problems)
I don't think I agree with this. To begin with, I don't think that having Data Structure problem is a requirement for a good contest at all, not just in first few positions.
However, for positions D2A-D2D, I just don't see a way to properly include data structure problems. Take some Data Structure problem, it consists from two parts:
<ul>
<li> Knowing/implementing the Data Structure </li>
<li> Actually thinking about the problem, and how this Data Structure...
6.
[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...
very brief and assumes the reader already understand the technique so it will
be hard for people who, This is actually a very well-known technique and most people should already
know this. This trick
7.
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 ...
##### Technique 1: "Total Recall", ##### Technique 2: "From Specific to General", ##### Technique 3: "Bold Hypothesis", ##### Technique 4: "To solve a problem, you should think like a problem", ##### Technique 5: "Think together", ##### Technique 6: "Pick a Method", ##### Technique 7: "Print Out and Look", ##### Technique 8: "Google", This technique can only be used if the round/contest rules allow it. If the
problem is about, This technique is only applicable to team contests. In group of two or three
persons start saying
8.
[Tutorial] Square Root Techniques _This is my 100th CF blog!_
This is a list of techniques with $O(\sqrt n)$ time complexity.
Watch the lecture https://youtu.be/BJhzd_VG61k, with timestamps!
1. Square root decomposition — split the sequence into blocks of fixed size.
2. Splitting objects (e.g. vertices) into light and heavy.
3. Square root decomposition by the time of queries & rebuilding the structure.
4. Mo's algorithm — processing queries in proper order and updating the answer by erasing/inserting new elements. https://cp-algorithms.com/data_structures/sqrt_decomposition.html
5. Strings — if the sum of lengths is $S$ then there are at most $\sqrt{S}$ distinct lengths.
6. Birthday paradox & baby-step giant-step. See P4 and P6 [here](https://codeforces.com/blog/entry/95571), and see https://cp-algorithms.com/algebra/discrete-log.html.
P1. [problem:398D]
P2. [problem:220B]
P3. <s>[problem:86D]</s> (actually, skip this one because it's boring)
P4. Count triangles in a graph, i....
9.
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.com/blog/entry/46620)
- [Number of points on Convex hull with lattice points](https://codeforces.com/blog/entry/62183)
- [FFT, big modulos, precision errors.](https://codeforces.com/blog/entry/48465)
- [Number of ways between two vertices](https://codeforces.com/blog/entry/19078)
- [Mathematics For Competitive Programming](https://codeforces.com/blog/entry/76938)
- [FFT and NTT](https://codeforces.com/blog/entry/19862)
- [Burnside Lemma](https://codeforces.com/blog/entry/51272)
- [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.com/blog/entry/76836)
- [On burnside (again)](https://codeforces.com/blog/entry/64860)
- [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.com/blog/entry/55912)
- [Probabili...
Query Based Rerooting Technique](https://codeforces.com/blog/entry/76150) -
[Almost-LCA in Tree\n, ) - [Random Walk: Hard version](https://codeforces.com/blog/entry/23576) -
[VeniceTechnique\n, ](https://codeforces.com/blog/entry/60442) - [A problem collection of ODE and
differentialtechnique
10.
[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...
11.
The Reason You are Bad at Codeforces — You are Not Russian Enough If you are triggered by this clickbaity blog title, you are probably interested in improving your Codeforces skills. Now, I will share my point of view on the differences between Codeforces and ICPC contests, and how you can, in my humble opinion, maximize your Codeforces rating gain.
I mostly consider that all conceivable competitive programming problems need three aspects of skill:
1. Observation — the ability to understand the problem and come up with non-trivial properties.
2. Technique — the ability to apply a well-known algorithm or data structure to the problem.
3. Implementation — the ability to code fast and debug fast.
Collaterally, I refer to these three skills as Russian-ness, Chinese-ness and American-ness, respectively, for reasons you will soon see below.
## Observation (Russian-ness)
Observation means that you stare at some problem for a sufficient amount of time and you are able to reduce it to some easier problem. One good proble...
## Technique (Chinese-ness), . Technique — the ability to apply a well-known algorithm or data structure to
the problem, Technique is the more common thing you will learn at any competitive
programming course, such as
12.
Sums and Expected Value — part 1 part 2: https://codeforces.com/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...
### Problems for "contribution" technique, ### Technique "Contribution to the sum"
13.
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.com/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.com/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...
14.
You won't believe how this simple trick defeated the unexplained bug destroying every top LGM ### TL;DR
Currently people are discussing a slowdown bug on Codeforces that seems to happen randomly, and can cause code to run 100x slower and get TLE. More details in [user:pajenegod,2024-03-03]'s [blog post](https://codeforces.com/blog/entry/126654).
In this article, I present a mitigation: add the following to your code.
~~~~
#include <windows.h>
void *operator new(size_t size) {
if (void *ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
throw std::bad_alloc{};
}
void operator delete(void *ptr) {
HeapFree(GetProcessHeap(), 0, ptr);
}
~~~~
<spoiler summary="If you use malloc/free in C++ (you shouldn't), also change them.">
~~~~
void *my_malloc(size_t size) {
if (void *ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
throw std::bad_alloc{};
}
void my_free(void *ptr) {
HeapFree(GetProcessHeap(), 0, ptr);
}
~~~~
</spoiler>
<spoiler summary="If you use aligned new/delete in C++, also change the...
15.
Competitive Programmer's Handbook — a new book on competitive programming Competitive Programmer's Handbook is a new book on competitive programming, written by me. The book is still in progress but almost ready, and I decided to release it now for a wider audience.
You can download the book here:
https://cses.fi/book.html
The book consists of 30 chapters and is divided into three parts. The first part discusses basic topics such as programming style, data structures and algorithm design. The second part deals with graph algorithms, and the third part introduces some more advanced techniques.
The book assumes that the reader knows the basics of programming, but no background on competitive programming is required. I think that the book is useful for future IOI participants, as the book covers most topics in the IOI syllabus.
The final version of the book will be ready later this year. The PDF version of the book will be available for free also in the future, and in addition, there will be a printed version that will cost something.
Before t...
16.
Lecture #3 — Exchange arguments (sorting with dp) Hi. I'm back from USA!
I will do a new lecture tomorrow (Thursday) at 2pm CEST on my Youtube channel: [https://www.youtube.com/watch?v=7hFWrKa6yRM](https://www.youtube.com/watch?v=7hFWrKa6yRM).
Watch me live (and ask questions), or just watch the video later.
This will be part 1, and I will do part 2 in a few days (maybe Tuesday).
**UPDATE** — part 2 is coming on Thursday, same time. Link: [https://www.youtube.com/watch?v=gXxu-Cr4b4c](https://www.youtube.com/watch?v=gXxu-Cr4b4c).
There are no prerequisites this time.
I recommend reading the materials below in advance, and trying to solve problems 1 and 5.
If you are strong, just read problems and see if you can't solve something (maybe problem 8?).
### Technique "Exchange Arguments"
If we're given $n$ items and we should choose some of them and choose their order, we should sort them with some strange/tricky comparator, and then do $O(N^2)$ dynamic programming.
The dp should be $dp[pref][used]$ — best po...
### Technique "Exchange Arguments", Not all problems use the described technique. I think it's a good lesson to see
some similar
17.
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.com/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...
tag technique to solve it. But we can use an auxiliary array $D_i$ with the
initial value of all, We can use the technique introduced in the previous part about interval min/max
operations to
18.
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.com/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...
By the way, this is a very common technique in problems like "you are given
operations X and Y, Many beginners have developed this "technique" for solving problems. They look
at the constraints, Maybe this technique of guessing and forcing DP or greedy works well enough for
easy problems and
19.
A Beautiful Technique for Some XOR Related Problems ## Inspiration
I'm very excited about this blog, as it took me quite a lot of effort and scavenging through the internet to completely grasp the concept of this technique(That's probably because I have almost zero knowledge in Linear Algebra or I'm just plain dumb). So I feel like I genuinely conquered a challenge, and I really want to share it with someone. But there's no way my CP friends circle will believe it, they'll think I'm just trying to show off :P
So here I am, sharing it on CF. I also created a [personal blog](https://drschwad.github.io/), so that if I ever feel like sharing something again(not only about CP), I can write a blog there. I also added this same post [there](https://drschwad.github.io/2019-08-06-z2-space-xor-trick/), you can read it there if you prefer dark theme. I'll be pleased to hear any thoughts on the blog or if I can improve it in some way ^\_^
## Introduction
Since it concerns Linear Algebra, there needs to be a lot of formal stuff going on ...
A Beautiful Technique for Some XOR Related Problems, bigger, say $10^5.$ That is when we can use Part $2$ of this technique, which,
in some cases, works, internet to completely grasp the concept of this technique(That's probably
because I have almost zero, scavenging through the internet to completely grasp the concept of this
technique(That's probably because I, Now, the problems that can be solved using this technique are actually not much
hard to identify, PS: Does anyone know any name for this technique? I'm feeling awkward referring
to it as 'technique, The whole technique can be divided into two main parts, some problems can even
be solved by using
20.
[Tutorial] How to learn better, and what most people don't get about learning **Disclaimer:** I am not an expert in the field of the psychology of learning and problem-solving, so take the following with a grain of salt. There is not much "scientific" evidence for this blog, and the following is validated by personal experience and the experiences of people I know (who fall everywhere on the "success" spectrum — from greys to reds in competitive programming, from beginners in math to IMO gold medalists, and from people with zero research experience to people with monumental publications for their own fields). This blog only covers one possible way of thinking about knowledge organization and retrieval that I have been using for the past decade or so, but there definitely will be other models that might work even better. Even though I just have a few courses worth of formal psychology experience, I still think the content of this blog should be relevant to people involved with problem-solving.
I hope this helps both students (to make their learning effic...
Maybe there's a better way of naming this reasoning technique, but I went with
the name rigor just
21.
[Tutorial] Matroid intersection in simple words **[This article is also available in [Russian](https://codeforces.com/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...
22.
Three Revolutions of AtCoder Hello. Today I announce three revolutions of AtCoder!
### 1. AtCoder Library (ACL)
We provide a collection of pre-written codes of various algorithms and data structures.
I'll describe details in a [separate post](https://codeforces.com/blog/entry/82400).
### 2. New Color Scheme
Previously, we decided colors by ratings. For example, gold for 3600 and above, silver for 3200 and above, red for 2800 and above, etc.
However, it's not clear what the rating values mean, for example, 2800. If we design the rating system relatively well, in the short term the rating 2800 corresponds to a certain level. The skill required to reach 2800 today is probably similar to that of a year ago.
However, the structure of the contests may change, the number of users may change, the average level of users may change, etc., and the exact value of ratings is very sensitive to these changes (and it may cause inflation/deflation).
Now I believe ranks are more robust against inflation/deflation and ...
23.
[Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges #### Introduction
This is a tutorial/exploration of problems that can be solved using the "DFS tree" of a graph.
For a way too long time, I didn't really understand how and why the classical algorithm for finding bridges works.
It felt like many tutorials didn't really explain how it works, kind of just mentioned it in passing and quickly
just moved on to implementation. The day someone explained what the DFS tree is, I finally understood it properly.
Before, it took me ages to implement bridge-finding properly, and I always had to look up some detail. Now I can
implement it at typing speed.
But more importantly, I began to see how the same techniques can be used to solve graph problems that have more or
less nothing to do with bridges. The thing is, when you have a black box, you can only ever use it as a black box.
But if you have a box that you understand well, you can take it into pieces, repurpose the pieces for completely
different things, all without getting lost...
24.
[Tutorial] Proving the inverse Ackermann complexity of Union-Find #### Introduction
Most of us are familiar with the union-find data structure and the two optimizations one can do on it: _union by rank_ and _path compression_. Most tutorials will introduce these methods and state that if both optimizations are used, the complexity will be $\mathcal{O}((n + m) \alpha(n))$. Here, $n$ and $m$ are the number of vertices and queries respectively. What is $\alpha$? Generally, we are told that $\alpha$ is some mysterious function that grows very slowly: $\alpha(N) < 5$ where $N$ is the number of subsets of particles in the observable universe and whatnot. What it is is usually not clarified very much. And there is typically no proof (or intuition and other such justifications) as to why the complexity is like that: usually we're told that the complexity analysis is quite long and complicated. At the time of writing, both [cp-algorithms](https://cp-algorithms.com/data_structures/disjoint_set_union.html) and [Wikipedia](https://bit.ly/3EvnzrI) are like th...
distribution "seems optimal" with respect to the proof technique., Now let's push this technique to the limit.
25.
On problemsetting 2 [Previous part](https://codeforces.com/blog/entry/70178)
Hi there again! Previous part with opinions of some amazing problemsetters turned out to be interesting for you, so I decided to gather some more opinions :D. I really hope that this post will help someone in their problemsetting future!
#### When and how did you start problemsetting?
[user:300iq,2020-01-11]: April, 2017
[user:maroonrk,2020-01-11]: In 2015 Summer, I hold the first contest with friends at high school club. It was a local Japanese contest.
[user:Radewoosh,2020-01-11]: In high school, so probably for 5 years. I was creating problems for other people from my school as my teacher told me that it's a completely different point of view.
[user:voidmax,2020-01-11]: It was 3 years ago. I was on plane and I didn't have a clue what to do in my free time. Then I realized that I can try myself in problemsetting. Later I created first and one of my favorite problem ([problem:963B]). I was full of inspiration a...
26.
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...
easier for you — it uses the same technique, after all.
Tutorial of Codeforces Round 333 (Div. 1)
Tutorial of Codeforces Round 333 (Div. 2)
27.
Сompetitive programming tutoring – help me fulfil my dream Hi, everyone!
My name is Aleksandr Mokin. I've been teaching competitive programming for 3 years as my main job.
I was a winner of the All-Russian Olympiad in Informatics in 2012, an awardee in 2011 and 2013. In 2018 I became a finalist of the ICPC world programming championship.
In 2019 I started teaching and have helped dozens of people to make progress and reach their goals ([see people's feedback](https://profi.ru/profile/MokinAB/)). Since then I've developed my own approach. I don't just guide people through notorious algorithms, but also teach concrete techniques on how to solve real problems and quickly write a working code.
Now I've decided to try bringing it to another level. I want to reach the worldwide audience: feel free contacting me on [Facebook](https://www.facebook.com/rembocoder/), [Telegram](https://t.me/rembocoder), private messages or e-mail: [[email protected]](mailto:[email protected]). My base rate is **$30/h**.
If I get enough feedback, I p...
28.
My own algorithm — offline incremental strongly connected components in O(m*log(m)) Hello Codeforces!
As all of you know, there are so many known algorithms named after people who invented them — from the easiest ones, like Dijkstra, to the harder ones, like Berlekamp–Massey algorithm. These algorithms were innovative when they were invented, so of course, it's good that they are named after their inventors.
But, today, I've seen a blog about the solution to the problem "compute LCS of two strings in time $O((n + k) \cdot \log(k))$, where $n$ is the sum of lengths of the strings, and $k$ is the number of pairs of matching positions in them". To be honest, it a bit pissed me off that even this algorithm is named after its creators. Is it ok to name the solution to every possible problem after its author? I won't judge it. Anyway, I want my very own Radecki algorithm, so let me give it a try. If anyone has ever heard about it — it's cool. Let me know, and it'll be just another helpful blog on Codeforces.
Let's imagine the following problem: there is...
Let's use the divide and conquer technique on the list of the edges. We can
also think about it
29.
[Tutorial] On Range LIS Queries, Part 1 Hello, Codeforces!
At some point of life you want to make a new data structure problem with short statement and genius solution. LIS (Longest Increasing Subsequence) is a classic problem with beautiful solution, so you come up with the following problem:
* Given a sequence $A$ of length $N$ and $Q$ queries $1 \le i \le j \le N$, compute the length of Longest Increasing Subsequence of $A[i], A[i + 1], \ldots, A[j]$.
But on the other hand this looks impossible to solve, and you just give up the idea.
I always thought that the above problem is unsolved (and might be impossible), but very recently I learned that such queries are **solvable** in only $O(N \log^2 N + Q \log N)$ time, not involving any sqrts! The [original paper](https://arxiv.org/abs/0707.3619) describes this technique as *semi-local string comparison*. The paper is incredibly long and uses tons of scary math terminology, but I think I found a relatively easier way to describe this technique, which I will show in...
any sqrts! The [original paper](https://arxiv.org/abs/0707.3619) describes this
technique as *semi, briefly discuss the application of this technique., increase the $j$. We will use this technique later on.
30.
Combinatorial species: An intuition behind generating functions Hi everyone!
The usage of generating functions is quite common in competitive programming these days. But it seems to happen so, that they're mostly presented as a way to simplify formal manipulation with polynomial coefficients, rather than something meaningful. But there actually is a meaning to all of this, and today I'm going to shed a light on it.
Alongside the blog post we'll uncover the combinatorial meaning of
- The addition $F(x)+G(x)$,
- The multiplication $F(x)G(x)$,
- The exponent $\exp F(x)$,
- The logarithm $\log F(x)$,
- The sum of the infinite geometric progression $\frac{1}{1-F(x)}=1+F(x)+F^2(x)+\dots$,
- The general composition $F(G(x))$
for the generating functions $F(x)$ and $G(x)$ and the underlying structures they represent.
### Prerequisites
- Basic notion of set theory (cardinality of sets, mappings, bijections, cartesian product, disjoint union, etc);
- Polynomials and formal power series (representation, convolution formula, power seri...
31.
The Ultimate Reroot Template Hi Codeforces!
Have you ever had this issue before?
If yes, then you have come to the right place! This is a blog about my super easy to use template for (reroot) DP on trees. I really believe that this template is kind of revolutionary for solving reroot DP problems. I've implemented it both in [Python](https://codeforces.com/contest/1324/submission/240129139) and in [C++](https://codeforces.com/contest/1324/submission/240131453) (the template supports `Python2`, `Python3` and `>= C++14`). Using this template, you will be able to easily solve > 2000 rated reroot problems in a couple of minutes, with a couple of lines of code.
A big thanks goes out to everyone that has helped me by giving feedback on blog and/or discussing reroot with me, [user:nor,2024-01-03], [user:meooow,2024-01-03], [u...
technique called _rerooting_. Long story short, it is a mess to code. Maybe you
could argue that for this
32.
Tutorial: A simple O(n log n) polynomial multiplication algorithm Hi Codeforces!
I have something exciting to tell you guys about today! I have recently come up with a really neat and simple recursive algorithm for multiplying polynomials in $O(n \log n)$ time. It is so neat and simple that I think it might possibly revolutionize the way that fast polynomial multiplication is taught and coded. You don't need to know anything about FFT to understand and implement this algorithm.
Big thanks to [user:nor,2023-07-10], [user:c1729,2023-07-10] and [user:spheniscine,2023-07-10] for discussing the contents of the blog with me and comming up with ideas for how to improve the blog =).
I've split this blog up into two parts. The first part is intended for anyone to be able to read and understand. The second part is advanced and goes into a ton of interesting ideas and concepts related to this algorithm.
Prerequisite: Polynomial quotient and remainder, see [Wiki article] (https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_divi...
, 1) (reweight technique)"> There is somewhat well known technique called
"reweighting" that allows
33.
All You Need is Randomly Guessing — How to Improve at Codeforces I hope [my previous blog](https://codeforces.com/blog/entry/126310) has convinced you that the best way to improve at Codeforces is to be more Russian, i.e. to improve your math capability. Unfortunately, humble mortals such as you and I are not gifted with the talent that esteemed Russian grandmasters such as 74TrAkToR had:
_Surely, it is beneficial to have a code reference for many algorithms and data structures, but I also think that just superficially knowing the algorithm and maybe having implemented it once or twice before is sufficient to use it without a reference?_
_— Some other Codeforces grandmaster_
Therefore, in this blog I will explore the dark side of Russian-ness — randomly guessing — that is forsaken by every Russian grandmaster of the light side I know. However, it has been very helpful to me, and I hope that it serves you well, too.
## Example 1
I will start by using an example to demonstrate my thought process. This problem [1923C](h...
doable by some technique., 1. **Dismiss.** I can say I know how to do this with some technique (i.e.
Chinese-ness) and throw
34.
[Tutorial] Searching Binary Indexed Tree in O(log(N)) using Binary Lifting **NOTE** : Knowledge of Binary Indexed Trees is a prerequisite.
## Problem Statement
Assume we need to solve the following problem. We have an array, $A$ of length $N$ with only non-negative values. We want to perform the following operations on this array:
1. Update value at a given position
2. Compute prefix sum of $A$ upto $i, i \leq N$
3. Search for a prefix sum (something like a `lower_bound` in the prefix sums array of $A$)
[cut]
<br>
## Basic Solution
Seeing such a problem we might think of using a Binary Indexed Tree (BIT) and implementing a binary search for type $3$ operation. Its easy to see that binary search is possible here because prefix sums array is monotonic (only non-negative values in $A$).
The only issue with this is that binary search in a BIT has time complexity of $O(log^2(N))$ (other operations can be done in $O(log(N))$). Even though this is naive, here is how to do it:
<spoiler summary="Implementation">
`int sum(pos)` -> comput...
Most of the times this would be fast enough (because of small constant of above
technique). But if, technique has a name but I am calling it binary lifting because the algorithm
is similar to binary
35.
Sums and Expected Value — part 2 ### Instruction
I recommend this blog also for red users.
Read the theory and problems below, try to solve them.
For solutions and extra insight/tips, watch my stream on Monday or watch the video later.
If you aren't familiar with EV or summing problems, see part 1 first: [http://codeforces.com/blog/entry/62690]
(http://codeforces.com/blog/entry/62690).
I will stream a lecture on Monday at [14:00 CEST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=EV+lecture+2&iso=20181029T14&p1=262) — [https://www.youtube.com/watch?v=HDk6zQw0Rdo](https://www.youtube.com/watch?v=HDk6zQw0Rdo) (also [Twitch](https://www.twitch.tv/errichto)).
I will go through theory and problems from this blog.
### Expected Value theory, part 2
We roll a 6-sided die.
Remember, EV of square of the number of pips is something different than square of EV:
$$E(X^2) = \frac{1+4+9+16+25+36}{6} = 15.166666\ldots$$
$$E(X)^2 = (\frac{1+2+3+4+5+6}{6})^2 = 3.5^2 = 12.25$$
Two events are ...
### Bonus: powers technique
36.
Hybrid Tutorial #-1: Heavy-Light Decomposition **[Here](https://www.youtube.com/watch?v=_G_LMuLWMaI&list=PLDjGkpToBsYDx4GWu2u87sTqt6ICELz-T) is a playlist of all hybrid tutorials I've done.**
# "Intro"
_Timestamp: [00:00](https://youtu.be/_G_LMuLWMaI)_
Hi! Definitely not inspired by [this comment](https://codeforces.com/blog/entry/81086?#comment-675431), I've decided to try something that seems relatively novel — combining a blog and video tutorial into one, in a "hybrid" fashion. Both should be usable independently, but they will have the same "flow" and structure so you can reference both for concepts that are harder to grasp, and the two will supplement each other. The goal of these is to be **complete** — beneficial for both video and blog lovers, as well as full of enough information that anyone without much of an idea of what the concept is should be able to fully understand. There will be code as well, however, I very highly recommend not looking at it, but rather working out the implementation for yours...
37.
Shallowest Decomposition Tree Hi Codeforces!
Today I want to tell you about a really cool and relatively unknown technique that is reminiscent of Centroid decomposition, but at the same time is also completely different.
The most common and well known decomposition tree algorithm out there is the centroid decomposition algorithm (running in $O(n \log n)$). It is a standard algorithm that is commonly used to solve tons of different kind of divide and conquer problems on trees. However, it turns out that there exists another closely related decomposition tree algorithm, that is in a sense optimal, and can be implemented to run in $O(n)$ time in around $30$ lines of code. I have chosen to call it the _Shallowest Decomposition Tree_. This blog will be all about the shallowest decomposition tree. Something I want to remark on before we start is that I did not invent this. However, very few people know about it. So I decided to make this blog in order to teach people about this super cool and relatively unknown tec...
Today I want to tell you about a really cool and relatively unknown technique
that is reminiscent
38.
Problem Topics Good Day to you!
I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now — so here it is:
<spoiler summary="aho">
http://www.spoj.com/problems/ADAJOBS/
URI 2226 (5) //[NICE][NUMBERS][DP]
http://www.spoj.com/problems/SUB_PROB/en/
http://codeforces.com/contest/696/problem/D 8
http://www.spoj.com/problems/AHOCUR/ 5 //Aho-Corassic + DP
https://www.codechef.com/problems/LYRC (5) //Sample aho-brute-force
http://codeforces.com/problemset/problem/346/B //Proposed by [user:bradyawn,2019-08-03]
</spoiler>
<spoiler summary="automat">
6861 [LA] //CYK
UVA 10679 //Suffix Automat
http://www.spoj.com/problems/STRMATCH/ //Suffix Automat — trie might do too
http://www.spoj.com/problems/NSUBST...
10888 UVA (4) //VERY NICE — but not main technique ... ++ DP /or/ MCMF
39.
Dynamic Programming Optimizations Several recent problems on Codeforces concerned dynamic programming optimization techniques.
The following table summarizes methods known to me.
<table>
<tr>
<th>Name</th>
<th>Original Recurrence</th>
<th>Sufficient Condition of Applicability</th>
<th>Original Complexity</th>
<th>Optimized Complexity</th>
<th>Links</th>
</tr>
<tr>
<td><small>Convex Hull Optimization1</small></td>
<td nowrap><small>$dp[i] = min_{j<i}\{dp[j]+b[j] \star a[i]\}$</small></td>
<td nowrap>$b[j] \geq b[j+1]$<br/><small><s>optionally</s> $a[i] \leq a[i+1]$</small></td>
<td nowrap>$O(n^2)$</td>
<td nowrap>$O(n)$</td>
<td nowrap><small>[1](https://web.archive.org/web/20181030143808/http://wcipeg.com/wiki/Convex_hull_trick) [2](https://cp-algorithms.com/geometry/convex_hull_trick.html) [3](https://codeforces.com/blog/entry/63823)<br/>[p1](/contest/319/problem/C)</small></td>
</tr>
<tr>
<td><small>Convex Hull Optimization2</small></td>
<td nowrap><small>$dp[i][j] = min_{k<j}{dp[i-1][k]+b...
40.
[Tutorial] Knapsack, Subset Sum and the (max,+) Convolution I would like to thank:
- [user:tfg,2022-01-04] for his helpful discussions, digging through papers and implementing SMAWK.
- [user:maomao90,2022-01-04] for proofreading.
## Prerequisites
Let us first define the classical knapsack, unbounded knapsack and subset sum problems.
#### Knapsack
There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized.
#### Unbounded Knapsack
There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a **multiset** $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized.
#### Subset Sum
There are $N$ items. The $i$-th item has weight $w_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i = C$.
You should know how to do both versions of knapsack in $O(NC)$ and subset sum in $O(\frac{NC}{32})$ before reading this blog.
In this blog post, I will just show...
The paper also mentions a way to generalize this technique to knapsack where
weights are bounded by
41.
Efficient and easy segment trees This is my first attempt at writing something useful, so your suggestions are welcome.
Most participants of programming contests are familiar with segment trees to some degree, especially having read this articles http://codeforces.com/blog/entry/15890, http://e-maxx.ru/algo/segment_tree (Russian only). If you're not — don't go there yet. I advise to read them after this article for the sake of examples, and to compare implementations and choose the one you like more (will be kinda obvious).
Segment tree with single element modifications
==================
Let's start with a brief explanation of segment trees. They are used when we have an array, perform some changes and queries on continuous segments. In the first example we'll consider 2 operations:
1. modify one element in the array;
2. find the sum of elements on some segment.
[cut]
.
### Perfect binary tree
I like to visualize a segment tree in the following way: [image link](http://i.imgur.com/GGBmcEP....
Lazy propagation ================== Next we'll describe a technique to perform
both range queries
42.
Editorial of Codeforces Round #701 (Div. 2) [problem:1485A]
Author: [user:TheScrasse,2021-02-07]<br>
Preparation: [user:MyK_00L,2021-02-07]
<spoiler summary="Hint 1">
Suppose that you can use $x$ operations of type $1$ and $y$ operations of type $2$. Try to reorder the operations in such a way that $a$ becomes the minimum possible.
</spoiler>
<spoiler summary="Hint 2">
You should use operations of type $2$ first, then moves of type $1$. How many operations do you need in the worst case? ($a = 10^9$, $b = 1$)
</spoiler>
<spoiler summary="Hint 3">
You need at most $30$ operations. Iterate over the number of operations of type $2$.
</spoiler>
<spoiler summary="Solution">
Notice how it is never better to increase $b$ after dividing ($\lfloor \frac{a}{b+1} \rfloor \le \lfloor \frac{a}{b} \rfloor$).
So we can try to increase $b$ to a certain value and then divide $a$ by $b$ until it is $0$.
Being careful as not to do this with $b<2$, the number of times we divide is going to be $O(\log a)$.
In particular, i...
and they can be handled in $O(n\log n)$ with ["Venice technique
"](https://codeforces.com/blog/entry
Tutorial of Codeforces Round 701 (Div. 2)
43.
Osijek Competitive Programming Camp 2023 winter — wrap Hi everyone!
<center><a href="https://ocpc.mathos.unios.hr"><img src="https://ocpc.mathos.unios.hr/images/ocpc.svg" height="100px"></a></center>
<center>
<b>Sponsored by</b><br>
<a href="https://www.janestreet.com/join-jane-street/open-roles/?type=students-and-new-grads&location=london">
<img src="/predownloaded/ee/f2/eef26616a3661c658d1545f18ed21fabb14d5871.svg" height="50px" style="margin: 5px 5px 5px 5px;">
</a>
<a href="https://www.think-cell.com/osijek2023"><img src="/predownloaded/97/88/97887beeb75a4601259414b36ecee0160c29d027.svg" height="40px" style="margin: 5px 5px 5px 5px;"></a>
<a href="https://pinely.com/">
<img src="/predownloaded/0a/0f/0a0f3f67435d1f6e467bc7203d4a2090ba8f92cc.svg" height="50px" style="margin: 5px 5px 5px 5px;">
</a>
</center>
The [Osijek competitive programming camp](https://ocpc.mathos.unios.hr) (also see the [announcement](https://codeforces.com/blog/entry/110945) on Codeforces) just concluded last Sunday, on February 26, and I'd lik...
44.
Codeforces Global Round 13 Editorial [problem:1491A]
------------------
Setter: [user:syksykCCC,2021-02-28]
Prepared by: [user:syksykCCC,2021-02-28]
<spoiler summary="Hint 1">
How can we find the largest $k$ such that the $k$-th smallest element of the array is $0$?
</spoiler>
<spoiler summary="Hint 2">
How can we maintain $k$?
</spoiler>
<spoiler summary="Solution">
Let's define $cnt$ to represent the number of 1s in the array.
For the modifications, if $a_i$ is already $1$ now, then we let $cnt \gets cnt - 1$. Otherwise, let $cnt \gets cnt + 1$.
For the querys, just compare $cnt$ with $k$. If $cnt \ge k$, the answer will be $1$. Otherwise, the answer will be $0$.
The complexity : $O(n + q)$.
</spoiler>
<spoiler summary="Code (C++)">
```c++
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, q, a[N], cnt;
int main()
{
scanf("%d%d",&n,&q);
for(int i = 1; i <= n; ++i)
{
scanf("%d",a+i);
cnt += a[i];
}
while(q--)
{
int opt, x;
...
It seems this problem needs some random technique, but here is a
Tutorial of Codeforces Global Round 13
45.
Mo's Algorithm on Trees [Tutorial] Introduction
------------
Mo's Algorithm has become pretty popular in the past few years and is now considered as a pretty standard technique in the world of Competitive Programming. This blog will describe a method to generalize Mo's algorithm to maintain information about paths between nodes in a tree.
Prerequisites
-------------
Mo's Algorithm — If you do not know this yet, read this amazing [article](http://blog.anudeep2011.com/mos-algorithm/) before continuing with this blog.
Preorder Traversal or DFS Order of the Tree.
Problem 1 — Handling Subtree Queries
------------------------------------------
Consider the following problem. You will be given a rooted Tree $T$ of $N$ nodes where each node is associated with a value $A[node]$. You need to handle $Q$ queries, each comprising one integer $u$. In each query you must report the number of distinct values in the subtree rooted at $u$. In other words, if you store all the values in the subtree rooted...
[user:sidhant,2016-02-20] for helping me understand this technique., standard technique in the world of Competitive Programming. This blog will
describe a method to
46.
On Multidimensional Range Queries The following question is frequently asked in Codeforces ([46390](https://codeforces.com/blog/entry/46390), [45157](https://codeforces.com/blog/entry/45157), [11324](https://codeforces.com/blog/entry/11324)): _Is there a 2D segment tree that supports range addition and range minimum?_ In this blog post I give evidence that such a data structure does not exist, or if it did exist it would not generalize to higher dimensions. In particular I show that if for all $d$ a $d$-dimensional data structure that performs such queries in $O(polylog(N))$ time did exist, then the [exponential time hypothesis](https://en.wikipedia.org/wiki/Exponential_time_hypothesis) would fail. Such a data structure exists for range addition and range sum, so this is a non-trivial claim separating the hardness of these problems.
## Update 2021:
A paper " Algorithms and Hardness for Multidimensional Range Updates and Queries" in ITCS 2021 by Joshua Lau and Angus Ritossa ([https://arxiv.org/abs/2101.02003](https:...
47.
On the mathematics behind rolling hashes and anti-hash tests This blog assumes the reader is familiar with the basic concept of rolling hashes.
There are some math-heavy parts, but one can get most of the ideas without understanding every detail.
The main focus of this blog is on how to choose the rolling-hash parameters to avoid getting hacked
and on how to hack codes with poorly chosen parameters.
# Designing hard-to-hack rolling hashes
## Recap on rolling hashes and collisions
Recall that a rolling hash has two parameters $(p, a)$ where $p$ is the modulo and $0 \leq a < p$ the base.
(We'll see that $p$ should be a big prime and $a$ larger than the size $\left|\Sigma\right|$ of the alphabet.)
The hash value of a string $S = s_0 \dots s_{n-1}$ is given by
$$
h(S) := \left(\sum\limits_{i=0}^{n-1} a^{n-1-i} s_i\right) \mod p
$$
For now, lets consider the simple problem of: given two strings $S, T$ of equal length,
decide whether they're equal by comparing their hash values $h(S), h(T)$. Our algorithm declares $S$ and $T$
t...
##### Credit for this part goes to [user:ifsmirnov,2018-07-05], I found this
technique in his
48.
A Rerooting Technique Application $$~-\text{In the name of God}~-$$
Hi
I saw my contribution going down so I decided to write a decent blog, explaining super advanced stuff, funny enough, I don't have the knowledge nor have the patience to write such a blog, so I wrote this blog explaining some applications of Rerooting Technique. But I was tired and lazy so here is a not quite usable nor perfect blog for whoever likes the Rerooting Technique(me for instance).
Note that RT stands for Rerooting Technique, DP stands for Dynamic Programming, RHS stands for Right Hand Side of an equation, LHS stands for Left Hand Side of an equation. (I assumed the reader is familiar with basics of math, trees, DFS and BFS)
Also I recommend reading my previous blog $\texttt{before}$ reading the rest of this blog:
[Online Query Based Rerooting Technique](https://codeforces.com/blog/entry/76150)
I recently solved the following problem for second or third time (which I believe is a very classic problem):
Given a tree, cal...
A Rerooting Technique Application, [Online Query Based Rerooting Technique
](https://codeforces.com/blog/entry/76150)
49.
[Tutorial] Generalized Möbius Inversion on Posets This blog will be more about developing ideas about certain structures rather than actually coding up stuff. The ideas we'll be developing here have many applications, some of which involve:
- Number Theoretic Möbius Inversion
- Principle of Inclusion-Exclusion
- Directed Acylic Graphs
- Subset Sum Convolution
- Finite Difference Calculus (and prefix sums)
Note that some of the terminology used below might be non-standard. Also, some parts of the blog make a reference to abstract algebra without much explanation; such parts are just for people who know some algebra, and can safely be skipped by those who don't know those concepts at all.
Prerequisites:
- Some knowledge about graphs.
- Matrix multiplication
- Basic combinatorics
## Definition of a poset and some intuition
All of these have one thing in common: they have an underlying "poset". Let's understand what a poset is.
Rigorously speaking, a poset is a partially ordered set, i.e., a set $S$ equipped wit...
intent behind this was to introduce a very standard technique in combinatorics
that people don't
50.
[Tutorial] Theoretically Faster HLD and Centroid Decomposition This blog was going to be translation of $[1]$ (which is in Chinese) but I think I ended up deviating too much from the source material that it would not be appropriate to call this a translation. Anyways, I am honestly amazed by how ahead of its time this paper is. In its abstract, it starts by saying that the state of art for tree path queries is $O(n \log n + q \sqrt n \log n)$, which I honestly can't fathom how one would arrive, then proceeds to claim that it has found an $O((n+q) \log n)$ algorithm. All the more, in 2007.
While I was in the process of writing this blog, [user:smax,2022-07-18] sniped me and posted $[9]$. However, we will focus on static trees **only**.
Thanks to [user:oolimry,2022-07-18], [user:everule,2022-07-18] and [user:timreizin,2022-07-18] for proofreading.
Note to reader: I am expecting the reader to be familiar with what a splay tree and HLD is. You do not really need to know why splay trees are $O(\log n)$ amortised but you should know what the z...
centroid decomposition problems. Thanks to [user:balbit,2022-07-18] for
telling me about thistechnique.
51.
How to composite (some) polynomials faster? Hi everyone, today I'd like to elaborate something more on the [problem I](https://codeforces.com/contest/1930/problem/I) on the recently ended div 1 contest.
As described in the [official solution](https://codeforces.com/blog/satyam343), a bottleneck of the problem is the following: Given a sequence
$\{c_j\}_{-n \leq j \leq n}$, compute
$$ g_k = \sum_{-k\leq j\leq k} ([x^j] (x + 1/x)^k) c_j $$
for all $0 \leq k \leq n$.
In the official solution, an $O(n\log^2 n)$ time algorithm is presented, and we also claimed that it is possible to compute $g_k$ in $O(n\log n)$ time. In this post, I'd like to elaborate on how to do that.
By the way, another bottleneck of the problem is the relaxed convolution problem, where the usual implementation also takes $O(n\log^2 n)$ time. I mentioned in [comment](https://codeforces.com/blog/entry/111399#comment-996712) that the relaxed convolution has a somehow practical solution that has time complexity
$$ O\left(\frac{n\log^2 n}{\log \log n...
Discussion of think-cell Round 1
52.
An Introduction to Plug DP So I realized that there are literally 0 resources written in English on Plug DP, which is one of my favourite DP tricks/techniques that I know of so far. Thus, I hope this serves as a soft introduction for English speakers to this technique, and maybe sheds some light on how powerful it can be. Before we start, I would recommend having a solid understanding of bitmask DP in general in order to get the most out of this blog. Now, let's begin.
### What is Plug DP?
In short, Plug DP is a bitmasking technique that allows us to solve complicated problems with relatively simple states and transitions. To illustrate Plug DP in its most primitive form, let's visit a rather classical problem: **How many ways can we fully tile an $N \times M$ grid with $1 \times 2$ dominoes?**
This problem can be solved with a standard row-by-row bitmasking approach, but the transitions for that DP state is annoying and unclear at best. Instead, let's investigate an approach that uses a slightly differ...
introduction for English speakers to this technique, and maybe sheds some
light on how powerful it can be
53.
XOR Hashing [TUTORIAL] This is a well known technique, but I couldn't find almost any detailed tutorial, so I'll try to help with this one.
####Motivational Problem:
You have an array $A$ and $Q$ queries, which are, say if the subarray from $l$ to $r$, ($A[l]$, $A[l+1]$, $...$, $A[r]$) forms a permutation.
####Some basic observations:
Only the set of elements matters, the order is irrelevant.
You want to know if each element is exactly once.
####Solution:
Assign a random number $randval[i]$ to each number $i$, now we can say that if the XOR of the subarray ( $randval[A[l]]$ xor $randval[A[l+1]]$ xor $...$ xor $randval[A[r]]$ ) is equal to the xor of any permutation of size $r - l + 1$ (for example $1$, $2$, $3$, ... ,$r-l+1$, which hash is $randval[1]$ xor $randval[2]$ xor $...$ xor $randval[r-l+1]$ ) the subarray is a permutation.
####Some Insights:
With the XOR we have some issues, we are counting if the number of occurrences of each element is even or odd, not the real number o...
####More problems using this technique (in no particular order of difficulty):
54.
CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) Editorial We apologize for the technical difficulties in Task B. We hope you enjoyed the rest of the contest. We will add hints soon.
[problem:1870A]
<spoiler summary="Tutorial">
Note that if $min(n, x+1) < k$, then the answer is $-1$.
Otherwise, there are two cases:
- If $k=x$, then the suitable array looks like $[0, 1, 2, \dots, k-1, \dots, k-1]$.
- If $k \ne x$, then the suitable array looks like $[0, 1, 2, \dots, k-1, x, \dots, x]$.
In both cases, we can construct the array and calculate its sum in linear time. The overall complexity is $O(n \cdot t)$.
</spoiler>
[problem:1870B]
<spoiler summary="Tutorial">
Note that after performing the operation on $b_j$, which has some bit set to 1, this bit will become 1 for all numbers in $a$ (and will remain so, as a bit cannot change from 1 to 0 in the result of an OR operation). If $n$ is even, then in the final XOR, this bit will become 0, as it will be equal to the XOR of an even number of ones. If $n$ is odd, then ...
55.
Every Technique and Algorithm I Used to Become Grandmaster Hi everyone, I became grandmaster today so I decided to go down memory lane and review every problem I have ever done in a CodeForces contest to look back and see every technique and algorithm I had to use to become a grandmaster. I am not sure how useful this is, I mostly think it's fun to look at all the old solutions I wrote and how different it was from how I write code now. The main takeaway is that, as many people have said before, you don't need to know or memorize a bunch of advanced algorithms to become grandmaster. As you will see, there are many problems where I just used "ad hoc reasoning," meaning there's not a standard technique I used to solve the problem and you just need to make some clever mathematical observations to solve the problem. Also, there are many popular algorithms that I have never needed in a CodeForces contest despite being a grandmaster:
- Sparse tables, Fenwick trees, and segment trees
- String algos, like rolling hashes, Knuth-Morris-Pratt, suffix...
Every Technique and Algorithm I Used to Become Grandmaster, problem I have ever done in a CodeForces contest to look back and see every
technique and algorithm I had
56.
First time becoming red In yesterday's contest [contest:1815] I've got the achievement which I could not imagine just half a year ago — reach 2400 rating and become GM.
The first time I learned about CF was on 2022.2, that time I registered this account and took my first contest. But my first submission [submission:146390589] on contest got TLE, and I solved 0 problem in this contest. (At that time I didn't know that's because the efficiency of `java.util.Scanner` is extremely low) And because I needed to deal with graduation thesis, I didn't use CF until the end of last year, when I restarted CF contest.
At 4th and 5th contests I solved div2D problems to reach blue. In my 9th contest, I first time solved div2E problem in contest, and I became purple in my 12th contest. In my 14th and 15th contest, I solved div2E problems twice and became orange. In the next weeks, I started to hit the upper limit of my skill, and dropped from orange twice.
In order to improve my skill of competive programming...
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Apr/24/2024 00:38:07 (l1).
Desktop version, switch to mobile version.
Supported by
