### stefdasca's blog

By stefdasca, history, 13 days ago,

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.

MikeMirzayanov

• +83

By stefdasca, history, 2 months ago,

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!

• +368

By stefdasca, history, 3 months ago,

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.

• +95

By stefdasca, history, 9 months ago,

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.

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

• +33

By stefdasca, history, 10 months ago,

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.

• +149

By stefdasca, history, 10 months ago,

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.

Discord server

Have fun!

• +94

By stefdasca, history, 11 months ago,

Hi!

Since the editorial will be posted later, I decided to write some quick solutions for the problems I managed to solve, as well as video editorials for C and F.

A - Little Artem

Add $W$ on $(n, m)$ and $B$ on all other squares, we will have two black squares bordering one white square, which is good enough.

B - Kind Anton

If $a_i$ $=$ $b_i$, do nothing. Otherwise, if $a_i$ $<$ $b_i$, check if we had some $a_i$ equal to $1$, otherwise, check if we had some $a_i$ equal to $-1$, this information can be kept while we iterate through the elements.

Total complexity: $O(n)$.

C - Eugene and an array

Video Editorial here

D - Challenges in school №41

Simulate the bubble sort algorithm(assume characters equal to $R$ are $1$ and characters equal to $L$ are $0$) and keep track of steps done. If we have done less swaps than $k$ or we can't finish the algorithm in at most $k$ days, the answer is $-1$.

Otherwise, we are going to greedily unify swaps from the same day in order to finish the algorithm in $k$ days.

Total complexity: $O(n^2)$.

F - Kate and imperfection

Video Editorial here

• +50

By stefdasca, history, 11 months ago,

Hi!

Here I'm going to keep updated the list of Problems of the Day I'm going to make a video editorial for.

Day 1
Day 2
Day 3

If you want to be the one to have its problem as the new POTD, join my Discord server and suggest any problem you want, as long as it's solvable by me :D

Have fun!

• +101

By stefdasca, history, 11 months ago,

Hello!

The first problem of the day is a div2F from a recent Codeforces Round, please check it out!

Video

Discord Server

You can join the server in order to suggest new POTDs, and subscribe to the channel for more content!

• +38

By stefdasca, history, 11 months ago,

Hi!

Since we're all staying home, I decided to come up with a way to spend our time in a more pleasant way.

At the beginning of each day, I'm going to post a problem on my Discord server and in the evening, I'm going to post a video editorial to that problem.

Below you will find the video for the first problem of the day!

The problems will have ratings between 0 and 2400, and you have the possibility to choose the next video editorial, as long as the problem is interesting enough!

Have fun!

• +102

By stefdasca, history, 11 months ago,

Hello Codeforces!

I decided to finally do a screencast and a full editorial, hope you'll enjoy watching.

Screencast

Video Editorials

Discord Server

• +17

By stefdasca, history, 11 months ago,

Hello!

Since the editorials are still not out, I prepared video editorials for div2 B, C and D.

B

C

D

Check the videos and if you liked them, subscribe to the channel for more CP content

• +105

By stefdasca, history, 11 months ago,

Hi!

While I was solving some National Olympiad problems, I came up with an interesting DSU trick which can be used instead of Parallel Binary Search.

Now that I started an YouTube channel, I decided to make a video based on it.

If you enjoyed watching, please leave a like and press the subscribe button.

Also, if you know the name of this trick, please share it here or on Youtube comment section.

• +152

By stefdasca, history, 11 months ago,

Hello!

I just uploaded a video about my opinion when it comes to approaching Codeforces contests.

Here

Everything I said is just the result of my personal experience with doing contests and I hope you liked my content.

You can also join my new discord server where I will interact with the subscribers and also with those interested in algorithmics.

Here

• +119

By stefdasca, history, 11 months ago,

Hi guys, I hope you're all staying home safe from COVID-19.

I decided to start an youtube channel where I'm going to explain various problems, both in English and in Romanian.

The latest video, where I'm trying to solve a div1B from a recent Codeforces Round

Even though I'm just a beginner when it comes to doing such content, I will definitely improve as time goes by.

You can leave suggestions in comments and subscribe to the channel, if you enjoy the content.

I hope you'll enjoy watching those tutorials.

• +114

By stefdasca, history, 16 months ago,

The registration for the next Div3 is restricted to people with rating lower than 1600, and this shouldn't be the case, since Div3 contests allow out of contest participation.

• +60

By stefdasca, history, 19 months ago,

