Hello Codeforces!

Just like last year, I worked on this year's Indigo Coding Contest as well and I am happy to announce this year's edition here on Codeforces too.

This year's Indigo Coding Competition will be happening on Saturday, November 23rd, from 3:00PM to 6:00 PM EST! and it will be held on HackerRank.

In order to participate, you need to complete the google form until November 21 and check out the information from the contest website. We also recommend joining our community on Discord.

Designed and organized by students from Carmel High School in the US, this contest is great for everyone, but mostly for beginner and intermediate contestants looking for a challenge on problems similar in style to the problems given at USACO or other Olympiads. Anyone can participate and there are prizes worth $1000+ for the winners who are in pre-college, but also raffle prizes.

This is a great opportunity to code with friends (you can compete individually or in pairs), meet new people, solve some cool problems, and have fun! If you're interested, check out the website and join the discord server.

We look forward to seeing you there!

At this point, I think that just about everyone here is familiar with the recent series of blogs surrounding the case of Psychotic_D and his gang of cheaters, things which have been exposed here and by defnotmee in these two blogs (here and here) in more detail.

But what if I tell you that cheaters end up setting rounds on a regular basis too? What makes it even worse is that in some cases, these people use the goodwill of some of the coordinators for their own benefit without having any remorse for their actions, and here is one example in action which caught my attention as it made waves in some of the communities I'm in.

Background story

Cheating is more and more of a problem as shown by the fact that at almost any instance, there is at least one blog talking about a cheater or a cheating group, and this problem got worse now that cheaters can live stream solutions on various platforms.

