Hello Codeforces!

flamestorm, mesanu and I want to invite you to Codeforces Round 964 (Div. 4).

It starts on Aug/06/2024 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

• 5-8 tasks;
• ICPC rules with a penalty of 10 minutes for an incorrect submission;
• 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
• after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
• by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

Additionally, there might be problems that are interactive, so please read the guide of interactive problems before the contest.

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behaviour. To qualify as a trusted participant of the fourth division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them),
• do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to the testers: Dominater069, Qualified, Vladosiya, qwexd, Gheal, cry, haochenkang.

We suggest reading all of the problems and hope you will find them interesting!

Good Luck!

UPD: Editorial is out!

Happy Holidays Codeforces! 🎅

mesanu, flamestorm and I are very excited to invite you to Codeforces Round 918 (Div. 4)! It starts on Dec/28/2023 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

• 5-8 tasks;
• ICPC rules with a penalty of 10 minutes for an incorrect submission;
• 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
• after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
• by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them),
• do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Special thanks to the VIP testers: AlperenT, KrowSavcik!

Thanks a lot to the testers: Qualified, Kaushal_26, htetgm, MADE_IN_HEAVEN, sandry24, hbarp, Vladosiya, LucaLucaM, Gheal, tvladm, Dominater069, haochenkang, xiaowuc1, pashka, vrintle, BucketPotato!

And many thanks to Vladosiya for translating the statements!

We suggest reading all of the problems and hope you will find them interesting!

🎄 🎄 🎄 Good luck to everyone and enjoy the holidays!!! 🎄 🎄 🎄

Hello Codeforces!

We are looking for problems for the European Girls' Olympiad in Informatics (EGOI) 2024. The contest will be held in Eindhoven, The Netherlands, 21-27 July 2024. The submission deadline is Sunday, 14 January 2024.

Details about the problem proposal process can also be found here.

We will be pleased to invite the authors of the selected problems to the contest. The authors are responsible for arranging their travel, but the costs for their stay will be covered by EGOI.

We are looking forward to seeing your creative problems!

EGOI 2024 Scientific Committee

Hello Codeforces!

mesanu, flamestorm and I are very excited to invite you to Codeforces Round 886 (Div. 4)! It starts on Jul/21/2023 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

• 5-8 tasks;
• ICPC rules with a penalty of 10 minutes for an incorrect submission;
• 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
• after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
• by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them),
• do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to all testers: MikeMirzayanov, erekle, Bakry, Dominater069, Gheal, andrei_boaca, zwezdinv, sam571128, Sho, Wibo, Phantom_Performer, moonpie24, mafailure, Kalashnikov, SashaT9, Qualified, haochenkang, ZiadEl-Gafy, MADE_IN_HEAVEN, AdOjis485, qwexd, mkisic, Killever, sabbir-hasan-anik, peshkoff, donghoony!

And thanks to Vladosiya for translating the statements!

We suggest reading all of the problems and hope you will find them interesting!

Good Luck to everyone!

UPD: Editorial is out!

Hey, hi Codeforces!

It's mesanu, flamestorm and me and we are very excited to invite you to Codeforces Round 871 (Div. 4)! It starts on May/06/2023 17:35 (Moscow time).

We worked swiftly to tailor the problems for this contest, so we hope you will enjoy them! We tried to make the statements short, epic and concise.

The format of the event will be identical to Div. 3 rounds:

• 5-8 tasks;
• ICPC rules with a penalty of 10 minutes for an incorrect submission;
• 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
• after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
• by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them),
• do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to all testers: RedstoneGamer22, tibinyte, sandry24, jampm, haochenkang, qwexd, Vladosiya, _Vanilla_, Phantom_Performer, ScarletS, NintsiChkhaidze, keta_tsimakuridze, Dominater069, Gheal, Bakry!

And thanks to Vladosiya for russian statement translations!

We suggest reading all of the problems and hope you will find them interesting!

Good Luck and have fun!!

Are you ready for it?

UPD: Editorial is out!

Hello Codeforces!

mesanu, flamestorm and I are very excited to invite you to Codeforces Round 859 (Div. 4)! It starts on Mar/19/2023 17:55 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

• 5-8 tasks;
• ICPC rules with a penalty of 10 minutes for an incorrect submission;
• 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
• after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
• by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them),
• do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to all testers: jampm, Max_Calincu, KrowSavcik, TimaDegt, nyaruhodo, tibinyte, badlad, Phantom_Performer, AlperenT, Bakry, keta_tsimakuridze, Gheal, RedstoneGamer22, Dominater069!

And thanks to Alexdat2000 for translating the statements!

We suggest reading all of the problems and hope you will find them interesting!

Good Luck to everyone!

UPD: Editorial

Introduction

Rating is a great measure of skill and a nice way to observe progress by comparing yourself to your past self and seeing where you stand in the community. As great measure as it is, there are a lot of problems that come with it. They have nothing to do with how the rating system works but rather with how human beings function. In this blog post, I will talk about some of the most pressing personal problems that come up with rating and try to provide some advice on how to solve them, speaking from personal experience and from the experience of a lot of other people I know.

Associating self-worth to rating

This is, in my opinion, the most significant problem people face, and it also pretty much contains all the following problems as a subset. It's extremely easy to fall into this rabbit hole since, as a competitive programmer, it only feels natural to associate our rating with intelligence and, respectively, our intelligence with self-worth. Why is this such a big problem?

• First of all, any rating loss will feel horrible. Around a year ago, I faced the same problem, and after each rating loss, I would have a terrible mood for a few days and, well... feel like I was an idiot. I wouldn't even enjoy the things I used to like doing since I wanted to practice more in order to become smart again! So, I could spend entire weeks just practicing and feeling guilty about doing other things due to not being content with the color of some virtual points next to my name...

• Toxic motivation. Even though it did work as motivation to practice more, it reduced all joy I had in problem-solving, and, in the long run, such "motivation" is only hurtful. In order to really be good at something, we need to enjoy what we are doing and not be motivated by disliking who we are now.

• At some point, even the positive deltas start feeling horrible — "I got just +100, but if I got five more, I would have gotten a new rank! Why couldn't I have gotten the five extra points? Am I too stupid? Why was I so slow on the problems? If I moved a bit faster, I would have gotten the LIFE-CHANGING color!!!" I've been hearing complaints like this after almost every Codeforces round, and doesn't it sound terrible? You actually got the positive delta you wished so much for, and instead of celebrating it, you are complaining about not getting more. Then, what will bring you happiness? Even if you got a new rank, wouldn't you just wish for more after getting used to it? And how would losing it feel?

• Affecting one's confidence. When caring so much about rating, it's easy to feel very unconfident in your abilities after performing poorly in a contest. I also have several times stopped believing in myself after having some consecutive bad performances. But it can happen the other way too. When I first hit expert, I was incredibly happy. I felt like I was a god. Then, I went to school with the idea of showing off how great I was, expecting praise from everyone. Well, no one cared. I wasn't a god. I was the same guy I was yesterday for all my friends. And that's normal, isn't it? Well, for the 10th-grader me, it wasn't. It felt demotivating and made me devastated again, even though I’d actually achieved the long-awaited result.

• Thinking you don't deserve things — "Why are these great people even talking to me? I am just a specialist. Why do I have the respect of a grandmaster, and why do they take out their time in order to talk to me, no-one?". It can even get to this level!

It gets to the point where life gets just sad. It makes you lose the joy in your passion and, pretty much, in life.

Advice/Solution

Thinking about it, what did really change? Wasn't I the same person I was just a day ago, before the rating loss? Why was I smarter back then and stupid now? It really doesn't make sense. I could have only learned more by failing in a contest, so I really could have only improved since then. And why would people not talk to me if I were a specialist and not an LGM? Rating isn't the only thing that defines us, humans. We are much more than that.

