Top Recent Blog Posts
By Just_Josh, history, 36 hours ago,

Drop a comment under this post, stating the different categories of programmers on codeforces. Here, I'll start:

1. The ones who solve problems
2. The ones who build mobile and web apps for group 1.
3. The ones who post blogs about cheaters xD
4. The ones who ask how to become red on codeforces
5. The one posts a blog about types of coders on codeforces

Continue the list

P.S. This is just for fun, don't take it too seriously :)

• +159

By Melonade, history, 25 hours ago,
Always remember, never forget

Erm, so...

Today for me starts like any other day, I woke up, ate breakfast, and visited Codeforces for fun. To be honest I didn't compete in any contests for a while, as I have a lot of exams and studying online.

I'm pretty bored so I scrolled down randomly, and I found something that hit me, like a truck.

One of the highest-rated and most respected Codeforces users in my country, Kuroni, left the Codeforces community.

I checked his profile, and he left it with nothing but a blank in his profile picture, and a line below his nickname that says "Goodbye". That's it, nothing else.

I was completely shocked. I even cried for around half an hour. I mean, anyone that has a big contribution to this community (and high-rated as well), and decides to retire, hurts. You may think that this is hurt as anyone else farewelled before, and I feel ok with it.

But for me, it hits different.

He is my personal favorite coder. Kuroni was my idol, since the first days I entered Codeforces.

I still remember back then, on my first day ever at Codeforces, with my curiosity I checked the highest rated users in Viet Nam. Well, it is now Maripium, but on that day, it was him. Kuroni.

Since then, I had a dream. A dream to practice with my own heart, to be a red coder like him one day. Across my journey on CP, he inspires me a lot. Every time I was feeling down, I checked his profile and have the motivation to continue. Seems pretty weird, but without him, I am not very sure that I would be blue right now.

Long story short, although this will be really hard for me to come through, life must continue. But for now, I will sit back and take this as a new step in my life. From now, I will train harder than ever, trying my best to one day, at least one day, fulfill my dream.

I don't think I could say anything more about this topic, so everything I can say is: farewell, thank you, and best of luck to Kuroni for whatever you choose to have a brighter future. I hope that when you come back here, you can know that at least this community doesn't forget and always welcome you with open hands.

Any thoughts are welcome. Sorry for my bad English.

Kuroni orz

• +309

By neko_nyaaaaaaaaaaaaaaaaa, 39 hours ago,

See current IOI ranking here

• +240

By eduardische, history, 38 hours ago,

• +96

By flamestorm, 33 hours ago,

Thank you for competing! I hope you had fun in the contest. UPD: Implementations have been added.

103150A - Addition Range Queries

Short Solution
Editorial
Implementation

103150B - Arrowing Process

Short Solution
Editorial
Implementation

103150C - EZPC Sort

Short Solution
Editorial
Implementation

103150D - Moving Points

Short Solution
Editorial
Implementation

103150E - o

Short Solution
Editorial
Implementation

103150F - Palindromicity

Short Solution
Editorial
Implementation

103150G - Segmentation Fault

Short Solution
Editorial
Author's Note
Implementation

103150H - William Tell

Short Solution
Editorial
Implementation

103150I - X-OR XOR

Short Solution
Editorial
Implementation

• +82

By ch_egor, 6 days ago, translation,

Thanks for the participation!

1539A - Contest Start was authored and prepared by grphil

1539B - Love Song was authored by jury and prepared by _tryhard

1539C - Stable Groups was authored by Artyom123 and prepared by Artyom123 and shishin

1539D - PriceFixed was authored by Helen Andreeva and prepared by Siberian

1539E - Game with Cards was authored and prepared by TeaTime

1539F - Strange Array was authored and prepared by Tikhon228

• +70

By aryanc403, 11 hours ago,

Update 1 -
Let's consider this problem -
We have a function subset_convolution(A,B) it gives us Subset Sum Convolution of two sets $A, B$.
Let's say we array $A$ with $A[0]=1$ and we want to find A^K defined as $A$ convoluted with itself $K$ times.
A^2 = subset_convolution(A,A)
A^3 = subset_convolution(A^2,A)
...
A^k = subset_convolution(A^{k-1},A)
The best I can think right now is using something on lines of fast exponential to achieve $O(log K*N^2*2^N)$ time where $2^N$ is the size of A.
But it can be done in $O(N^2*2^N)$ using tricks well known at some places. Idk why it works tho.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

