I don't feel like my attention-seeking senses are fulfilled with just comments, so I think it makes more sense to write a blog about it. Codeforces has evolved over the years and I think it might be a good move to talk about some relicts of the past that are still there, or even possibly do something about them. I'd like to note, that it's possible that there've been some blogs about this topic from the admins and I've missed them and lack information because of that. In this case, please pardon me.

After the first two Spectral::Cup rounds I've commented on things that in my opinion are somehow harmful.

The first comment was this one. It was mostly about the solution being judged twice on the same tests. I'm not much against it, as it seems to be well defined in theory: you have to pass both times to get AC (where the second time it might include extra tests), which is fine — not perfect, but ok, rules are rules. But from what appears here (or at least from what I understand), this guy's solution got rejudged after it got TLE on the second (system) testing. For me seeing that my solution passed the pretests means nothing definitive (mostly because of possible extra systests, that will be touched more in the next paragraph), but apparently that's not the case for everybody and maybe it's bad of me to not follow what I'm observing about recent contests.

The second comment was this one. This one is less about something being unfair in a direct way, but rather about hurtful conventions/assumptions. During this contest having the knowledge that systests are not going to contain any additional tests (except for possibly unexpected hacks) would get me a better place -- but seeing no announcement that in some problems the pretests are equal to systests (which appeared multiple times if I'm not mistaken) I've assumed that I can't assume so and resubmitted the code (I think that both version of the code are actually correct if you make some extra observations, but the discussion is about decision making). And that would be totally fine, but I kind of think that this assumption is actually correct nowadays and systests are actually supposed to be equal to pretests and that people who assume so are ahead of others (because of being less likely, or even fully unlikely to resubmit).

I kind of imagine the Codeforces team to try to be nice to users and therefore contain as much tests in the pretests as possible, but because it totally wasn't the case some years ago, it's hard for me to just assume so without seeing any clarifications. I also assume that the rejudge of the solution from the previous paragraph happened because of cf team wanting to be kind, but that couldn't happen if pretests wouldn't be equal to systests, right? So if pretests = systests is really such a "rule" right now -- why not come clear about it? Otherwise it favors people who make unspecified assumptions, or even worse, people who are close with cf team and possibly got a (in theory) not very meaningful bit of information like "yeah, we usually just set systests=pretests nowadays" or something like that.

As I'm already writing this blog, I think it might also make sense to remind about another Codeforces' bad choice, that I think is still there (I might be mistaken though and maybe it got fixed). This one is a pure choice and if wanted might stay here, but I still think that's the worst option out of three -- to come clear, by a pure coincidence, it's something that also have stripped me out of a better place (and even a victory) some years ago, but I don't think that that's that crucial, as it probably influenced the results multiple other times as well, including ones beneficial to me or the opposite. It's about whether a submission which fails on sample tests should get a penalty or not. Assigning a penalty would obviously make sense as I think on most other competitions this is the case and it just works. Not assigning a penalty is also a right (and I guess preferable) choice as Codeforces wants to be nice and from what people were saying, it's possible to submit a wrong code/to a wrong problem or format the output incorrectly or something -- this makes sense, as then the problemsetters might try to "catch" such solutions and prevent them from getting a penalty, and I totally support this option and I think it should be the active one. So it turns out, that there is also a third option, which I don't really understand, but it turns out to be the active one -- to not assign the penalty only if the solution fails on the first test, no matter how many tests are marked as samples. For me, this is clearly because it was just implemented this way temporarily and not fixed later. In this setting it obviously contradicts with the idea of problemsetters being able to detect the wrong formatting for example -- imagine two samples, one with answer YES and second with answer NO -- it depends on the pure randomness whether spelling each of those incorrectly results in a penalty (yes, I know that most times outputting something like "yEs" is also accepted, just try to stretch the example a bit if you need it). I can also obviously imagine cases where it wouldn't save someone from getting a penalty when submitting a wrong file -- I imagine a problem with the output on the first sample is "0" and the next samples have more complex outputs -- it could be rare, but I'd assume there is a non-zero number of such problems and I totally imagine the wrong code outputting "0" just because. So again, not assigning the penalty for failing any of the samples seem strictly better to me?

I also know that in theory requiring extra work from the CF team wouldn't be super nice, but in the past I learned that they are super responsive about some stuff -- for example I remember preparing a round and saying something about the polygon and it got fixed/improved within a day or so. I also assume that Codeforces is very much a site "from competitive programmers for competitive programmers", so I don't think that mentioning MikeMirzayanov and KAN and inviting them to the discussion is something bad. I'm also doing so because I really think that some things are simply a bit dusty and talking about them might make sense and improve the platform.

Thank you for your attention, good night.

UPD: I forgot to mention something. I understand that not clarifying whether the pretests are equal to systests is somehow "comfortable" for admins/problemsetters, but I think that the biggest usage of that fact (that I'm aware of) happened at this one round (it was a couple of years ago) when one of the problems had deterministic model solution, but it was possible to come up with non-deterministic one and I think that only I and one other guy somewhere down the standings did it this way. So for the systest phase, the problemsetters added like 700 extra tests to test against such solution and if I'm not mistaken I've won this round, so that definitely felt like a personal attack on me. So I'd say that the biggest usage of the comfortableness should've not really happened and rolling with whatever the state of the systests is is the way to go (except for saying that all unexpected hacks will be added for example).

Hello Codeforces! Are you ready for the third Universal Cup stage made of problems from Potyczki Algorytmiczne? I hope so, because during the next weekend (21.06-22.06) you will have a chance to participate in it!

Please note, that this is the last stage in this season and your last chance to participate!

The contest, just like the previous two (1, 2), is composed of problems from the finals of Algorithmic Engagements, the biggest polish open programming competition. If you happen to know the problems from the last two finals, please don't participate in this stage.

Problems used in the upcoming contest were authored by me (Radewoosh), Marcin_smu, tribute_to_Ukraine_2022, fwitt, onufryw, mnbvmar and Markadiusz.

You can participate in the contest during the standard time windows:

• 08:00 (UTC +8) on Saturday ~ 13:00 (UTC +8) on Saturday

• 10:00 (UTC +8) on Saturday ~ 15:00 (UTC +8) on Saturday

• 13:00 (UTC +8) on Saturday ~ 18:00 (UTC +8) on Saturday

• 16:00 (UTC +8) on Saturday ~ 21:00 (UTC +8) on Saturday

• 19:00 (UTC +8) on Saturday ~ 24:00 (UTC +8) on Saturday

• 21:00 (UTC +8) on Saturday ~ 02:00 (UTC +8) on Sunday

• 23:00 (UTC +8) on Saturday ~ 04:00 (UTC +8) on Sunday

• 02:00 (UTC +8) on Sunday ~ 07:00 (UTC +8) on Sunday

You can find all the information about all the stages here: https://ucup.ac

Hello Codeforces! I wanted to invite you (just like last time) to participate in the 2nd Stage of the 3rd Universal Cup, which will be held from June 15th to 16th.

The contest is made of problems from the finals of Potyczki Algorytmiczne (a.k.a. Algorithmic Engagements) from the last couple of years, which is the biggest open polish programming competition. Two such contest were created, one of them was held last season and in the upcoming weekend you'll be able to face the second of them.

If you participated in any of the PA2020, PA2021, PA2022 or PA special edition finals, or happen to know the problems, please don't compete in this contest. Also note, that this contest was previously used on OCPC 2024 Winter, so if you participated in this camp, please don't compete now.

Problems used in the upcoming contest are authored by me, Asymmetry, Marcin_smu, and monsoon. Also a huge round of applause for kostka, who helped a lot in organization of each edition of PA, coordinated this contest and translated all the statements!

You can participate in the contest in the following time windows:

• 08:00 (UTC +8) on Saturday ~ 13:00 (UTC +8) on Saturday

• 10:00 (UTC +8) on Saturday ~ 15:00 (UTC +8) on Saturday

• 13:00 (UTC +8) on Saturday ~ 18:00 (UTC +8) on Saturday

• 16:00 (UTC +8) on Saturday ~ 21:00 (UTC +8) on Saturday

• 19:00 (UTC +8) on Saturday ~ 24:00 (UTC +8) on Saturday

• 21:00 (UTC +8) on Saturday ~ 02:00 (UTC +8) on Sunday

• 23:00 (UTC +8) on Saturday ~ 04:00 (UTC +8) on Sunday

• 02:00 (UTC +8) on Sunday ~ 07:00 (UTC +8) on Sunday

You can find all the information about the upcoming stages here: https://ucup.ac

It was a beautiful journey full of internet digging, searching for patterns, learning stuff, fighting with formulas on paper, making crazy observations, coming up with brilliant ideas, implementing crazy optimizations, waiting for the programs to finish, suffering when something was wrong, and so on (and each of the mentioned not once not twice took multiple hours).

It's been a couple of months since I was left with the last unsolved problem and finally I did it! I didn't give up and I obtained the answer alone, without anyone's help, like in the rest of the problems (I was using only internet sources created before the publication of the problem). I'm writing this blog because I am bursting with joy and I wanted to share it with the community. I highly recommend PE as most of the problems were definitely very high quality (and some were a real pain in the ass, but they still teach how to overcome stuff that you're uncomfortable with).

Here's a little souvenir for me:

PS I still have no clue how to do anything useful with continued fractions.

Hello Codeforces! I wanted to invite you to participate in the 6th Stage of the 2nd Universal Cup, which will be held from October 21st to 22nd.

The contest is made of problems from the finals of Potyczki Algorytmiczne (a.k.a. Algorithmic Engagements) from the last couple of years, which is the biggest open polish programming competition. There will be two such contests held as Universal Cup stages and in the upcoming weekend you'll be able to face the first of them.

If you participated in any of the PA2020, PA2021, PA2022 or PA special edition finals, or happen to know the problems, please don't compete in this contest.

Problems used in the upcoming contest are authored by me and mnbvmar. Also a huge round of applause for kostka, who helped a lot in organization of each edition of PA, coordinated this contest and translated all the statements!

You can participate in the contest in the following time windows:

• 02:00 (UTC) on Saturday ~ 07:00 (UTC) on Saturday

• 05:00 (UTC) on Saturday ~ 10:00 (UTC) on Saturday

• 08:00 (UTC) on Saturday ~ 13:00 (UTC) on Saturday

• 11:00 (UTC) on Saturday ~ 16:00 (UTC) on Saturday

• 13:00 (UTC) on Saturday ~ 18:00 (UTC) on Saturday

• 15:00 (UTC) on Saturday ~ 20:00 (UTC) on Saturday

• 18:00 (UTC) on Saturday ~ 23:00 (UTC) on Saturday

UPD: Meta Hacker Cup Round 2 will take place this Saturday, so we added two more windows:

• 15:00 (UTC) on Sunday ~ 20:00 (UTC) on Sunday

• 18:00 (UTC) on Sunday ~ 23:00 (UTC) on Sunday

You can find all the information about the upcoming stages here: https://ucup.ac

Will there be one? Also, I'm not much into the topic: I'm asking about the finals taking place right now as I think it's the 2021 edition.

Hello Codeforces!

As all of you know, there are so many known algorithms named after people who invented them — from the easiest ones, like Dijkstra, to the harder ones, like Berlekamp–Massey algorithm. These algorithms were innovative when they were invented, so of course, it's good that they are named after their inventors.

But, today, I've seen a blog about the solution to the problem "compute LCS of two strings in time $$$O((n + k) \cdot \log(k))$$$, where $$$n$$$ is the sum of lengths of the strings, and $$$k$$$ is the number of pairs of matching positions in them". To be honest, it a bit pissed me off that even this algorithm is named after its creators. Is it ok to name the solution to every possible problem after its author? I won't judge it. Anyway, I want my very own Radecki algorithm, so let me give it a try. If anyone has ever heard about it — it's cool. Let me know, and it'll be just another helpful blog on Codeforces.

Let's imagine the following problem: there is a directed graph on $$$n$$$ vertices without any edges and a list of $$$m$$$ directed edges which we want to add to this graph one by one. After adding each edge, we want to have full information about the strongly connected components. Know the number of strongly connected components, be able to tell whether two vertices are in the same connected component or even make this information persistent. Critical condition: the list of edges is given in advance.

So, for a few years, I'm able to solve this problem, but people told me that it's rather boring and it's not worth to write a paper about it. Anyway, let me give it a try.

Let's use the divide and conquer technique on the list of the edges. We can also think about it like about divide and conquer over the timeline. So, let's assume that we have some function $$$rec(a, b, edges)$$$, where $$$a$$$ is the start of the time interval, $$$b$$$ is the end (we can assume that both are inclusive, doesn't matter, I'm still pissed a bit) and $$$edges$$$ is the list of edges together with the times when they're added. We start the process like $$$rec(0, m-1, everything)$$$.

Everytime we should look at the middle of the time interval, so let's compute $$$s=\lfloor \frac{a+b}{2} \rfloor$$$. Let's use the standard offline algorithm to calculate strongly connected components in the graph which consists only of the edges from $$$edges$$$ which were added before $$$s$$$ or exactly at $$$s$$$. We want to split recursively somehow, but how to do it to keep good complexity? It turns out that in the moments after $$$s$$$ all the SCC that we've just calculated will stay connected. So, we can merge whole components into single vertices and only pass to the right edges connecting vertices from different strongly connected components. Also, the edges that are now connecting different connected components were useless in the past, which means that we can pass to the left the rest of the edges. In this way, each edge will occur once at every level of the recurrence, there are $$$O(\log(m))$$$ levels, and in each level the overall complexity is linear, thus we have $$$O(m \cdot \log(m))$$$ complexity (if we implement it carefully enough to have no extra logs).

What should we take from the recurrence? The simplest idea: at each call of the $$$rec$$$ function, for each edge, push some information to some global data structure. My idea is to for each edge that connects vertices from the same strongly connected component push information "these two vertices are in the same strongly connected component at this time". This gives us something which we can interpret as a graph of undirected weighted edges. It's easy to see that we are only interested in its MST (the graph has $$$n$$$ vertices and $$$O(m \cdot \log m)$$$ edges with weights from $$$0$$$ to $$$m-1$$$, we can calculate it's MST in $$$O(m \cdot \log(m))$$$ time).

What can we do now with this information? We can answer queries like "What's the moment when vertices $$$a$$$ and $$$b$$$ start belonging to the same strongly connected component?" Yep, that's the maximum value on the path between these two vertices.

Clear? Clear.

Cool? As f**k.

Easy to implement? So so, easy to copy-paste and use. My implementation (without computing MST, just getting the list of undirected edges) has 72 lines.

New? That's a tough question. I know that it was on the prime new year contest 2018, which took place between 2018 and 2019, which tells that this problem was created in 2018. Even if the intended solution is the same as mine, here comes a twist: link. This is the problem authored by me in July 2017. I know, just a pdf is worth nothing, but it's possible to dig deeper and believe me: the solution implemented here is the same as described.

Lest thoughts: the resulting tree is really similar to Gomory-Hu tree (because of minimums/maximums on the paths).

So, do you know any existing papers about this algorithm? If no, I claim that it'll be called Radecki algorithm, Radecki's algorithm, or something, it doesn't matter, it's mine XD. The resulting tree can even be called Radectree. Let me know if you know any sources about it and if (in your opinion) it's worth writing a paper about it (I hope that this blog is enough to sue anybody if he'll write this paper before me) as I don't know much about this scientific world.

I'm not very often replying to questions about how to practice, but as I'm getting enough of them (and I've just seen another blog about practicing) let me tell you about it.

Of course, every time when you ask someone good about how to practice, he/she will reply to you to "solve a lot of problems" and that's true, there's no other way. Anyway, I've thought about it and actually I'm able to tell a bit more. I know some people, I've seen many people practicing (including me) and I have an opinion.

Many people practice in some organized way. High schools organize IOI/OI training contests every Saturday, universities organize ICPC training contests once a week, people try by their own to solve three problems each day, websites host rounds and so on. Here's a secret: it's a sh*t. Yep, that's true. If you want to be really good and to make it happen you compete in a training once a week, you do it only to be able to make excuses "but I'm training so hard" when you see no progress.

Every really good person gave a part of their life to CP. And I don't mean giving up Saturday parties or having no friends, I kind of mean the part of their minds. You have to really want to get better and find real pleasure in practicing and watching your progress. It also means catching yourself thinking about various problems or seeing algorithmic interpretations in many aspects of real life.

You should practice every time when you have an idea "oh, I'd solve some problem", "oh, it'd be good to practice a bit now" or "oh, it'd be cool to solve every problem on this website, let's start". Here's a trick: if you really want to be good, you'll have a lot of such ideas. If you don't have them and you want to just practice weekly, then better go and reconsider if you really want to be better.

Do you think that you are bad at combinatorics? Good, you see your weaknesses, go solve some such problems.

Do you want to simply solve a few problems? Great, go and solve them as long as they are challenging for you. Or you want to solve every problem from some problemset (still can be a challenge for you). Or you want to upsolve a whole round (still can be a challenge for you). Or you want to have more problems solved on Codeforces than your friend (still can be a challenge for you). Or because of any other reason, but still, don't solve the easiest problems on Codeforces and expect to become good.

Do you want to participate in a virtual round? Sure, go and do this. Don't do this if you are sure that you'd solve them. Do this if you want to check if you'd win that round/be better than your friend/something. Challenges, remember? But don't get me wrong, for example, if you are already quite strong and you want to read (or even participate) the problems from div3, which is definitely below your level — it's ok if it's a sign that you are curious about problems and it's interesting for you.

Do you really want to get better and compete virtually in two 5-hour contests in a row? Great, go and practice.

Want to go and participate in a training organized by your university? Of course, great idea — rivalry, some stress, fun with other people. If you are really practicing and trying to get better, the weekly trainings with your schoolmates/university/teammates will become a nice event for you, but don't depend on them. Also, practicing with your ACM team is a way to create a better team — you have to know your weaknesses and strengths and learn how to cooperate. To make your team better at solving problems when you already know how to cooperate, you have to make yourself better at solving problems.

Do you want to skip a training organized by the university and meet your friends/read a book/play some games? Sure, if you don't feel like practicing, then don't force yourself. If you really want to practice and become strong, you'll for sure compete in this contest virtually or something, don't force yourself, just really feel a need to practice. You can't rush art, right?

One more time: you really have to have CP in your mind. After solving a problem, it doesn't mean that it's gone and you have to forget about it. Maybe you'll find yourself thinking about some interesting aspects of some task and you'll invent a harder one?

I don't know what's more to say. Don't give up? With the right attitude, if you can't solve a problem which is really interesting/important for you, you'll try for a few days — the pleasure and self-satisfaction after solving a problem for a few days with success is one of the best feelings.

Also, one last tip: I've noticed it observing all the top people on Codeforces/Atcoder. None of them uses the word "question" instead of "problem"/"task". So don't do it. You won't progress if you'll keep calling problems "questions".

So yeah, that's my opinion. Let CP get into your mind and find a true desire to practice. Don't try to force yourself to practice in an organized way.

I know that this blog may discourage some people, but they wouldn't go far with such an attitude. I also think that it can help people with real potential to become somebody really strong and that's why I wrote it.

If any other top-rated coder wants to share his/her way or just point the differences — that's great.

As you may know, Codechef long challenge is currently running. After the first one, I thought that I should just ignore it, but I've received a second ask for help with a problem from this contest...

Probably I'm not the only one being asked and that there may be more questions in the future. I'm always surprised by such questions. If you don't know how to solve a problem and you want to be able to solve it someday, then trying to cheat definitely won't make you such a person. What's their motivation if not just solving the problem (which makes no sense, because in this way you should just want to get better)? A bet with friends? Asking random people who are able to tell admins about this question is not a good idea then. Wanting to get a higher rating? Also stupid, you shouldn't get a rating to show that you are good, you should be good to show that you are able to get a rating.

Also, note that one of them was saying that he didn't ask for help because he didn't ask for any approach, while in my opinion asking for information which is not known for everybody is still cheating.

So, my question is how do you guys react in such situations. Here are my replies if somebody is interested.

Should I show their nicknames? Should just this blog and discussion be a way to show them that they should try to solve them by themselves? Probably it won't be the first discussion about it. I don't know, maybe making the world better is just a dream, but let me know what do you think in the comments.

Also, please note that I'm a bit irritated, as they used "question" instead of "problem"/"task".

There are many blogs on Codeforces, and most of them aren't very important a long time after publishing, like round announcements, saying "hello", asking for a better explanation of problem B than the one in the editorial, and so on. Among them, there are a few very interesting blogs that are a great resource of knowledge, like ODE by MiFaFaOvO, HLD by Vladyslav, suffix automaton by quasisphere or even Blogewooshes.

In my opinion, it would be great if there would be a special place for such blogs, accessible for example, by navigation bar, where they would be somehow sorted. It would be much easier to think "Let's learn something new!" and to do it. Also, probably Codeforces would have the greatest such base for competitive programmers. What do you think guys and MikeMirzayanov?

EDIT One more argument after thinking a bit more: of course there are a lot of papers, but everybody here knows that it's much easier for "us" to learn from blogs written by other competitive programmers. An example which comes to my mind: I've heard that parametric search sometimes isn't very popular in papers because it has something like $$$O(\log(limit$$$_$$$for$$$_$$$coordinates))$$$ and it isn't "proper" to have something like this in the complexity while ofc for us it's great and has a lot of usages. Competitive programming and paper-science differ a lot, so a base of knowledge for us would be great and we have a lot of it written and hidden, so why not organize it?

Can somebody tell me what's going on with Project Euler problems on HackerRank? Do they just steal the problems? Project Euler says that they ban everybody who spoils solutions to problems above 100, and it took me a few minutes to find a solution to one of the later problems with difficulty $$$80\%$$$.

I see a few options:

Maybe Project Euler doesn't know about it? -- Hackerrank isn't as quality as CF or PE, but still, I think that PE's admin would already hear about it, and it's big enough that it might look like a problem.

Maybe PE allows HR to take their problems? -- Of course, it's possible, but knowing the policy and rules of PE it looks very strange -- finding this code took was very easy, somebody just posted it in the comments section on HR.

Money? -- ???

The same admins? -- ???

Of course, everybody sometimes steals a problem, to use it in his/her school or university for example, but this looks like a huge process. Does anybody have any information? I'm just curious.

So, one person (we know who) was annually making a poll to choose the best problem of the year. I'd like to see the results of the voting, but there's no poll. Should we wait a bit longer or maybe can someone do such a poll.

I mean someone respectable, like MikeMirzayanov or snarknews.

Is anybody going to do something with that? Just asking, I don't know if I should prepare for some changes or for choosing only one of them.

OK, this might be a bit strange. Many people ask others "How to become a better programmer?", "How to become red in two weeks?" or "Can somebody explain to me the solution to problem B?" under the editorial with a beautiful explanation to problem B. My question will be a bit different.

It'll be about marathon problems, especially about Marathon Matches. I'm not so bad at it, I've been the best in my problem in Deadline24 eliminations a few times or so, but I'm much worse on long contests. Now, it looks almost impossible for me to win a Marathon round. I'm not sure how should I practice, there are many ways to practice normal CP, but marathons are different. You have to spend a lot of time on one problem to produce a good enough solution. Also, I don't know what am I missing — bad idea, implementation details, wrong temperatures (I'm still not sure if I anneal correctly) or if my code is simply too slow to check enough options?

So, is there any list of tips from people who are for example Red on TopCoder or are regular Marathon finalists? Some ways to know what am I doing wrong? Or maybe even some tutorials? Psyho, Milanin, mugurelionut, wleite, CatalinT, how did you guys become so good?

And yes, here it is, Radewoosh getting back to basics and asking for tips :P

Hello everybody! A new round is upcoming and I'm honored to be its author. The round will first appear as the onsite for Dasha.AI Code Championship and later we will hold a rated mirror. Everybody is welcomed to participate in Codeforces and I wish good luck for people in Saint Petersburg and Novosibirsk.

Using the opportunity, I want to thank:

• mnbvmar for helping in the preparation of a great part of everything. Really, without you, I wouldn't do it.
• 300iq for coordination and help with preparation.
• As always, MikeMirzayanov for taking care of international competitive programming and making such great platforms as Codeforces and Polygon.
• KAN, zscoder, Lewin, Jeffrey, Darkstalker, Darko and Gtaumaturgo for testing the problems and great advice.
• Dasha.Ai for an organization and a sponsorship.

Scoring will appear later.

Good luck and see you during the contest!

UPD1a: Scoring in div2: 500-750-1250-1750-2500-3000

UPD1b: Scoring in div1: 500-1000-1500-2250-(1500+1250)-3500

UPD2: editorial

UPD3: Congratulations to the winners!

In div1:

1. Um_nik
2. yosupo
3. ksun48

In div2:

1. lqs2o15
2. rainboy
3. HoshigakiKisame

In the onsite competition in Saint Petersburg:

1. aid
2. vintage_Vlad_Makeev
3. cookiedoth

In the onsite competition in Novosibirsk:

1. Timonnable
2. Pechalka
3. Maho

As we all know, polygon is a really great system for the problemsetters. I have one proposition, which may make it a bit better.

After making an invocation with all the tests, if we add some tests in the future and rejudge this invocation, the new tests will also be included. That's really great and helpful. Things are different if we consider solutions. If we add a new solution, we have to manually remove each invocation and add it back with a new subset of solutions. In my opinion, it would be nice if new solutions would be added automatically to the invocations which have the option "all solutions" marked.

What do you think about it guys? MikeMirzayanov, can you consider this?

I'm not sure what's exactly happening right now. I know that a few (about 7) last SRMs was a series of fuck-ups, so I assume that people from marathons also aren't sure what should be done now. Can anybody from topcoder write any clarification?

We've been waiting more than two weeks for the systests for the first round (if I'm not mistaken). Are the current standings final? Is there any way to be informed about the news and know the current status?

There's some information that you wanted to make three stages of standard matches and three matches in each of them. Why is leaderboard showing stages numbered $$$2$$$, $$$3$$$ and $$$4$$$ and the fact that stage "$$$3$$$" had only two matches and stage "$$$4$$$" still had no matches... I'm not sure if the stage "$$$1$$$" is missing, or if you didn't manage to organize matches in stage "$$$4$$$". Or maybe just the leaderboard doesn't work? It would be nice to check stage dates in the "rules" section, but they are missing here too...

Fortunately, there are dates of the online rounds in the "rules" section. And they say that the second round is going to end tomorrow... Are you sure? Has it even started?

In conclusion, what are you planning to do now? Can you tell us some dates? Or at least guarantee that the marathon finals will take place this year?

Also, I want to ask about the new system. There is definitely at least an intention to go in the good direction, we already can use standard I/O, but will it go further? By further I mean just sending only one file like on any other platform, or letting us use standard I/O also on SRMs.

If you've already seen this task somewhere, I'd be grateful for the link.

You are given a string of length about $$$10^5$$$. There are many queries about intervals of this string and for each interval, you have to calculate the number of distinct subsequences (not necessarily contiguous) of this interval.

The solution builds a segment tree and keeps matrices in each node. Have you seen this problem?

Am I the only one who is not able to register? The button "Register" is gray and I'm unable to click it. link

Hello, codeforces!

Long time no see, right? So maybe it's a good idea to try to return to my blogs slowly. This time the blog will be about a trick, which usually isn't necessary to solve a task, but can be useful to make implementation much more comfortable.

Let's look at this problem. It is about some DP on a tree in which we have to use convex hull trick to improve the complexity. The task requires merging two convex hulls with "smaller to bigger" trick. I recommend you to read the statement before reading the rest of the blog (and the editorial if you don't know how to solve it).

Once, during one training, my team and I noticed something strange. I'll write a little bit later what it was exactly. The point is that after the contest we decided to investigate how c++ rand() behaves on our machines (we use Linux). So, we used a Berlekamp–Massey algorithm on the results of rand() taken modulo 2.

The result is shocking — the length of the linear recurrence is only 527! No, the results aren't cyclic, just the recurrence is short.

"Cool, but who cares? Just some random fact which I wouldn't notice and it wouldn't have any impact on me." — wrong!

We discovered it while solving a task which required calculating the rank of a binary matrix. We wanted to check something, so we just generated big matrix using rand(), which turned out to be a bad decision. As only the first 527 columns were, let's say, independent, the rest were determined by first 527 ones, so the rank didn't exceed 527, and we lost much time just wondering what's happening.

Moreover, if the number of columns is even, the rank is only 496 (for matrices big enough of course). Guess what's the length of the recurrence if we look only at every second value of rand().

Yep, you're right — 496. One can notice that 527 - 496 = 31 and that 31 divides 527! Illuminati!

Here are some useful links: 1 2.

If anybody can explain precisely what's happening for even number of columns, it would be great. Also, if anybody knows how does rand() look inside and can say a few words about it, it also would be great.