But yet, even though we understand all this on a logical level, it's way easier said than done to get rid of this toxic mentality...

If you think you have such a mentality, you are already on the right track! The first step in solving any problem is identifying it! Now, here are my pieces of advice.

• The most important step is to start taking control of your own thoughts. Realize you are much more than your rank. Don't judge yourself solely based on your rating.

• Did you get a negative delta? That means you learned something new, you gained experience, you participated in a contest, and that's what you enjoy, isn’t it? It won't always go your way, and you should realize that. Additionally, the rating loss won't matter after attending a few more competitions. Stop self-deprecating after any rating loss, and stop treating rating as if it was the most important thing in the world. It isn't. No, getting your dream rank won't be the thing that will make you the happiest. It will, of course, feel good, but with such a toxic mentality, it won't last long.

• But, even though understanding this helps, it doesn't completely solve the problem, at least speaking from personal experience. As a competitive programmer, I surrounded myself with other competitive programmers, and most discussions were on competitive programming. Easy to start caring so much about your performances in competitive programming when it's all you talk and think about, right? It's important to balance your life. Find another activity that's not related to competitive programming at all that you simply enjoy doing, just for fun. Maybe you always wanted to learn how to play the piano or the guitar. Maybe you wanted to learn speed-cubing, get good at chess, or how to yo-yo. Maybe you have a book you always wanted to read and never got to it, or maybe you even want to start writing your own book. Just pick up anything, it will make you happy and a more interesting person to get to know.

• Speak with your friends about other topics. What was the last book they read? What's their favorite tv-series and movie? What do they think of the new song that dropped? Who did they support in the world-cup? Why do they support Ronaldo and not the actual team? Is this more boring to find out compared to what their last performance was in a contest?

• Get to know new people that don't even do competitive programming. What's the first question they ask you? I am sure it won't be what's your rating on Codeforces. You will realize no one really cares about what your rating is when talking in real life (even competitive programmers usually don't).

• Take a small break from competitive programming. It doesn't have to be long. Just go on a holiday for 1-2 days. Go camping with your friends, visit another city or country, or go to the cinema or a restaurant. There is so much that, if you are like how I used to be, you forgot existed in life. Try to remember them.

• Try changing the people around you. It can happen you have this toxic mindset because everyone in your circle also does.

Comparing yourself to others

This is another big problem that almost everyone faces. We are competitive programmers, so we compete. It only feels natural to compare ourselves to the ones around us, trying to become better than them. But, this again has quite a lot of negative side effects.

• Envy becomes a big issue in this case. One can't even feel happy for his friends' success due to getting overpassed in rating or noticing their progress was slower. It happens that it can even make relationships way tenser and way more distant and cold.

• It affects performance. One can't even focus on performing to the best of his abilities due to always worrying about how others are doing. During contests, one can spend more time checking the standings rather than actually solving the problems.

Advice/Solution

When you're trying to perform to the best of your abilities and don’t worry about what others might have solved, results are always better.

-A very wise person.

Just as the quote says, try not to care about others. Focus on yourself. Compare only to your past self. Where were you a year ago, and where are you now? What about two years ago? What about three? You most probably have come a very long way. By not comparing yourself with others, you are also more open to learning new things by collaborating. It's easier to work with others when you aren't jealous of them and don't focus on beating them, isn't it? Additionally, working with others makes learning a much more enjoyable, pleasant, and easier experience.

Being scared of losing rating

Of course, giving so much importance to rating will make one afraid of losing it. So, they will find a way to avoid this.

• Not participating in contests. I know of quite a lot of people who got their desired ranks and just quit participating in contests, but this is detrimental to their further improvement. Contests are a great way to practice in a competitive environment, learn to deal with the competition stress, learn about new topics and just have fun.

• Alting. Alting has pretty much all the downsides of not participating in contests. It's hard to treat contests seriously if it's not your main account on the line. (For legal reasons, this is a part where I am definitely not talking from personal experience).

• Cheating. There are people who actually start cheating in contests due to fear of rating loss, and this is the worst thing one can do. It ruins the whole point of participating in the competition and brings even more sadness and cheating in the future when they won't be able to match the skill of their rating.

Advice/Solution

Really, just change your attitude! Enjoy solving problems and participating in contests; rating will come on its own, and even if you lose it, it will be easier to gain it back in the next contest.

Chasing results

It may sound weird, but chasing results usually only affects the said results in a negative way. The practice will usually be inefficient due to focusing on the end result rather than on the process of actually getting better. Additionally, it will only bring negative emotions when one fails to achieve their desired results, and everyone fails sometimes...

Advice/Solution

Enjoy the process! Improving yourself should always be the main goal. Chasing only results means you will only be based on extrinsic motivation, but the strongest one that really helps one grow is the intrinsic one. You need to aim for getting better, not for getting better results. I already said this multiple times, but I think it's necessary for any competitive programmer: Enjoy problem-solving and competing and let the results come on their own.

Conclusion

These problems aren't merely rating or CP-related. They’re pretty common in any sport. And the process of overcoming the toxic mindset that comes with them isn't easy, but it's necessary for further growth and for living a happy life, in my opinion. Just try working on yourself, making small steps every day, and one day you will realize this mindset was just in the past.

Thanks to keta_tsimakuridze for helping proofread the blog and useful suggestions!

Hello Codeforces!

mesanu, flamestorm, MikeMirzayanov and I are glad to invite you to Codeforces Round 835 (Div. 4)! It starts on Nov/21/2022 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

• 5-8 tasks;
• ICPC rules with a penalty of 10 minutes for an incorrect submission;
• 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
• after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
• by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them),
• do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

We would like to thank:

• RedstoneGamer22, tibinyte, haochenkang, badlad, qwexd, nyaruhodo, Phantom_Performer, tolbi, AlperenT, Bakry, prvocislo, Gheal, keta_tsimakuridze, KrowSavcik, BucketPotato, pashka, MikeMirzayanov for testing the round!

• Max_Calincu, TimDee, MikeMirzayanov for helping with Russian translations!

We suggest reading all of the problems and hope you will find them interesting!

Good luck!

UPD: Editorial is posted.

Hello Codeforces!

mesanu, flamestorm, MikeMirzayanov and I are glad to invite you to Codeforces Round 827 (Div. 4)! It starts on Oct/13/2022 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

• 5-8 tasks;
• ICPC rules with a penalty of 10 minutes for an incorrect submission;
• 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
• after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
• by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them),
• do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

We would like to thank:

• pashka, keta_tsimakuridze, Gheal, AlperenT, KrowSavcik, Sho, badlad, qwexd, Phantom_Performer, haochenkang, _Vanilla_, sandry24, jampm, tibinyte for testing and great feedback!

• TimDee for helping with russian translations!

• badlad for helping with a problem!

We suggest reading all of the problems and hope you will find them interesting!

GLHF!

UPD: Editorial

Introduction

Hi everyone, because we noticed there was no good tutorial in English explaining this idea, KrowSavcik and I have decided to write a tutorial blog on it!

This idea finds the values of each element from a binary array using $$$O(N / log(N))$$$ sum queries, more specifically it solves problems of the type:

Given a binary array $$$b$$$ (an array consisting only of zeroes and ones) of $$$n$$$ elements, you can ask queries of the following format:

What is the sum of the subsequence of the values on positions: $$$p_1, p_2, ..., p_k$$$. In other words you will give the subsequence $$$p_1, p_2, ..., p_k$$$ to the interaction and it will return you the value of ($$$b_{p_1} + b_{p_2} + ... + b_{p_k}$$$).

And after asking $$$O(N / log(N))$$$ queries we should be able to tell the value of each index.