TLDR — Just me rambling about the old ARC problem I was solving for the last 3 days. Something "set power series" similar to "power series for polynomials" I came across and I have an iota idea about it right now. Also amplifying some unanswered bugaboo related to it in the discussion of that ARC round. Spoiler is just very very briefly mention different solutions I had for ARC105F problem.

Me trying to solve ARC105 F

The logarithm of 'set power series' is a function $g(x)=\sum_{S} g_{S} x^{S}$ such that $f(x) = \sum_{S} (\sum_{\mathcal{P}} \prod_{P_i \in \mathcal{P}} g_{P_i}) x^{S}$, where the inner summation goes over all unordered partitions $P$ of $S$.

dario2994 submission on the same problem implements a small library for subsets with functions namely and/or/xor/subset convolutions along with log and exp of set power series.
(First to answer dario2994 comment — Yes, there does exist a clever way (and maroonrk's submission) to compute subset convolution.)

I did asked some of my friends and seniors doing MATH major — where can I read formal definitions of "set power series" since googling it just gave me useless results and none of them ever heard it.

Q1 — What exactly is the definition of exp of set power series? (One implemented by dario2994 and mentioned by mmaxio). Where can I read about more similar definitions?

mmaxio mentions Lu Kaifeng's report, googling about his report along with keywords such as "set power series" doesn't yield helpful results. But then I came across this blog. It has a code snippet and mentions For details, please refer to the 2015 Proceedings of the National Training Team Lu Kaifeng, "The Properties and Application of Set Power Series and Its Fast Algorithm".

It's a 17 page report published in 2015 in Chinese, I wasn't able to find an English version. Hence must be a well-known problem in China and hence a "trivial solution" by Elegia. I tried auto translating it using the method mentioned by z4120 in Auto-translated Chinese national IOI training team report papers but I messed up a step somewhere and ended up with just Chinese translated into Chinese, would really appreciate it if someone can translate it for me.

Q2 — mmaxio's comment looks like you can apply any function to the set power series by applying it to a "ranked" vector for each mask independently makes me much more interested in this. It opens the door to a hell of a lot of possibilities here (a reason for this blog here) integration, derivative, inverse, square root to name some among similar operations on polynomials and series.

I do remember the day when I learnt about the inverse and square root of a polynomial and was overwhelmed by it. On that day, I just concluded that "polynomials are just numbers". Later I have seen some problems which even used dp states as polynomials instead of integers. The observation "polynomials are just numbers" makes it easy for me to understand those editorials and those problems do excite me these days. Something similar for sets will for sure generalize it further.

Publishing this blog with the expectation that I would find more material to read about it since Google isn't my friend here.

Update 1 (solution) —

O(N^2*2^N) solution of initial problem

• +63

By Leonardo16, history, 34 hours ago,

Hello, codeforces.
I think this technique is important, and easy to code, although I haven't found much about it, so I've decided to make a blog explaining it.This technique allows to compare substrings lexicographically in $O (1)$ with a preprocessing in $O (NlogN)$.
As this is my first post on codeforces, please let me know if there are any mistakes.

##### Prerequisites:
• Basic strings knowledge.
• Sparse Table(Optional).

## What is a Dictionary of Basic Factors?

As in the sparse table we will have a matrix of size $N\log{N}$ called $DFB$, where $DFB[i][j]$ tells us the position of the string $S[i ... i + 2^j-1]$ (the first time it appears) among all the strings of size $2^j$ ordered lexicographically.

So, how do we build the matrix? Let's start with the lowest level, for powers of size $2^0$, we simply put the position of the character $S[i]$ in the dictionary (1 for 'A', 2 for 'B' ... and so on).

For the following $DFB[i][j]$ we can save a pair of numbers that are $(DFB[i][j-1], DFB[i+2^{j-1}][j-1])$

Now we replace the pairs by their position (the first time the pair appears) on the ordered array of those pairs. This can be done with Counting Sort in $O(N)$, otherwise with a normal sort in $O(NlogN)$ (But this will slow down the algorithm).

We do that for all powers of two and we will have the complete matrix.

##### Handling queries:

Suppose we want to make a query that is "Say which of the two substrings $S[l_{1}...r_{1}]$ and $S[l_{2}...r_{2}]$ is smaller lexicographically?".
First of all, let's analyze that if the substrings have different sizes, we can compare only the prefixes of size $M$ where $M$ is the minimum size between the two substrings, if both prefixes are equal then the smallest lexicographically is the substring of smaller size.
As in the Sparse Table, suppose $k = \ log {(r-l)}$, then we can represent the substring $S [l ... r]$ as the pair $( DBF [l] [k], DFB [r-2^k+1] [k] )$. Now to compare two substrings of equal size we simply lexicographically compare their pairs in $O(1)$.
For example, suppose we have the string "ABACABA" and we want to know which string is lexicographically smaller between $S [0 ... 5]$ and $S [1 ... 6]$ ("ABACAB" and "BACABA").Since $\log{(5-0)}=2$, the pairs to compare would be: $(DBF [0] [2], DBF [2] [2])$ and $(DBF [1] [2], DBF [3] [2])$, which would be $(1,2)$ and $(2,4)$ therefore the first substring is lexicographically smaller.

## Proof:

Since we have that $DBF [i] [j]$ is the position of $S [i ... i + 2 ^ j + 1]$ between all substrings of size $2 ^ j$. If we want to compare two substrings, which would be represented as pairs, and we compare the first element in the pairs, we are comparing prefixes of size $2 ^ k$ of the substrings (where $k$ is the logarithm of the size of the substring). If they are the same, we compare the second elements of the pairs, which would be the same as comparing suffixes of size $2 ^ k$ of the substrings.

Thanks for reading, I hope this article will be useful. Any questions or suggestions let me know in the comments.

• +97

By me123456, 4 days ago,

A lot of people in today's contest have copied code from various sources. A youtube channel was continously posting solutions during the contest. He posted A,B,C,D solutions within the first hour of the contest.

Numerous people copied code from here and made slight changes into the code and submitted and got AC. I request you to get this channel banned as soon as possible and take whatever action is required so that codeforces ratings do not loose credibility.

These channels distribute solutions during live contest and even the people who cannot solve A end up solving 3 to 4 problems. So it's better if these channels are banned asap else there is no point in giving these contests when someone can cheat and easily get a better rank than you.

• +163

By flamestorm, 5 days ago,

### Hello, Codeforces!

I would like to invite you all to my first contest, EZ Programming Contest #1. It will be held on Jun/23/2021 18:35 (Moscow time). The round is not rated for anybody, since it is an unofficial contest.

The contest has $n$ problems, where $n$ is an integer satisfying $7 \leq n \leq 11$. You will have 2 hours and 30 minutes to solve the problems. The problems are meant to be about Div. 2 A, B, and C level, and they will not be sorted in order of difficulty. So, you can think of the problemset like if ICPC only went up to Div. 2 C.

A huge thanks to my testers wabadabakalakaboo, manish.17, and fishy15!

I know you all are filled with questions, so I'll try to answer them all now.

• Q: Is it rated?
• A: No.
• Q: Why did you write this contest?
• A: I have a lot of ideas for easy Div. 2 A, B, and C level problems, not all of which can get into a contest. I thought it would be fun to compile them all into one contest anyways, and hey, it might actually be good practice for beginners or just anyone who wants to practice solving these types of problems quickly!
• Q: Why didn't you propose the problems to other platforms?
• A: uuuuuuhhhhhh idk. I just thought it would be fun to give these problems to Codeforces, since that's where I do most of my competitive programming :P.
• Q: Do you think this will be good practice for beginners?
• A: Yeah! It's a long-form contest (2.5 hours), but I think all the problems are approachable by beginners.
• Q: Is there anything unusual about the format of the contest?
• A: The round is ICPC-style. I wanted to make it like ICPC but for early Div. 2 problems. This means that the problems won't be sorted in order of difficulty. So, I encourage you to read all the problems ;).
• Q: Is it rated?
• A: No.

Thank you all for reading this far. Good luck, have fun, and I hope to see you on the scoreboard!

UPD1: The editorial is out!

UPD2: Also, like most contests, I want to congratulate the winners, so here they are:

Overall winners (individual):

Div. 2 winners (individual):

Team winners:

1. Absalom: paramk, klexis, _webhub_

2. Sh00nya bata Sh00nya: dadboss, mexomerf, Athem

3. LeanMeanFightingMachines: Kabir, VAICR7BHAV, ProfessorChaos

4. Time Limit Defeated: Blitztage, a_manglani, suneet27

5. Bugged House: MvKaio, naniim

Thank you all so much for participating, and I hope to see you again soon!