It seems like uphacking is affecting rating changes, this shouldn't happen.

rip fishy

• +156

By stefdasca, history, 20 months ago,

Hi, Codeforces!

I've observed that in the last several months, I haven't managed to achieve a significant progress in average rating on CF and i started to worry whether I touched my peak potential or not, so I came here to ask you some questions. I know it's a debated subject, yet I still think it's sensible to talk about this, so I came up with some questions I still haven't found a clear answer to.

1) When do you believe one has touched his/her peak(bonus points if you're talking about yourself)?

2) If you ever believed you're stagnating, how did you change your way of practice and why?

3) Do you think that everyone has its maximal potential? No matter what do you believe, I'd like to see you state the reasons why you believe/don't believe everyone has a maximal potential.

If you have tips to counter this problem, please share them here, they will help me and many other people now and in the future.

• +245

By stefdasca, history, 23 months ago,

Hi everyone!

ICPC World Finals 2019 are approaching and we're proud to announce that we're going to be a discussion place for all those who have qualified to the World Finals.

If you are one of the finalists, you can join our server to take part in the special ICPC World Finals chat.

Good luck and have fun!

• +29

By stefdasca, 2 years ago,

Codeforces's virtual contests are probably one of the best feature in CP, since it allows people who can't do the contests because of various reasons to have a chance to simulate the contest. However, the virtual contest format doesn't consider the fact that the real contestants had pretests and system tests, while in a virtual contest, the source gets evaluated to all the tests in the moment of submission.

So, I suggest that the virtual contestant should be able to choose whether he wants to get his solution tested only on pretests(just like in the real contest) or to have full feedback(the current format of VC as of now). I don't think this isn't that hard to implement, CF can probably still evaluate all the tests and show "Pretests passed" if the source passed a certain test number(the number of pretests which this contest had).

I think this is a problem which concerns most of the people who are using the virtual contest feature, so fixing this problem would improve this feature significantly.

• +202

By stefdasca, history, 2 years ago,

Ever since tzuyu_chou started advertising Twice at round #497, an increasing number of people have got to hear about this band, and it seems that for most of them, it was a great deal in their competing skills.

Even though at first I was reluctant about how can a K-pop band, especially Twice can improve people's CP skils, but after seeing that many guys with K-pop related accounts performing great made me start listening to Twice too and soon after this, I managed to get Master for the first time ever, after struggling in purple for a long time.

The examples can continue, so is listening to Twice really boosting cp skills?

I'd like to hear other successful stories too, so that i can be sure that my skill gain is not just a result of hard work.

• +178

By stefdasca, history, 2 years ago,

Hello Codeforces!

As i randomly observed by reading an editorial blog, when i searched for contests done by same author, there was shown a contest which seems to have no link to that user

The author shown

Announcement blog, totally unrelated

Editorial blog, totally unrelated

However, div1 version is correctly attributed to the actual author

As you can see, author's name and the actual writers have no link to each other, unless i missed something which is not shown in any of the announcement or editorial. Will this be fixed?

• +32

By stefdasca, history, 2 years ago,

Hello Codeforces!

I've been a member of this community for about 1 year and i'm very glad of how things go there, with a single exception: Educational Rounds.

Ever since they became rated for div2 users, despite of their rather interesting format, they've proved to be a trap for many users, because of hacking period and contest format(extended ICPC). Basically, as a result, in 99% of situations, problem A, which is supposed to be the easiest one, becomes the most important problem, and this is not exactly good, because in many situations, people who have, let's say ABCD and a rather good penalty, end up getting only BCD but with a bad penalty for 3 problems, just because of a single mere error, while in any other contest they would only have gotten a small drop in standings.

Thus, my humble suggestion is to rethink a bit how Educational Rounds(and any ICPC style contest in CF with sorted difficulty problems, like div3 rounds) are working.

One of my ideas is to add weight to each problem, so instead of each problem having the same value (another point on number of problem solved), we can have something like A = 1, B = 2, C = 3 and so on, thus while still advantaging people who did ABCD, it will not hurt people who did something like BCD so much anymore.

Another idea i have thought at is while keeping the current system(people ranked by number of problem solved and penalty), we can add another criteria of separating people's ratings.

For example, a person who solves ABCDE should be better than a person who solves even DEFG, but a person who solves ABCD shouldn't be better than a person who solves, let's say, ABCE

What do you think of those ideas? Can they actually be an useful change for educational rounds and how does it work? Suggest any other ideas in comments and feel free to share your feedback.