The first notorious case of a cheater who set a round which came to my mind was the round where TimDee, someone who cheated multiple times according to this comment and the linked blog ended up being a co-author in the round (in fairness, judging from the editorial, 90% of the work wasn't done by him). I thought at first that this should be just a one off, right? Codeforces can't possibly let people who fraud their contests set rounds.

Oh dear, I couldn't have been more wrong

As the number of cheaters grew, more people started using various tricks to also fraud their way into problem setting, without respecting the current system, and I am going to show one case which stroke to my mind after having seen the discussions online. First, it is a known fact that many rounds are set based on official contests, with various degrees of quality, and what I will say here does not apply to these rounds.

While I believe many rounds are set by people based on their connections to coordinators rather than having waited in the queue, talked to coordinators and then have an actual round set up after some time (I have been involved in two such rounds and the process took about 1 year and many problem proposals in each of these, back in 2019 and 2020), nothing has been as worse as what I witnessed over the past couple of weeks. So let's present -2.71

A wannabe innovator turned cheater

Just about everyone who is somewhat more known must have received such messages over time, from various people who want to set rounds and have an easy path to getting it done. At the time, I thought he would simply just try to maybe team up with some more experienced problem writers and maybe have a round like that. Now, let's analyze his behavior during this year.

First, I had a series of messages with him where I reviewed a few of the problems, without the intention of actually coordinating him (I am not a coordinator here and also I have many other things I have to do anyways) only to then see his messages grow more and more absurd and dishonest. His initial motive according to his messages was to make Palestine proud of him before any unfortunate event happens given the ongoing conflict in the region, but going from this and turning it into a weapon to shame people into having him around is something completely different and unacceptable in my opinion.

Over the last few months, I saw his name pop out more and more and I started making some more research. One can notice here that a lot of his comments are about how he claims to be a national pioneer as far as many aspects go.

Recently, I learned that he is in the shortlist of setting a Codeforces round and given how long the queue is, plus the fact that I personally know very capable people who have to be stuck in the queue while such persons end up setting rounds on the fast track was what made me actually write this blog.

His low rating is already enough evidence for probably not having what it takes to be a problem setter, but what if I tell you that he doesn't have the knowledge about some relatively standard topics, such as DP?

At some point, he ended up joining TheForces, as shown by his profile status and his status as a moderator in their discord server, and this is where things started to become more shady, as shown by the evidence below. Given how some of TheForces' staff behave as far as reaching out to coordinators goes, with wuhudsm's case here exposed by errorgorn, our main protagonist of the blog decided to follow his lead too.

In one of his recent rounds, he was caught cheating and in many of his other rounds, he had suspicious submission times and different coding styles in the same round.

However, in yesterday's div3 round, he ended up using a solution for 1996E - Decode which was used mostly by cheaters who were given this code by someone in order to catch them off guard (there was an obvious wrong case when the answer was actually mod-1 and they printed -1, with respect to the modulo, due to adding a +1 at the beginning and removing it at the end without actually knowing what the code is doing 272757058), as shown in this 272834543.

What does this tell us about the current problem setting system

While I acknowledge that there are things which can't be improved fast, due to a relative understaffed coordinating team, I think something which can be improved, and it is about time for such a post, is to have a clear and more transparent version of the ruleset regarding setting rounds, waiting in the queue and the coordinators responsible with each division, as according to my knowledge, at least when it comes to div3 and div4, the system is not explained anywhere, and for div1 and div2 rounds, there is the old system which seems to not work that well anymore.

Personally, I would also argue that the system of becoming a coordinator should also be more transparent, as I'm sure there are people who would love to help with that but they don't know where to reach out to or even worse, they are too shy to just DM someone from the Codeforces' staff for that (which according to my knowledge, it is the current state of affairs).

In addition, I think given that we have now several rounds where cheaters author problems, plus the rather frequent occurrence of them being among testers, who can later leak problems, something must be done about this.

I want to thank errorgorn, defnotmee, chromate00 and TheScrasse for reviewing the blog and adding more evidence.

Hello all,

Recently, while looking at interesting problems I can assign my students to solve, I found this CSES problem — Xor Pyramid which to my surprise I didn't see it covered anywhere lately even though it's in my opinion quite a beautiful problem with a short implementation, so I decided to make a video solution for it, which can be found here.

At first, it seems very hard to approach it faster than building the entire pyramid in $$$O(n^2)$$$ but after thinking at various observations related to how XOR operation works, as well as recalling a similar approach used for the same problem's SUM version, we can come up with a very short and in my opinion, beautiful idea.

The main idea is to observe that each of the numbers from the bottom row of the pyramid has a certain contribution to the final XOR sum, and similar to how you would compute the actual sum of the values, we can see that the contribution of the values on the final row is equal to the $$$n_{th}$$$ row of Pascal's triangle, and thus we can reduce the problem to finding the parity for each value from this row (even contributions cancel out when it comes to XOR operation).

In order to compute this fast, we will have to precompute for all factorials up to $$$n-1$$$ the exponent at which $$$2$$$ shows up in all factorials and now we will rely on the well known formula for combinations in order to find the final exponent at which $$$2$$$ shows up in the contribution for each of the numbers in the array.

Thus, we managed to solve a seemingly complicated CSES problem using a beautiful solution with only around $$$10$$$ lines of code. Please let me know what you think and I am curious to find out what other problems or techniques should I cover next.

Hello all,

While waiting to submit my solution for last div3's G, I realized that the system tests last way more as of late in div3, div4 and educational rounds. System tests started around 5 hours ago and we are only around 00:50 into the contest, as of the time I am writing this blog.

Although some of the difference is caused by the ever increasing number of contestants for these rounds, this still doesn't explain what seems to be the huge downgrade of the judging servers. From my memory, this phase used to not last more than 1h, maybe 2h in exceptional cases.

Educational Codeforces Round 166 (Rated for Div. 2) System tests lasted around 5 hours

Codeforces Round 946 (Div. 3) System tests lasted around 3 hours

Codeforces Round 944 (Div. 4) System tests lasted around 8 hours

Codeforces Round 943 (Div. 3) System tests lasted around 3.5 hours

Here is a series of 4 contests around 1 year ago

Codeforces Round 898 (Div. 4) System tests lasted around 2.5 hours

Codeforces Round 895 (Div. 3) System tests lasted around 2 hours

Educational Codeforces Round 154 (Rated for Div. 2) System tests lasted around 1 hour

Codeforces Round 894 (Div. 3) System tests lasted around 30 minutes (Probably due to few hacks)

While this is usually not a huge problem, it can lead to situations where in case of back to back rounds, people get assigned to wrong divisions and in general it leads to an annoying experience for the users.

As some suggestions, maybe the hacking phase can be reduced to 8 hours so that the system tests can be hold around what would be early morning in Europe, when the user activity is the smallest? I guess another option would be to be more selective as far as hack tests go so that we don't see 100 tests which test the same thing (i.e: unordered map hacks in the case of this round)?

I think finding some solution to this problem is very important for the purpose of future rounds.

UPD: Codeforces Round 964 (Div. 4)'s system testing beat all the records with over 10 hours, as shown by these judging times from my friends' submissions 274711443 and 274945800, however Div. 1 and Div. 2 rounds seem to generally have reasonably fast system tests, does anyone know why is this the case?

Even if it takes you 7 years to upsolve a problem, there is no point in not doing it eventually.

Hello Codeforces,

Today I'm going to talk about something that is often overlooked in competitive setups in academics and especially STEM, which is Mental Health. During my competitive years and my life, I often felt very bad about where I was standing and looking back, I realize that things could have gone much better for me if I were to take the right steps.

Over the years, I developed pieces of advice that can help you overcome these issues and while it is not by any means professional advice, it can be very helpful as far as managing the stress of competing at the very top goes. It is something I give a lot of importance to nowadays when coaching people or when I give people advice in general.

Here is the link to the video.

I would also like to thank everyone who helped me made this video, by listening to my ideas and sharing their stories, which helped me tell things from a broader perspective as far as this topic goes. Their support has been invaluable and I am forever grateful to them opening up, since this can be something very difficult to do nowadays.

I hope you find the video useful and let's have a meaningful discussion about this topic, because I believe we as a community can do so much better than the increasing toxicity that has been noticed by many other people before me, including numerous blogs and commenters.

Info1Cup, the first junior olympiad of 2024 is starting today with its competition days taking place tomorrow and on sunday.

I invite you all to write the codeforces handles of the participants and maybe even predict potential winners or high performers.

After the contest days, let's also discuss the problems here.

Good luck to all participants.

UPD1: The first day should end anytime from now, so let's discuss ideas for the problems that were given.

UPD2: The second day should end anytime from now, so let's discuss ideas for the problems that were given.

Congratulations to everyone and especially to the winners.

Here are the results: Link

Hello Codeforces,

I am happy to invite you all to the Runtime Terror 22105 Coding Competition, a competition organized by the FTC team Runtime Terror #22105, competing in the United States FTC Robotics Competitions and myself. This competition is open to everyone who wants to join, but only pre-collegiate students who are in USACO Gold or below are allowed to compete for the financial prizes, which will be available for top 5 contestants.

I am happy to have sponsored and coordinated their efforts and I can assure you that the contest will be an interesting one. The tasks have been written by BearytheGreenBear, THE_GOAT_coder and myself, stefdasca.

The competition will have 6-8 interesting problems which will be suitable for contestants ranging from USACO Bronze level to USACO Gold level and the contest will take place on Codeforces, with more details coming up on the discord server of the competition. The tasks will have partial credits for various solutions found.

If you want to take part in the competition, you should both complete this google form as well as joining our Codeforces group, here is a link for the group.

The contest will take place on Saturday, 3rd of February, from 4:15pm to 7:15pm PST. You can check your timezone equivalent in the link here [contest_time:502499].

If you want to follow the team, please check out their social media links down below:

Team's Instagram page

My website

Support the team here (any small amounts go a long way for them!)

Thank you for your interest and we are looking forward to see you all compete and win!

Since the editorial is still unpublished yet as I was writing this blog, I decided to write an editorial for the problems that were given at yesterday's contest. For tasks A-E I also published video editorials (A-C, D-E)

1922A - Tricky Template

In order to solve this problem, we must observe that each position is independent from each other and it is enough for us to fix only one position in order to see if we can get both $$$a$$$ and $$$b$$$ match the template while $$$c$$$ doesn't. Thus, it will be enough to check if $$$a_i \neq c_i$$$ and $$$b_i \neq c_i$$$ for that to work, as we could then put an uppercase letter and discard $$$c$$$ right away.

Solution code: 242416975

Video editorial: Link

Alternatively, this can also be done in a much more complicated fashion with bitmask dp where $$$dp_{(i, j)}$$$ is $$$1$$$ if we can get a configuration up to position $$$i$$$ such that strings with mask $$$j$$$ match the template, and the answer is YES if $$$dp_{(n, 6)}$$$ is $$$1$$$.

Bitmask dp solution: 242442065

1922B - Forming Triangles

This problem is based on a very standard problem, which is finding the number of triples that form a triangle. While the original problem is solvable using binary search in $$$O(n^2 \log n)$$$, given that here we have powers of two, we can find an important observation that allows us to reduce the complexity. Namely, we can never have three distinct lengths of sides as this would make the triangle invalid.

In addition, the two equal sides can't be smaller than the third one too as this would also make the triangle degenerate (for example, $$$2^2 + 2^2 = 2^3$$$). Therefore, the equal sides must be the larger ones. Now, we reduced the problem to two cases:

• When all sides are equal, we can just sum up the values of $$$\frac{freq_i \cdot (freq_i - 1) \cdot (freq_i - 2)}{6}$$$ ($$$n$$$ choose $$$3$$$) and that would be the answer.
• When two sides are equal, we can just sum up the values of $$$\frac{freq_i \cdot (freq_i - 1) \cdot sum}{2}$$$ ($$$n$$$ choose $$$2$$$) where $$$sum$$$ is the sum of the frequencies of the smaller sides and that would be the answer.

In order to find the final answer, we can sum up the answers for the two cases which can be speed up using prefix sums.

Solution code: 242416552

Video editorial: Link

1922C - Closest Cities

The worst case answer for each query is the distance between the two values, but we now want to find out for each query how many times we can reduce the distance by using the $$$1$$$ instead of the actual distance.

Given that the distances never change and it is never optimal to turn back on our journey, we can precompute this information for all suffixes and prefixes in a prefix sum-like manner and this will help us answer the queries in $$$O(1)$$$ time.

Solution code: 242416485

Video editorial: Link

1922D - Berserk Monsters

Let's analyze what happens on a round by round basis. If there is no monster who dies, nothing will change anymore and we can finish the game. Otherwise, let's take the monsters that die and find for every monster next to them the new neighbors.

This will be the basis behind implementing the solution for the problem, as we need to simulate the process fast enough. In order to avoid the $$$O(n^2)$$$ complexity, we need at each step to only deal with the monsters that were killed in the previous round and the adjacent monsters, in order to see if there are any new monsters that could die in the next round. In order to keep track of the new adjacent monsters, we can either use sets or use a linked-list like approach, where for each position we store the previous and the next value, and when we kill monster $$$x$$$, if we knew $$$prev_i$$$ and $$$nxt_i$$$, they will become the new previous/next for each other now.

The solution can now be implemented in $$$O(n \log n)$$$ or $$$O(n \log^2 n)$$$.

Bonus: can you solve this in $$$O(n)$$$?

Solution code: 242417965

Video editorial: Link

1922E - Increasing Subsequences

Let's start from a very important observation. Every increasing array has all of its $$$2^n$$$ subsequences increasing, where $$$n$$$ is the length of the array. Therefore, we can start the solution with an array like $$$1 \ 2 \ ... \ \log n$$$, which will have $$$2^{\lfloor \log n \rfloor}$$$ increasing subsequences. Now, in order to continue creating subsequences, we can basically rely on the binary representation of $$$k$$$ and if at some step we add $$$2^x$$$ subsequences, we can append at the end a value equal to $$$x+1$$$. Now, we need to be careful to add the new values in decreasing order in order to avoid generating new subsequences.

The final complexity will be $$$O(\log K)$$$ as we need to find the powers of two to add to the array.

Solution code: 242418015

Video editorial: Link

1922F - Replace on Segment

Credits to Dominater069 for writing this solution

In order to solve the problem we can use range dp, but the way to think about it is not very obvious at the first glance. While it seems somewhat obvious that we need to do something around this concept, the states are not very easy to define.

As we usually go about in range dp, assume that we know the answer for a range $$$[l, r]$$$ and try to update larger ranges using smaller ranges information. Let $$$dp_{(l, r, k)}$$$ be the minimum number of moves we need in order to make every value in the subarray $$$[l, r]$$$ equal to $$$k$$$. Now, again using standard range dp thought process, in some optimal solution for a range $$$[l, r]$$$, we divide the subarray into $$$2$$$ parts (namely a prefix and a suffix) where we do not overlap prefix and suffix operations, with the exception of using an operation on the whole subarray $$$[l, r]$$$.

Now, here is finally the slightly tricky part. It's not possible to tell whether we can operate on the whole range $$$[l, r]$$$ with just our $$$dp_{(l, r, k)}$$$. So, we define another auxiliary dp state, let $$$dp2_{(l, r, k)}$$$ be the minimum number of moves in order to make every value in the subarray $$$[l, r]$$$ not equal to $$$k$$$. Transitioning for splitting the subarray into $$$2$$$ parts is simple and standard. Assume that we now use an operation with set to $$$x$$$ for the subarray $$$[l, r]$$$. Then, we need to update $$$dp_{(l, r, x)}$$$ and $$$dp2_{(l, r, y)}$$$ with $$$dp2_{(l, r, x)} + 1$$$ (if $$$y \ne x$$$). Implementing these transitions directly, we get a $$$O(n^3 \cdot x)$$$ solution, which is sufficient to pass comfortably.

Dominater069's solution code: 242258097

Hello everybody!

This year I decided to be way more active as far as posting educational content goes so I decided to start with posting video tutorials for as many problems from the CSES problem set as possible, as there are many videos out there which often explain solutions by going through way more details than needed or simply make understanding the problem way more complicated than needed.

Here is a playlist with the solutions I did so far, with the most recent addition being Tree Distances I, a problem I reviewed today in this video.

In order to know what should I focus on going forward in terms of educational content, I would love and be grateful to hear in the comments about topics or problems from CSES or from other places (I prefer more well known/educational ones however) you think they're worth reviewing. I will try to do 2-3 videos a week with the most upvoted comments and I will keep the blog updated as I keep posting solution videos over time.

Here's to a great 2024 and if you find my tutorials interesting and worth watching, you can subscribe to my channel for more content in the future.

UPD: I just uploaded a video solution to Polynomial Queries from CSES. Thank you maxrgby for your suggestion!

UPD2 new video: I just uploaded a video solution to Multiplication Table from CSES.

If you want to suggest more videos, be ready to do it in comments, I want to upload as many solutions as possible. In addition, any feedback is much appreciated as well.

Here is a playlist where you can watch all solutions I posted so far.

Have you ever wanted to know how will your CF rating look like in the future, without having to be stressed about the potential shortcomings which may come in future contests?

Have you ever wanted to be able to say that you will get the rating of your dreams soon?

If the answer for both of these questions is Yes, then you once again came to the right place.

Over the last three years since I posted the first such blog , everyone wanted to learn how will their CF rating look like in the future and I got such questions pretty much everywhere I could possibly get, including but not limited to:

• replies to comments I made here
• DMs here, on Discord and even on other social media platforms
• replies to messages on Discord
• even when I met people during onsite contests

As a result, exactly three years after the first iteration of the blog, I decided to come back with a second edition of this blog, where I am using my now three more years of experience in predicting ratings and studying how people will evolve in the future, solely by looking at their charts.

Since images are often worth 1000 words, you can notice the high rate of success I had when I first did this and the relentlessness with which people asked for a part 2 can tell you everything you need to know about how popular this idea is (someone even made a tool for something like this as a result of this blog). Even before writing this blog, I had people asking me about this so you can tell how popular this is.

If you want to know how will your(or your friends') CF rating will look like, post the handle in the comments or an image of the rating graph and I will come with a reply as soon as possible.

However, this system only works for users with at least 15 contests taken and whose ratings are below 2600(from 2600 on, large swings happen and I can't really consider them as relevant in those persons' future skills)

Even if my predictions won't please you, you can look at my channel and my website for ways to make even the most negative predictions fail. After all, they only indicate how well you do based on the charts, without reflecting any kind of practice strategy or anything.

Good luck and I wish you nice holidays and a wonderful 2024!

Hi Codeforces!

Lately I've seen a few people in the communities I follow create their own competitive programming tier lists based on the tier maker below, so I decided to give it a try too. As it would've been too long of an entry to write my opinions here, I decided to make a video about this and you can watch it by following the link here

While the video itself is a bit long, I had lots of fun creating it and I even had the chance to cover some insights about the various techniques presented which should be educational as well.

I hope you enjoy watching and I am curious to see how do your tier lists look like as well.

Have fun with the tier list and let's see how things go!

The tier list

Recently, the 2023 edition of the Romanian Collegiate Programming Contest took place in Iasi as part of the RCPCamp, an international ICPC camp organized in Romania by the Alexandru Ioan Cuza University of Iasi (UAIC).

I had the opportunity to coordinate RCPC this year and as the contest turned out to be an interesting and a challenging one, I posted the contest yesterday on gym. The contest can be accessed here.

The problems were created and prepared by RedstoneGamer22, anpaio, LucaLucaM, caheman, andrei_C1, divad and me.

I also thank pauldiac for giving us the chance to set this contest as well as Alex_Vasiluta for the Kilonova platform we used for holding the contests on both days of the camp.

I hope you find the contest interesting.

Until the other contest will be added on Gym too, you can access both of the problemsets here:

Day 1

Day 2

UPD: The ghosts were added too to resemble the results of both online and onsite participants.

Hello Codeforces,

On behalf of the international scientific committee of IIOT, we would like to invite you all to the mirror of the international round of this year's IIOT, contest which took place in Egypt.

You are given 9 problems and 4 hours to solve the problems and it is recommended to solve the problems in teams of up to 4 members.

The contest is organized with USACO-like rules, as the mirror lasts until 7th of June, 23:59 UTC+3 and you can choose a window of 4 hours to solve the tasks together with your teammates. You are limited to 30 submissions per problem and the scoring style is the same as in OI (each problem has 100 points and there are subtasks for each problem as well).

The link of the mirror is here.

Thank you and we are looking forward to see you join the contest.

UPD: The tasks are also added in the archive for upsolving: here

Hello Codeforces!

I tested this contest and I found it of a high quality especially for the div2/div3 participants, and at the request of the organizers, I am sharing the announcement in order to promote it here. The announcement starts below.

Hi all! This is slightly short notice, but if you are interested in a great challenge, you should definitely sign up!

The Indigo Coding Competition will be happening tomorrow on Saturday, April 15th, from 4:30 to 7:00 PM EST! and it will be held on HackerRank.

In order to participate, you need to complete the google form and check out the information from the contest website.

Designed and organized by high school and college students from Indiana, this contest is great for beginners, advanced programmers, and all in between. Anyone can participate and there are prizes worth $700+ for the winners who are in pre-college, but also raffle prizes.

This is a great opportunity to code with friends (you can compete individually or in pairs), meet new people, solve some cool problems, and have fun! If you're interested, check out the website and join the discord server.

We look forward to seeing you there!

Hello everybody!

As you already know, some high profile competitions, such as GCJ and TCO have been officially discontinued and there is clearly a lack of competitive programming contests with awards for the very best performers.

Given the size of the community we have here on Codeforces and on other places too, I think we can use our expertise and our networking to create a new series of competitions (and possibly in the future an organization to help competitive programming grow worldwide) to make up and even pass the existent competitions in prestige and awards. After all, the platform which will be used won't even matter that much, as I see it as a team effort to bring competitive programming to a higher standard in terms of prizes in competition.

For example, Codeforces got $125k when people donated for the 10 year badge, which is a lot of money used for expenses such as keeping the servers up, paying problem setters and paying the employees, among others. In my opinion, such a sum of money could help the community run a series of more highly respected competitions to award the best performers for a few years, while also helping communities grow.

Even though there is an economic downturn going on, I'm sure there would be a lot of interested firms in donating even sums such as $1k or even $500, plus as I showed with the Codeforces donations, a lot of individual donors. It doesn't take a lot of donations to at least make up for what was lost as a consequence of losing GCJ and TCO on a yearly basis.

Also, if competitive programming turns out to be more and more popular (that might require some format changes IMO), the income streams would also grow and this could only turn out to be more beneficial for the entire community.

I am aware this would mean a lot of organizing work and this is why I believe working as a team would help us achieve this goal, assuming it is something the community wants.

What do you all think about this idea? Do you think it has any potential to succeed?

I am looking forward to any potential suggestions on how to make things better from this perspective.

Let's have a debate on that and if things go well, maybe even start a conversation in a more organized way to get things going.

UPD1: My starting idea was something based on Titled Tuesdays from chess.com or Titled Arenas on lichess, if that helps. In short, we could organize biweekly or monthly contests with awards for the best performing contestants.

UPD2: I created a Discord server where we can discuss the ideas based on the blog and the comments added by people here.

Hello Codeforces.

As you know from one of my previous videos from my YouTube channel , I am offering individual tutoring classes to students interested in getting better at competitive programming while also offering an innovative and customized tutoring program, adapted to their always changing needs in terms of improving their competitive programming performance.

However, there are so many more people who were interested in joining those classes but because of various reasons, they couldn't have classes with me and this is something I want to address with this blog post.

Lately I have been thinking at organizing group classes where I can teach various topics and guiding the group towards getting better, based on their common need, thus adapting two of my main principles when it comes to tutoring. I am looking to have a few group classes during each week.

Some of the ideas I have been thinking at were either creating classes on one demanded topic (for example, a Dynamic Programming series of classes) or creating a series of classes oriented towards people with similar skill levels, which would help them become better at the algorithms and the data structures they need in order to be able to make the push towards the next level in their competitive programming journey.

Another benefit of the group class would be that it will be more affordable than having a one-to-one tutoring program, but this also comes with the price of not being able to get fully customized help as a student.

If you are interested in joining those group classes or if you have anything else to suggest regarding the way I should conduct these classes, you can add a comment to this post, write a private message here on Codeforces or on Discord (username: stefdasca#0001). Based on the popularity of this blog post and on the amount of interest I get, I will keep working on these group classes and I will provide more detail with the way they will be conducted.

Thank you for your continued interest in my work both as an Youtuber (thank you for helping me get 4000 subscribers there) and as a tutor and I am looking forward to getting as much feedback as possible and future students for the group classes too.

UPD1: The group lessons will be topic based and you can join any class you want, and I will announce the schedule beforehand. More details on the Discord server https://discord.gg/9ysRZcmB

Hello everybody!

One year ago, I posted the first tutorial video on YouTube, and while many things have changed since then, me and my channel have stayed here, and in this video I am talking about my journey as an youtuber as well as about my journey as a competitive programming after I finished competing actively, like I used to do it in my high school days.

Here is the video

Here is the link for the Discord server.

Thank you for watching and I am really grateful for your support during this time.

Hello everybody!

It's been a while since I last posted a video tutorial, and since the previous one received a really positive feedback, I decided to create another tutorial. Since it's generally a data structure which isn't that loved by many competitive programmers, and it has also been suggested by many people in my Discord server, I decided to create a detailed video tutorial about Fenwick Trees.

I explained everything about Fenwick Trees, starting from basics and going all the way to the less well known optimizations, as well as explaining when Fenwick Trees are useful and why should they get more love from the community.

Here is the video

As always, if you have constructive feedback, please share it in comments or in the Discord server.

Thank you for watching.

Good afternoon, Codeforces.

Recently, I tried to add some bigger testcases manually in Polygon and it seems like I'm getting this error whenever I'm uploading something bigger than 1MB.

Is there something which could be done about it? I never had this issue before, so I guess it probably has something to do with the recent maintenance Polygon went through.

Thanks in advance.

MikeMirzayanov

Have you ever wanted to know how will your CF rating look like in the future, without having to be stressed about the potential shortcomings which may come in future contests?

Have you ever wanted to be able to say that you will get the rating of your dreams soon?

If the answer for both of these questions is Yes, then you came to the right place.

During the last few months, I have used some technical analysis to predict how will some of the people from my Discord server and I have gotten quite consistent results, so I think that my strat is working.

I am not going to enter in details on how do I actually do this, because it requires quite some experience to learn all the details, but as people say, an image is worth 1000 words, so here are some few examples.

First example is ScarletS

Here is how his rating looked like in November, before he had a bad contest

Here I told him that he will fall a bit and the chance for him to rise again is high, and that's what happened

As you can see, a great example of a trendline which held. Hopefully he will keep his uptrend and reach new highs :)

The second example is lookcook

In early December, I told him that he has to be careful at the next contests otherwise bad things can happen

Sadly for him, the rising wedge is starting to play out and he fell to blue

I wish him to make this bearish pattern fail and reach new highs as well, since after all, this is just technical analysis.

Another example is rotavirus

In August, I saw this potential head and shoulders pattern in his chart, which would lead to a downfall.

Sadly for him, this played out too and he fell quite a bit, down to 2100, but hopefully he will rise again as well

However, this doesn't always work, as you can see in Java's graph

I predicted a move up to 2050, based on the previous range(1730-1880) but it didn't work out

Aftermath

I wish him good luck in actually reaching that target.

If you want to know how will your(or your friends') CF rating will look like, post the handle in the comments or an image of the rating graph and I will come with a reply as soon as possible.

However, this system only works for users with at least 20 contests taken and whose ratings are below 2600(from 2600 on, large swings happen and I can't really consider them as relevant in those persons' future skills)

Good luck and have nice holidays and a wonderful 2021!

Hello everybody!

Since it has been suggested by many people in my Discord server, I decided to create a longer and more detailed video tutorial about the Knapsack problem.

Because there are many such tutorials online, I have also added more advanced Knapsack variations, including different types of tricks and usages of this DP technique in the problems.

Here is the video

As always, if you have constructive feedback, please share it in comments or in the Discord server.

Thanks for watching.

Hello Codeforces!

I have been asked by people in my Discord server and on my YouTube channel to explain my approach for F, and in my opinion, it ended up being an approach worth of writing a separate blog for it, since it's a bit different from the editorial approach and also more intuitive(at least in my opinion).

My solution is slightly different from editorial's, and it relies on using the problem constraints and also on the fact that we only have to respect one of the errors to get a correct verdict, as I'm going to show below.

We will also start from the well known divisor formula:

$$$n$$$ $$$=$$$ $$$a_1^{b1}$$$ $$$*$$$ $$$a_2^{b2}$$$ $$$*$$$ ...$$$*$$$ $$$a_k^{bk}$$$, the number of divisors is $$$(b1+1)$$$ $$$*$$$ $$$(b2+1)$$$ $$$*$$$ ... $$$*$$$ $$$(bk+1)$$$.

Basically, the solution is made of two parts. The first part consists in grouping the prime numbers up to $$$677$$$ in groups such that their product does not exceed $$$10^{18}$$$(the biggest number I could get to by grouping the primes in increasing order, this bound can definitely be made bigger by grouping the primes in a better way, however this is not necessary for this task). Why $$$677$$$? Because grouping requires $$$17$$$ queries, which leaves us with $$$5$$$ more queries to use.

Now, using these $$$17$$$ queries, we can find which queries up to $$$677$$$ show up in the number's prime factorization(For now, we don't care about the power at which they show up, we just want to check if they show up or not). In order to do this, for every prime in the current group, we're going to check if the obtained $$$GCD$$$ divides that prime and add it in an array of prime divisors. Since the product of the first $$$10$$$ primes already exceeds $$$10^{9}$$$, this means we're going to have at most $$$9$$$ primes in the number's factorization.

Since we can ask $$$5$$$ extra queries, we can find the exact power at which each of the smaller primes in factorization shows up at. In order to do this effectively, we will group primes in pairs of two and create some big numbers like this, where $$$a$$$ and $$$b$$$ are prime numbers:

Let's note $$$floor(\log_a 10^9)$$$ with $$$pa$$$ and $$$floor(\log_b 10^9)$$$ with $$$pb$$$

Then, the number will look like this $$$a^{pa}$$$ * $$$b^{pb}$$$.

This number won't exceed $$$10^{18}$$$ and by using GCD, we can find for each power at which it appears in the given number.

After finding the powers at which the smaller prime numbers appear in the given number, all we have to do is print the answer. I'm going to show that it's enough to print $$$max(ans+7, ans*2)$$$.

Why does $$$max(ans+7, ans*2)$$$ work?

My method can miss at most three factors, let's note them $$$p$$$, $$$q$$$ and $$$r$$$(they have to be distinct in order to get us the worst case, according to the divisor formula). Also, they have to be bigger than $$$677$$$ in order to get them missed in my solution. There can't be $$$4$$$ big missed factors because $$$677^{4}$$$ is way bigger than $$$10^{9}$$$.

If I don't miss any prime factor, printing $$$ans*2$$$ is fine, since the relative error will be $$$2$$$ $$$(\frac{ans}{real ans} = 2)$$$

If I miss one prime factor, then printing $$$ans*2$$$ is actually the correct answer.

If I miss two prime factors, printing $$$ans*2$$$ will give a relative error of $$$0.5$$$, which is also fine.

If I miss three prime factors, printing $$$ans+7$$$ will be fine, since the maximal number of divisors for some number of type $$$X * p * q * r$$$ is $$$16$$$ (We can have at most one extra prime factor without passing $$$10^{9}$$$, and in the worst case, ans will always be $$$1$$$, and the relative error will be $$$0.5$$$, which is fine enough.

Also, printing at least $$$8$$$ every time ensures that I will never miss any number with divisor count in range $$$[1, 16]$$$.

Therefore, I managed to get AC using this method. Sadly, I got WA in system tests because I printed $$$ans*2$$$ instead of $$$max(ans+7, ans*2)$$$ in the last case I talked about in blog.

Submission link: 80521041

I hope you enjoyed reading, even though it's quite a long editorial.

Given MikeMirzayanov's Div 4 contest announcement and Errichto's suggestion for lower bound for Div 2, I decided to come up with some ideas to further improve this update.

Firstly, I'd like to say that Div. 4 contests are a great addition for people who have absolutely no idea about competitive programming and the ability of being able to solve more than just one problem will definitely make new people more confident when it comes to problem solving.

However, this change will definitely bring lots of new contestants to Codeforces, and some measures will have to be taken in order to deal with the new change.

As Errichto suggested, a rating lower bound would be beneficial because it partly solves the rating inflation and also because it will generate less queue.

Starting from this point of view, I'd like to suggest further improvements which can be made in order to make the platform even better:

1) Since we have parallel div1/div2 rounds, maybe we can also have parallel div2/div3 and maybe div3/div4 parallel rounds as well. Obviously, some lower bounds will have to be implemented, but this is not much of an issue, because the current lower bounds for colors should make the splits easy to implement.

2) Maybe let other people become problemsetters for div3 as well, there are plenty of people who want to become Codeforces problemsetters but maybe their tasks are not considered good enough for a div2 round because of one reason or another. Since div3 tasks are meant to be more standard, the problemsetting criteria can be less harsh.

3) Given the recent inflation of ratings, which is also a problem and if none of these suggestions will be implemented, this is going to become a major problem, since one can become purple with div3 rounds(look at andryusha_na_knopke for proof), maybe also change the color thresholds for each color.

What do you think about these possible new changes, would they be useful to make the Codeforces experience even better in this era of dramatic growth? I'd like to see your opinions in comments.

Hi!

Since i'm getting close to 1k subscribers, I decided to do a livestream where I will do various CP stuff to celebrate the first such milestone for me.

Stream link

Channel link

Discord server

Have fun!