The technique was mentioned here too but it was not as detailed and not easy to find.

Concept

The idea is to use a divide and conquer-like approach. Because it's not an intuitive concept, firstly I will have to add some simple notations, so it will be easier to understand it.

• $$$x_i$$$ — refers to the position $$$i$$$
• $$$A$$$ — any capital letter (except S) refers to a set of points $$$x_i$$$
• $$$v_{A} = \sum b_{x_i}$$$ for $$$x_i \in A$$$
• $$$k$$$ — the layer we are currently considering
• $$$S_i$$$ — Set of queries

Also you should keep in mind that indices are enumerated from 0.

Also keep in mind that even though it's said the queries are used, we actually only query at the end, and we build up our set of queries first for multiple layers first.

As it is a divide and conquer-like approach we will work with layers. Let's say that for layer $$$k$$$ we need $$$2^k$$$ queries and that from it we can get the value of $$$f_k$$$ elements. Then $$$f_{k+1} = 2 \cdot f_k + 2^k - 1$$$.

First of all, let's set our base case, which is $$$k = 0$$$. So, for $$$k = 0, f_0 = 1$$$ and the query set will only be {$$$0$$$}, so we know a single element using a single query.

The block $$$f_{k+1}$$$ is formed from $$$2$$$ blocks of size $$$f_k$$$ and $$$2^k -1$$$ additional elements in this order. Let's say $$$k_1$$$ represents the first block of $$$f_k$$$ elements and the $$$k_2$$$ the second such block.

The first query is used to get the sum on $$$[f_k, 2 \cdot f_k)$$$ — the sum of the second block. Then we add two new queries for each non last query in $$$S_{k_1}$$$ and $$$S_{k_2}$$$. First one is $$$S_{k_1}[i] \cup S_{k_2}[i]$$$. Second one is $$$S_{k_1}[i] \cup ([f_k, 2 \cdot f_k) / S_{k_2}[i]) \cup x_{(2 \cdot f_k + i)}$$$.

The last query is for entire range $$$[0, f_{k+1})$$$.

I think it's easy to see why we now have $$$2^{k+1}$$$ queries. The harder part is to understand why we don't lose any value in this process, and how we can solve it recursively. In fact, having answered all the $$$S_{k+1}$$$ queries, we can calculate all the $$$v_{S_{k_1}[i]}$$$ and $$$v_{S_{k_2}[i]}$$$.

Now, when we reach a $$$k$$$ with a value of $$$f_k >= n$$$ we can stop there. Let's assume $$$n = f_k$$$ since it will be easier to work with it (when $$$n$$$ is smaller than $$$f_k$$$ we can just think of it as appending $$$f_k - n$$$ zeroes at the end since they won't influence the sum at all). There is a more elegant way to form $$$n$$$ from blocks of different sizes, but it doesn't enter the scope of this blog and it's not that hard to implement using offsets. Using the set of queries responsible for the $$$k$$$-th layer we can in fact now reconstruct the whole sequence, now recursively going from the $$$k$$$-th layer to the ($$$k - 1$$$)-th one (but consider each layer can have multiple blocks).

First of all, the only things we care about when we are in the $$$k$$$-th layer are:

• The query set for the corresponding block of the corresponding layer.
• The block we are currently at (can be dealt with using an offset value in the recursion).

So we will store them when going recursively.

Firstly, let's again set our base case: $$$k = 0$$$. We are now sure that only one element is responsible for this block from this layer, so we can just set the value of the $$$b_x$$$-th bit (where $$$x$$$ is some offset value we use to keep track of the block) to $$$v_{S_0}$$$ (since that's the sum for a single element which we've seen at the build-up).

Now, since the base case is already dealt with, here's how we will go to the ($$$k - 1$$$)-th layer:

We will need to reconstruct the previous query sets for the first block and the second block of size $$$f_{k - 1}$$$, and set the values for the other $$$2^{(k - 1)} - 1$$$ values respectively (since they aren't part of any of the blocks they shouldn't be part of the recursion either).

Let's denote the numbers of $$$1$$$-s in $$$[f_k, 2 \cdot f_k)$$$ with $$$c$$$. It's obvious that $$$c = v_{S[0]}$$$. We will now go through every pair of queries, starting from 1. That means we will be analyzing queries $$$S_1[i] \cup S_2[i]$$$ and $$$S_1[i] \cup ([f_{k-1}, 2 \cdot f_{k-1}) / S_2[i]) \cup x_{(2 \cdot f_{k-1} + i)}$$$.

• $$$v_{S[2 \cdot i + 1]} = v_{S_1[i]} + v_{S_2[i]}$$$
• $$$v_{S[2 \cdot i + 2]} = v_{S_1[i]} + c - v_{S_2[i]} + b_{2 \cdot f_{k-1} + i}$$$

In this case we have to calculate 3 values: $$$v_{S_1[i]} , v_{S_2[i]} , b_{2 \cdot f_{k-1} + i}$$$.

• $$$v_{S_1[i]} = \lfloor\frac{v_{S[2 \cdot i + 1]} + v_{S[2 \cdot i + 2]} - c}{2}\rfloor$$$
• $$$v_{S_2[i]} = \lceil\frac{v_{S[2 \cdot i + 1]} - v_{S[2 \cdot i + 2]} + c}{2}\rceil$$$
• $$$b_{2 \cdot f_{k-1} + i} = (v_{S[2 \cdot i + 1]} + v_{S[2 \cdot i + 2]} - c) \land 1$$$

The only remaining queries to answer are $$$v_{S_1[2^{k-1}]}$$$ and $$$v_{S_2[2^{k-1}]}$$$ as we didn't add them in $$$S$$$.

• $$$v_{S_2[2^{k-1}]} = c = v_{S[0]}$$$
• $$$v_{S_1[2^{k-1}]} = v{S[2^k]} - c - \sum_{i = 0}^{2^{k-1}-1} b_{2 \cdot f_{k-1} + i} $$$

So, with all this calculated we are ready to go down to the previous layer's blocks.

Visual representation

Here's a visual representation of the queries we use for going up to the next layer:

• The green squares represent the queries responsible for the first block of the previous layer.
• The orange squares represent the queries responsible for the second block of the previous layer.
• The blue squares represent the queries that query the whole second block excluding the elements from the query of the second block.
• The red squares represent the last $$$2^k - 1$$$ bits.

Count of queries (a bit optimized)

Here's a visual representation of how the count of queries grows as $$$n$$$ increases, we notice that the count of queries is around $$$2.67 \cdot n / log2(n)$$$.

Some Code

Keep in mind this code is pretty inefficient and is just used to explain the solution better (it's still functional though)

Firstly, let's set some helper functions to work easier with our query sets:

vector<int> range(int l, int r) {  
    vector<int> v;
    for(int i = l; i <= r; ++i) v.push_back(i);
    return v;
}
vector<int> lift(vector<int> v, int extra) {
    vector<int> ans;
    for(auto x: v) ans.push_back(x + extra);
    return ans;
}
vector<int> add(vector<int> A, vector<int> B) {
    vector<int> C = A;
    for(auto x: B) C.push_back(x);
    return C;
}
vector<int> erz(vector<int> A, vector<int> B) {
    vector<int> v;
    for(auto x: A) {
        auto it = lower_bound(B.begin(), B.end(), x);
        if(it != B.end() && *it == x) continue;
        v.push_back(x);
    }
    return v;
}
int query(vector<int>& v, int limit) {
    if(v.empty() || v[0] > limit) return 0;
    for(auto x: v) if(x <= limit) cout << x << " ";
    cout << endl;
    int x; cin >> x; return x;
}

Now, here's how we do the build-up part:

int kk = -1 //kk will be the first k value such that f[kk] >= n
s[0] = {{0}}, f[0] = 1; //assigning the base case
for(int k = 0; k + 1 < K; ++k) {
   //Going from k to k + 1
   f[k + 1] = 2 * f[k] + (1 << k) - 1; //the size of the range it solves now
   vector<int> c = range(f[k], 2 * f[k] - 1);
   s[k + 1].push_back(c);
   vector<int> q;
   for(int i = 0; i < (int)s[k].size() - 1; ++i) {
       //the first query we do for each previous query
       q = add(s[k][i], lift(s[k][i], f[k]));
       s[k + 1].push_back(q); 
       //the second query we do for each previous query.
       q = add(add(s[k][i], erz(c, lift(s[k][i], f[k]))), {2 * f[k] + i}); 
       s[k + 1].pb(q);
   }
   //the final query
   s[k + 1].push_back(range(0, f[k + 1] - 1));
   if(f[k + 1] >= n) {
      kk = k + 1;
      break;
   }
}
//Now we ask the actual values of the queries.
vector<int> qq;
    for(int i = 0; i < (int)s[kk].size(); ++i)
        qq.push_back(query(s[kk][i], n - 1));

And the final part — recursively going from the $$$k$$$-th layer to the ($$$k - 1$$$)-th till each element is visited.

void rec(int k, int x, vector<int>& q, int limit) {
    if(k == 0) {
        //the base case
        if(x <= limit) {
           //make sure the element fits between a limit so we don't assign useless values.
            ans[x] = q[0];
        } 
        return;
    }
    vector<int> ql, qr; //the query sets for the previous layer for the left and right blocks respectively
    int a, b, c, q1, q2, sm = 0;
    c = q[0];
    assert(sz(q) % 2 == 0); //we can be sure the query set is even.
    for(int i = 1; i + 1 < sz(q); i += 2) {
        q1 = q[i], q2 = q[i + 1];
        a = (q1 + q2 - c) / 2;
        b = q1 - a;
        if(2 * f[k - 1] + x + (i / 2) <= limit) {
            //assigning the value of the bit in the third block (in the last 2^k - 1 elements)
            ans[2 * f[k - 1] + x + (i / 2)] = (q1 + q2 - c) & 1;
        }
        sm += (q1 + q2 - c) & 1;
        ql.push_back(a);
        qr.push_back(b);
    }
    a = q[sz(q) - 1] - c - sm;
    ql.pb(a);
    qr.pb(c);
    rec(k - 1, x, ql, limit); //recursively going to the first block of the previous layer
    rec(k - 1, x + f[k - 1], qr, limit); //recursively going to the second block of the previous layer
}

Hello Codeforces!

mesanu, flamestorm, MikeMirzayanov and I want to invite you to Codeforces Round 799 (Div. 4)! It starts on 14.06.2022 17:35 (Московское время).

The format of the event will be identical to Div. 3 rounds:

• 5-8 tasks;
• ICPC rules with a penalty of 10 minutes for an incorrect submission;
• 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
• after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
• by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them),
• do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to the testers: Neophiliatic, Qualified, sandry24, _Anurag, jampm, TimDee, Olympia, hbarp, AlperenT, BucketPotato and VIP-tester _Vanilla_.

And thanks to NEAR for supporting this round, details can be found in this post.

We suggest reading all of the problems and hope you will find them interesting!

Good Luck!

UPD: Editorial is posted!

Thank you for participating!

1676A - Lucky?

Idea: mesanu and SlavicG

#include <bits/stdc++.h>
using namespace std;

void solve() {
	string s;
	cin >> s;
	if(s[0]+s[1]+s[2] == s[3]+s[4]+s[5]) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

int main() {
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
}

1676B - Equal Candies

Idea: Errichto

#include "bits/stdc++.h"
using namespace std;

int main() {
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        vector<int> a(n);
        int mn = INT_MAX, ans = 0;
        for(int i = 0; i < n; ++i) {
            cin >> a[i];
            mn = min(mn, a[i]);
        }
        for(int i = 0; i < n; ++i) {
            ans += a[i] - mn;
        }
        cout << ans << "\n";
    }
}

1676C - Most Similar Words

Idea: MikeMirzayanov

#include "bits/stdc++.h"
using namespace std;

int cost(string& a, string& b) {
    int val = 0;
    for(int i = 0; i < a.size(); ++i) {
        val += abs(a[i] - b[i]);
    }
    return val;
}

int main() {
    int t; cin >> t;
    while(t--) {
        int n, m; cin >> n >> m;
        vector<string> s(n);
        for(int i = 0; i < n; ++i) {
            cin >> s[i];
        }
        int ans = INT_MAX;
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                ans = min(ans, cost(s[i], s[j]));
            }
        }
        cout << ans << "\n";
    }
}

1676D - X-Sum

Idea: mesanu

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
	int n, m;
	cin >> n >> m;
	int a[n][m];
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			cin >> a[i][j];
		}
	}
	int mx = 0;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			int now = 0;
			int ci = i, cj = j;
			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
			{
				now+=a[ci][cj];
				ci--;
				cj--;
			}
			ci = i, cj = j;
			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
			{
				now+=a[ci][cj];
				ci++;
				cj--;
			}
			ci = i, cj = j;
			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
			{
				now+=a[ci][cj];
				ci--;
				cj++;
			}
			ci = i, cj = j;
			while(ci >= 0 && ci < n && cj >= 0 && cj < m)
			{
				now+=a[ci][cj];
				ci++;
				cj++;
			}
			now-=a[i][j]*3;
			mx = max(mx, now);
		}
	}
	cout << mx << endl;
}

int main() {
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
}

1676E - Eating Queries

Idea: mesanu

#include "bits/stdc++.h"
using namespace std;

int main() {  
    int t; cin >> t;
    while(t--) {
        int n, q; cin >> n >> q;
        vector<long long> a(n), p(n);
        for(int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        sort(a.rbegin(), a.rend());
        for(int i = 0; i < n; ++i) {
            p[i] = (i ? p[i - 1] : 0) + a[i];
        }
    
        while(q--) {
            long long x; cin >> x;
            int l = 1, r = n, ans = -1;
            while(l <= r) {
                int mid = (l + r) / 2;
                if(p[mid - 1] >= x) {
                    ans = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            cout << ans << "\n";
        }
    }
}   

1676F - Longest Strike

Idea: MikeMirzayanov

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
	int n, k;
	cin >> n >> k;
	int a[n];
	map<int, int> mp;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		mp[a[i]]++;
	}
	vector<int> c;
	for(auto x : mp)
	{
		if(x.second >= k)
		{
			c.push_back(x.first);
		}
	}
	if(c.size() == 0)
	{
		cout << -1 << endl;
		return;
	}
	sort(c.begin(), c.end());
	int mx = 0;
	int lans = c[0], rans = c[0];
	int l = c[0];
	for(int i = 1; i < c.size(); i++)
	{
		if(c[i]-1 == c[i-1])
		{
			if(c[i]-l > mx)
			{
				lans = l;
				rans = c[i];
				mx = c[i]-l;
			}
		}
		else
		{
			l = c[i];
		}
	}
	cout << lans << " " << rans << endl;
}

int main(int argc, char * argv[])
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
}

1676G - White-Black Balanced Subtrees

Idea: MikeMirzayanov

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n;
	cin >> n;
	vector<int> child[n + 7];
	for (int i = 2; i <= n; i++) {
		int x;
		cin >> x;
		child[x].push_back(i);
	}
	string s;
	cin >> s;
	int res = 0;
	function<int(int)> dp = [&] (int x) {
		int bal = (s[x - 1] == 'B') ? -1 : 1;
		if (child[x].empty()) {return bal;}
		for (int i : child[x]) {
			bal += dp(i);
		}
		if (bal == 0) {res++;}
		return bal;
	};
	dp(1);
	cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

1676H1 - Maximum Crossings (Easy Version)

Idea: flamestorm

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

void solve() {
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int res = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (a[i] >= a[j]) {res++;}
		}
	}
	cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

1676H2 - Maximum Crossings (Hard Version)

Idea: flamestorm

#include <bits/stdc++.h>

using namespace std;

const int MAX = 200007;
const int MOD = 1000000007;

long long merge(int a[], int temp[], int left, int mid, int right) {
   int i, j, k;
   long long count = 0;
   i = left;
   j = mid;
   k = left;
   while ((i <= mid - 1) && (j <= right)) {
      if (a[i] <= a[j]){
      temp[k++] = a[i++];
      } else {
         temp[k++] = a[j++];
         count += (mid - i);
      }
   }
   while (i <= mid - 1)
      temp[k++] = a[i++];
   while (j <= right)
      temp[k++] = a[j++];
   for (i=left; i <= right; i++)
      a[i] = temp[i];
   return count;
}
long long mergeSort(int a[], int temp[], int left, int right){
   int mid;
   long long count = 0;
   if (right > left) {
      mid = (right + left)/2;
      count = mergeSort(a, temp, left, mid);
      count += mergeSort(a, temp, mid+1, right);
      count += merge(a, temp, left, mid+1, right);
   }
   return count;
}
long long aInversion(int a[], int n) {
   int temp[n];
   return mergeSort(a, temp, 0, n - 1);
}

void solve() {
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	long long res = aInversion(a, n);
	sort(a, a + n);
	long long curr = 1;
	for (int i = 1; i < n; i++) {
	    if (a[i] != a[i - 1]) {res += (curr * (curr - 1)) / 2; curr = 1;}
	    else {curr++;}
	}
	res += (curr * (curr - 1)) / 2;
	cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
    // solve();
}

Credits to FLEA for teaching me this trick.

Introduction

Recently I learnt an interesting trick I wanted to share with others. I'm not sure if this trick is well known, but I didn't know about it and didn't find any other articles on it so decided to write this blog.

Problem statement

We have a connected undirected graph with $$$n$$$ nodes and $$$m$$$ edges between them, each node having a value $$$w_i$$$ ($$$1 <= n, m <= 10^5$$$), ($$$1 <= w_i <= 10^9$$$).

Let's denote $$$f(a, b)$$$ as the minimum value of a node on a path from node $$$a$$$ to node $$$b$$$.

We have to answer $$$q$$$ queries about this graph. Each query contains $$$2$$$ nodes $$$a$$$, $$$b$$$ and asks for the maximum $$$f(a, b)$$$ over all possible paths from node $$$a$$$ to node $$$b$$$. ($$$1 <= q <= 10^5$$$).

Notes

This problem can be solved in another (more optimal) way, which is described in these comments: 1, 2. Thanks to valeriu and geniucos for mentioning it!

A similar idea from stefdasca.

Prerequisites

In order to fully understand the idea you have to know about DSU (disjoint set union) and small to large merging.

Solution

We will do some kind of DSU (disjoint set union). For each node, we don't only keep its parent, but also the queries it appears in (we store them in a map/set). Then we go through all the $$$n$$$ nodes in decreasing order of their values. When we are at a node — $$$u$$$, we "activate" it and then go through all the already activated neighbors the node has and we merge these two nodes.

How do we merge them?

First, we do the simple merge of the $$$2$$$ components with the classic $$$par[a] = b$$$. Then, we go through all queries the node is responsible for and check if it also appears in the query of the other node. If it does, we set the answer of that query to the weight of the node we are currently considering, since we know it will be the minimum on the path (because we are going through nodes in decreasing order of their values), if they don't both appear we just insert the the given query to the combined component and continue. But, since it would take too long, we merge the query sets with small to large merging (merge the node which has a smaller (in size) query set to the one that has a larger one). So, we do all this in $$$O((n + m) log^2n)$$$.

Some code

Note: ans[i] is the answer for query with index $$$i$$$.

First of all, we need the DSU functions — get (which returns the node responsible for the whole component) and union, which merges $$$2$$$ different components.

Since the only things we care about for a node are its parent and set of queries it's responsible for we can keep a pair of an integer and a map/set.

The union, as discussed in the above solution part involves small to large merging. If both nodes are responsible for a query then the answer for the query is the weight of the other node, otherwise we insert the query to the combined component.

const int N = 1e5 + 10;

vector<pair<int,int>> adj[N];

pair<int, map<int, int>> d[N];

int get(int u) {
    if(u == d[u].first) return u;
    return d[u].first = get(d[u].first);
}

void uni(int a, int b, int c) {
    a = get(a), b = get(b);

    if(d[a].second.size() > d[b].second.size()) {
        swap(a, b);
    }

    d[a].first = b;
    for(auto i: d[a].second) {
        if(d[b].second.count(i.first)) {
            ans[i.first] = c;
        } else d[b].second[i.first] = 1;
    }
}

After that, we need to set the initial components. Initially, nodes should have an empty query set and their parent should be themself only, and we can sort the nodes by decreasing order of their values in the same time (vector v will contain the node index on the second position). And, we can go also go through queries and add the queries responsible for a given node to a list.

vector<pair<ll, int>> v;

for(int i = 0;i < n; ++i) {
   v.pb({dist[i], i});
   d[i] = {i, {}};
   d[i].second.clear();
}
sort(v.rbegin(), v.rend());
int qq;
cin >> qq; // scanning the number of queries and node a, b of each query
vector<pair<int,int>> qr(qq);
vector<int> responsible_queries[N];
for(int i = 0;i < qq; ++i) {
   cin >> qr[i].first >> qr[i].second;
   --qr[i].first, --qr[i].second;
    responsible_queries[qr[i].first].pb(i);
    responsible_queries[qr[i].second].pb(i);
}

Now for the iteration in decreasing order of the values, we keep the boolean activated for each node, which tells us whether the node was already "activated" (gone through) or not.

vector<bool> activated(n, false);
    for(auto ff : v) {
        int u = ff.second, w = ff.first; //u - node, w - its value
        int l = get(u); //l - parent responsible for the component of the node
        activated[u] = true;
        for(int z: responsible_queries[u]) {
            if(!d[l].second.count(z))
                d[l].second[z] = 1; //we add the query to the set of queries the node is responsible for.
            else ans[z] = w; //The node is an endpoint of a query and its the smallest when merged to it, so the answer for the query is just the value of the node.
        }
        for(auto yy: adj[u]) {
            int ng = yy.first;
            if(activated[ng]){
                uni(u, ng, w); //if the node is activated we merge them in the manner described above.
            }
        }
    }

Then, we are left with outputting the answer for each query.

Variations

This trick can solve many variations of the problem, the most obvious one being that $$$f(a, b)$$$ would be the maximum value on the path instead of the minimum, which would require their little modifications

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 _Vanilla_ and mesanu for helping me write the blog, and Monogon, qwexd and AlperenT 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 ratings, divisions, rules, rating system, contribution and many more. I strongly suggest taking a look at it.

What is the Home Page?

The Home page is where the official Codeforces announcements are posted, these being mostly round announcements and sponsored posts. It also gets the occasional new feature update and such. You are directly sent to the home page when you open Codeforces but it's also possible to get to it by clicking the "Home" button in the top left bar. The contest announcement blogs will usually have information about the contest like: The author of the contest The time the contest will take place How much time the contest will last The rating range of rated contestants The contest’s coordinator, official problem reviewer Testers, community problem reviewers Scoring Distribution, points given for every problem Also after the contest, the blog will be updated to include: Editorial/Tutorial Winners of the contest

At the bottom of most contest announcements you can find the “Announcement of ”, you can click on this button to take you to the contest’s dashboard. You can also upvote/downvote a blog using the green and respectively red arrows.

What is the top page?

The Top page can be accessed by clicking the "Top" button on the menu bar. It contains the most popular recent blogs and comments. You can change between looking through blogs and comments by clicking "Posts" or "Comments" in the top left of the page.

What is the Catalog?

Catalog page can be accessed using the "Catalog" button on the menu bar. It is a community based page which contains blogs written by the community sorted on topics.

About Contests

The Contests page can be accessed by clicking the "Contests" button on the menu bar. On this page you can see all scheduled contests sorted by date, and some short information about them: Their title (which also contains the division the contest is rated for), the contest writers, the start time and the duration of the contest. You can register to contests using the register button which appears some days before the contest (you can't participate in a contest without registering to it, and if you register in a contest and don't submit anything the contest won't be rated for you, otherwise it will if your rating fits in the contest criteria (which will be discussed about later)).

This page also contains "Contest history" which has all past contests that happened on the website sorted decreasingly by date, so the newest contests appear on the top. Alternatively, one can use the Calendar page to view all upcoming contests. The Calendar page displays information about past and upcoming contests in a more concise and organized form factor. It is based on "Google Calendar". You can easily navigate through it to any date you want and you can select to whether you want to see the calendar for a week, month or even a year. The Calendar is also capable to show upcoming streams from our beloved creators (insert love emoji).

In a contest's page, you can also access the standings, which is the scoreboard in increasing order of the place the participants got, so the first place is the topmost. There is also friend's standings where you can see the place only of the people you follow in the same format, which is more convenient to follow only the performance of the people you care about.

During a contest, in the problem's tab, you can also ask clarifications, using the "Ask a question" button as shown below:

You can ask clarifications on the specific problems you have trouble understanding some part of the statement. Clarifications should only be "clarifications", so you shouldn't try to use the clarifications button for asking for help to debug the code, the solution or any other unrelated things.

What is the GYM?

The Gym page can be accessed by clicking the "GYM" button on the menu bar. On this page there is a vast selection of contests, with the same information about them as in the contests page. All these contests are community written and aren't rated. This page also contains a "Training Filter" section. Using it you can filter the contests that you are searching for.

What is the problemset?

The problemset page can be accessed by clicking the "Problemset: button on the menu bar. This page contains the collection of all problems that appeared in contests in codeforces sorted by their ID number, which is practically by date in decreasing order. So the most recent problems appear on top. For each problem some information is given about each problem: it's ID, name, tags which are written in the same place as the name, submit and star options (clicking the submit button which has the shape of an airplane would redirect you to the submit page which has the problem selected), and clicking the star button would add the problem to favorites (there is a page where you can see all problems you marked as favorite which I will discuss about later), the problem's difficulty (currrently 800 is easiest and 3500 is the hardest difficulty), and the count of participants which solved the problem.

By clicking on the given arrows circled, you can sort problems by difficulty and count of solved accordingly. Clicking once will sort by hardest/most solved according to the clicked button, and clicking one more time sorts by easiest/least solved according to the clicked button.

How to solve problems?

Once you pick the problem you want to solve and go into it's page you can see: it’s title, it’s position in the contest, it’s time limit, memory limit, input/output format, samples and problem notes.

What is time limit?

The time limit is the most amount of time your solution will run on a single test. In case your solution takes more time to complete, you will receive a “Time Limit Exceeded” (TLE) verdict. If your solution gets time limit exceeded for a certain test, it will be run several times to make sure the verdict should in fact be time limit exceeded.

What is the memory limit?

The memory limit is the most amount of memory your program can consume. In case the memory consumed is more than the memory limit you will receive a “Memory Limit Exceeded” (MLE) verdict.

Verdicts

Accepted — it means the solution passed all the given tests and is correct.

Pretests passed — it means the solution passed a subset of tests during the contest and it might not be correct but there is a big probability it is. Pretests exist because running all solutions on all tests during a contest would be way too demanding for the servers.

Runtime error — it means the solution has an error that takes place while executing the program, such errors can be caused by dividing by 0, accessing invalid positions of an array and many more.

Wrong answer — it means your solution outputs an answer which differs from the intended answer or doesn’t satisfy some certain constraints given in the problem statement.

Time limit exceeded — it means your solution takes longer to execute than the time limit of the problem is.

Memory limit exceeded — it means your solution takes more amount of memory than the limit given for a certain problem.

Compilation error — it means your code failed to compile. Some causes for it could be that you used wrong syntax or submitted in the wrong programming language.

Hacked — it means your solution passed all tests but was hacked by another user during the hacking phase (which differs from contest to contest).

Idleness limit exceeded — it occurs when your program stays idle (waiting for user/interaction program) for too long.

What are problem tags?

Problem tags are the topics/algorithms that can be used to solve the problem. If a certain tag is present it doesn't mean that the solution must be related to that tag, but there is a solution using that certain topic. Tags may be put by members of the community who achieve a rating of 1900 or higher.

In case of practicing, you can choose whether you want to see the tags or not. Just click the "Show tags" checkbox in the right of the "Problemset" page. There you can also hide the solved problems.

What is the Groups page?

The Groups page let's you see the groups where you are a member. You also have the option to list all existing Codeforces groups, and to create your own group. For each group you have a different role, be it Participant, Manager or Creator. Each role gives access to different actions, the most important of them all being the Creator role. You can participate or create your own private Codeforces contests / mashups using the groups functionality. Joining some groups require that a Manager or Creator to accept your request. When creating a private group, you are prompted to specify the registration policy, based on which members can join it.

What is the Rating page?

The Rating page is a rather simple one, with it's base objective is to admire other's performance. There are some filters available, like selecting a country, a city or an organization. You also have the option to look at your friend's ratings, excluding everyone else. On the Rating page, you can see the name of the user, the number of contests he participated in and his current rating (usually takes some time to update after the rating changes of a round are published).

What is EDU?

The Educational page is a rather new addition to the Codeforces page. You the page you are shown a list of courses you can register and take part in. Each course has a navigation page, where you can hastily move throughout the content of the course. A "Step" in the course consists of "Theory" and "Practice". The Theory part usually consists of a video containing a short, but concise explanation of the topic. The Practice part usually consists of some problems where you can apply the algorithm and knowledge you obtained completing the Theory. The course also contains a comment section, where you can share your thought on the course or ask questions on it.

What is the calendar page?

The Calendar page contains all the scheduled Codeforces rounds and video streams in a compact way.

What is the API page?

The API page helps you use the restful API that Codeforces has to offer. It contains instruction on how you should model your GET or POST requests, how to obtain a private API key and what information to include in your requests headers. This page contains all information you would need when building a service / bot that needs access to Codeforces data, being a way better alternative to the traditional web scraping methods.

The Profile Page

The profile page can be accessed by clicking either your picture from the right part of the page or your name from the top right of the page, as shown in the following picture:

Just by opening the page, you can see it contains the contest rating, contribution amount, number of users who follow you (AKA friends), a change settings button, details about the registration on the website time and the last visit on Codeforces, a button where you can access all your blogs and comments, the "Write new entry" button used to write blogs, and "view my talks" button using which you can see all your discussions with other users on the website. Below all this information is your rating graph. It shows all rating changes from the first contest to the present. The colors on the graph represent the rank of the users, in the following way:

• gray — newbie (<1200 rating)
• green — pupil ([1200, 1399] rating)
• cyan — specialist ([1400, 1599] rating)
• blue — expert ([1600, 1899] rating)
• purple — candidate master ([1900, 2099] rating)
• yellow — master ([2100, 2299] rating)
• orange — international master ([2300, 2399] rating)
• red — grandmaster ([2400, 2599] rating)
• darker red — international grandmaster ([2600, 2999] rating)
• black-red — legendary grandmaster (>=3000 rating)

Below the rating graph there is the activity through the year. Green squares representing submissions on certain days.

How to access a contest's page?

You can access a contests page directly by clicking "Enter" in the Contests tab. But, if you are at a problem from the contest, you can click the contest's name from it:

How to view all my submissions?

To view all your submissions, from the profile page, click the Submissions button on the menu bar from the top.

On this page, submissions are sorted by submission time in decreasing order of time (the most recent submissions are also the top-most). You can also filter submissions based on your verdict, programming language and contests it appeared in, using the status filter on the right of the page:

How to view others' submissions on a certain problem?

To view others' submission on a certain problem, you need to get to the problem's contest page (as shown above). From this page, click the "status" button:

To view a solution click the Source (the long number in the first column of the table). To select submissions of a certain verdict on a certain problems use the status filter on the right part of the page.

So, if you were looking for Wrong Answer solutions on the first problem you would select:

• Problem: A
• Verdict: Wrong answer

You can also see submissions from a certain user just by writing his name in the Participant box.

How to view my submissions on a certain problem?

There are several ways. If you are at the problem's page, you could look at the bottom right of the page where there are "Last submissions of the problem". To view it just click on the ID of the submission which is in the first column of the table.

Another way is to go to the contest's page, the same way mentioned in "How to view others' submissions on a certain problem?" and click the "My submissions" button.

What are Codeforces friends?

By accessing someone's profile page and clicking the star near their name you "friend" this person. It basically means you follow this person's activity now. So, by looking at status and choosing the "friends only" option you will view only the submissions of the people you follow, same goes for standings in a contest as mentioned in the "About Contest" part.

The Codeforces friends is a one-sided relationship, so it's impossible to see who friended you.

What is Contribution?

The contribution number is the amount you contribute to the community. You get contribution by making blogs and/or comments who get upvotes. Contribution also decreases when you get downvotes. Also, the contribution of your older blogs becomes less after some time, more specifically after six months. So upvotes you get six months ago value way less than upvotes you get now.

About Blogs

Anyone can post blogs on Codeforces. New blogs can be accessed by anyone in the recent actions tab in the right part of the page. If you like someone's blog post you can upvote it by clicking the green triangle pointing upwards, and if you dislike one you can click the red triangle pointing downwards.

About Comments

Each blog has comments right under it. Anyone can comment on someone's blogs. The same as with blogs, you can upvote and downvote others' comments. You can also edit comments, but all previous revisions will be available for everyone by clicking the Rev arrow in the top-right of the comment.

Upvotes value

Different upvotes contribute a different amount of upvotes. So while a newbie's upvote counts as 1, an expert's value would count as 3. This number changes some time after upvoting, not instantly, so once you upvote it only changes by 1 but the value changes to your respective upvote's value later.

Find user

The Find user can be located in the middle-right of the home page. You can easily find the users you are searching for by writing a substring of their name there, such as in this example:

Problemsetting

Most Codeforces rounds are community written, once you reach certain requirements you will have the "Propose a contest/problems" button under your profile. You can learn more about problemsetting here.

Types of Codeforces Rounds

At the moment there are 5 types of rounds:

• Div. 3 rounds — these rounds are rated for all users with a rating <= 1599. Each task in this types of contest values the same amount. After the round, there is a 12 hour open hacking phase where all users can look at others submissions and try to find a counter case to their solution and hack them. You don't get extra points for these hacks.

• Educational Rounds — these rounds are rated for all users with a rating <= 2099. The same as for Div. 3 rounds, each task in this contest values the same amount and after the round, there is a 12 hour open hacking phase where all users can look at others submissions and try to find a counter case to their solution and hack them. You don't get extra points for these hacks.

• Div. 2 rounds — these rounds are rated for all users with a rating <= 2099. The difference between Div. 2 and Educational rounds is that tasks values are chosen by the organizers of the rounds and easier tasks value less than harder tasks. Also, there is no hacking phase after the contest. You can make hacks during the round if you solve a problem and lock it. After locking, you can go in the "room" section and see the submissions of all users in your room. You can only hack people from your room.

• Div. 1 rounds — these rounds are rated for all users with a rating >= 1900. The rest is the same as for Div. 2 rounds.

• Open rounds — these rounds are open and rated for everyone. The format is the same as for Div. 1 and Div. 2 rounds. The most popular type of these rounds are the "Global Rounds" which happen approximately once per month.

Note: There was also a Div. 4 round once, which was rated for users with a rating <=1399. But, there probably won't be any more Div. 4 rounds so I didn't list it here.

Editorials

After each contest, the editorial is published. The editorial is a blog written by the authors of the round that contains solutions to all problems of the contest, sometimes with code. You can access it by clicking on the tutorial button on the bottom right of the problem's page in the contest materials section.

Virtual Contests

Virtual contests are a great way to practice. They simulate the contest environment perfectly. During a virtual contest you can see what your place would be as if you participated in contest, calculating your place as if you were actually participating in the round. You can start a virtual by going to the contest page and clicking the start virtual contest button:

Hello Codeforces!

Here are the results of the poll I made a week ago!

Because of the small sample size of 500 responses and a lot of other factors I am pretty sure the results aren't the most accurate, so take them with a grain of salt.

Anyway, let's start with the direct correlation table, for each of these items in the table, you can see the dependency level on the items represented as numbers between in the range [-1, 1], -1 meaning complete inverse correlation and 1 complete correlation, as the absolute value decreases the correlation decreases as well.

As we can see, there isn't that strong of a correlation, the strongest for rating being the people who practiced for math Olympiads and participated in national ones.

Now, here are results individual for rating ranges:

Even though there isn't that much of a noticeable correlation we can notice that the amount of participants and medalists in higher rated users is higher than the lower rated users. Same goes for the percentage of people that prepared for Olympiads.

But, what do others think? It turns out most think their previous math experience helped them achieve their current rating

Here you can access the document with all the data, in case anyone is curious about some more details I might have missed.

Thank you for reading the blog and answering to the poll!

Hello Codeforces!

Since I saw a lot of discussions regarding this topic, I wanted to see what the (actual) correlation between CP and Math skill is.

So, I am asking you to complete the following form and I will post the results and conclusions after I get enough responses (probably in around 2-3 days).

Maybe it won't be the most accurate measure, feel free to post suggestions to additional questions which would make the survey more accurate.

UPD: Results are out!

Hello Codeforces!

magnus.hegdahl and I are glad to invite you to Codeforces Round 767 (Div. 1) and Codeforces Round 767 (Div. 2) which will be held on Jan/22/2022 17:35 (Moscow time)! This round is rated for both divisions.

In each division there will be 6 problems and 2 hours to solve them.

We would like to thank the following amazing people:

• 74TrAkToR for great coordination of the round and translating the statements!
• efimovpaul, agrayush13, ak2006, BidoTeima, QuangBuiCPP, mesanu, _Vanilla_, qwexd, FedShat, gupta_samarth, namanbansal013, hbarp, stefdasca, AlperenT, DIvanCode, plagues, voventa, kpw29, ptd, AlexLuchianov, PurpleCrayon, abc864197532, Maksim1744 for testing, providing invaluable feedback and being awesome!
• Nika_Tamliani for helping in the early stages of the round!

• MikeMirzayanov for great Codeforces and Polygon platforms!

• You, for participating and upvoting!

Score distribution:

Div. 2: $$$500$$$ — $$$750$$$ — $$$1250$$$ — $$$1500$$$ — $$$2000$$$ — ($$$1500$$$ — $$$1000$$$).

Div. 1: $$$500$$$ — $$$750$$$ — $$$1250$$$ — ($$$1000$$$ — $$$750$$$) — $$$2250$$$ — $$$3000$$$.

UPD1: ak2006 and namanbansal013 have prepared video editorials for most div. 2 problems that will be available on ak2006's channel and namanbansal013's stream

UPD2: Editorial is out!

I think the order: Home, Top, Contests, Gym, Problemset, Groups, Rating, Catalog, Edu, API, Calendar, Help

would be more appropriate because of their functionalities. In my opinion, contests and problemset should be more in front because it's the main reason of the website and EDU and Catalog should be next to each other, due to their educational nature.

Another reason I am not very fond of the Catalog's position is because of muscle memory. Me and a lot of people I know keep on mis-clicking the Contests button because of it's previous position in the list.

A poll to see what the community thinks

I would like to see the Catalog's position changed

I like current Catalog's position

I don't care

How I got Sabotaged In GR17

• I was participating in the Global Round, submitting my ordinary wrong answers on pretest 2 on problem A when I got a notification that I got a Codeforces message (it was around 20 minutes into the round). Didn't give it much thought and immediately opened it to find the following message:

• Now, because of this, I couldn't submit the solution to the problem anymore, since it would be considered cheating, even though I had quite high chances of finding the edge-case myself. So, I had to participate the whole round with ~400 points less than I could have gotten myself, which is quite frustrating. I know they didn't have bad intentions, but let's be fair, cheating is bad in any manner.

The Problem

• The same way I got the undesired external help, how many other people have gotten it? For how many was it actually undesired? And what if others submitted the solution and replied with help to another problem as well?

Possible Solution

• Cheating is almost impossible to stop, but we can at least reduce it. I suggest just totally removing the possibility of messaging during a round (2-3 hours of not being able to message on codeforces shouldn't be that big of a deal) or at least make it available for a smaller subset of people (maybe based on rating, or trust factor). At least it would make cheating harder, and stop cases where people randomly "help" without you even asking for it.

MikeMirzayanov is there any reason why messaging on codeforces wouldn't be blocked during the contest period?

Hello Codeforces!

mesanu and I are very glad to invite you to Codeforces Round 726 (Div. 2) which will take place on 18.06.2021 17:35 (Московское время). The round will be rated for participants with a rating lower than 2100. Division 1 participants are also welcomed to take part in the competition but it will be unrated for them.

The round was originally planned to be a division 3 round so the problems might be slightly easier than average Div 2.

You will be given 6 problems and 2 hours to solve them.

We would like to thank the following people:

• 1-gon for amazing coordination of our round!

• antontrygubO_o for testing, translating statements and providing useful ideas!

• Maksim1744, Ari, qpwoeirut, magnus.hegdahl, PurpleCrayon, Brodicico, Omkar, DenjellBoone, Arsenie, Lost_Arrow, Etherite, asrinivasan007, nishuz, cringeworthyplayz, Nika_Tamliani, Vpurice for testing and providing invaluable feedback!

• MikeMirzayanov for great Codeforces and Polygon platforms!

• You, for participating!

The scoring distribution is: 500 — 750 — 1000 — 1500 — (1250+1750) — 2000.

UPD: Editorial

This is the editorial for the Unofficial Div 4 Round #2 by ssense SlavicG.

We hope everyone had fun and enjoyed the contest!

Video Editorial by demoralizer

Problem A — Catching the Impostor.

#include "bits/stdc++.h"
using namespace std;
int main()
{
    set<int> s;
 	int n, m;
 	cin >> n >> m;
 	for(int i = 0;i < m;i++){
 		int x;
 		cin >> x;
 		s.insert(x);
 	}
 	if(s.size() == n - 1){
 		cout << "YES";
 	}else{
 		cout << "NO";
 	}
}

Problem B — Rabbit Game

#include "bits/stdc++.h"
using namespace std;
int main()
{
        int n;
	cin >> n;
	int a[n];
	for(int i=0;i < n;i++)
		cin >> a[i];
	int Rabbit1 = 1;
 
	for(int i = 1 ;i < n;i++)
	{
		if(a[i] >= a[i-1]){
			Rabbit1++;
		}else{
			break;
		}
	}
 
	int Rabbit2 = 1;
 
	for(int i = n-2;i>=0;i--)
	{
		if(a[i] >= a[i+1]){
			Rabbit2++;
		}else{
			break;
		}
	}
	cout << min(n , Rabbit2 + Rabbit1);
}

Problem C — Similar Arrays

#include "bits/stdc++.h"
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[n];
    for(int i = 0;i < n;i++){
    	cin >> a[i];
    }
    sort(a,a+n);
    long long ans = 0;
    int median = a[n/2];
    for(int i = 0;i < n;i++){
    	ans += abs(median - a[i]);
    }
    cout << ans;
}

Problem D — Sanda's Job

#include "bits/stdc++.h"
using namespace std;

int main()
{
    long long n,m;
    cin >> n >> m;
    m-=n;
    if(m <= 0){
        cout << "NO";
        return 0;
    }
    string s = to_string(n);
    string k = to_string(m);
    sort(s.begin(), s.end());
    sort(k.begin(), k.end());
    if(k==s){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

Problem E — Count Substrings

#include "bits/stdc++.h"
using namespace std;

int main()
{
    string s, t;
    long long n;
    cin >> n >> s >> t;
    long long l = 0;
    long long ans = 0;
    for(int i = 0; i < n-1; i++)
    {
        if(s[i] == t[0] && s[i+1] == t[1])
        {
            long long from = i-l+1;
            long long to = n-(i+1);
            ans += from*to;
            l = i + 1;
        }
    }
    cout << ans << endl;
}

Problem F — Game on Grid

#include "bits/stdc++.h"
using namespace std;

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
	    int n;
	    cin >> n;
	    if(n%4==2){
	    	cout << "Alice\n";
	    }else if(n%2==0){
	    	cout << "Draw\n";
	    }else{
	    	cout << "Bob\n";
	    }
	}
}

#include "bits/stdc++.h"
using namespace std;

int main()
{
    long long n;
    cin >> n;
    long long cover = ((n / 2) * (n / 2) + 1) / 2;
    long long as = 4 * cover;
    long long bs = n * n - as;
    
    if (as == bs) cout << "Draw\n";
    else if (as < bs) cout << "Bob\n";
    else cout << "Alice\n";
}

Hello Codeforces!

mesanu and I are glad to invite you to Unofficial Div 4 Round #1. The round will not be rated for any participants since it is unofficial. Sadly, We can not post the contest on the Gym Section, so you can virtually participate in the contest by clicking this link:

https://mirror.codeforces.com/contestInvitation/d477e058f265a72092af5c11074234d720a0fb5f

You will be given five tasks and two hours to solve them.The problems were created and prepared by mesanu and SlavicG for users with a rating range from 0 to 1400 but anyone is welcome to participate in the round!

We would like to thank everyone who was involved in the round preparation:

• Brodicico, Grumpah, Sho for testing the problems and providing useful feedback.
• MikeMirzayanov for Polygon and Codeforces platforms.

Even though the contest is unrated we believe it is a really good way of practice, especially for Div 4 users. We tried our best to keep the statements short and clear and we hope you will like our problems!

UPD: You can participate whenever you want, just click the link above and virtually participate.

UPD2: Tutorial will be posted September 19 by mesanu.

UPD3: Editorial is out and contest is open for practice!

Editorial

Congratulations to the winners:

1. extremum

2. tribute_to_Ukraine_2022

3. Denisov

4. conqueror_of_tourist

5. iamnifer

6. brunomont