Codeforces Global Round 28 just finished, and I had a heartbreaking moment. Three minutes before the end of the contest, I finished writing code for problem G, submitted it, and got RE1. I didn't have enough time to figure out what the problem was. However, after the contest, I was able to understand what causes this behavior but I still can't figure out WHY this happens so maybe some C++ experts among you can help me :)

Submission for reference: 297344731. I have a structure for modular arithmetics template<int mod> struct ModularInt. Inside it, it has a static vector of some modular inverses: static vector<ModularInt<mod>> invs; that is then initialized after the end of the structure: template<int mod> vector<ModularInt<mod>> ModularInt<mod>::invs{ModularInt<mod>{0}, ModularInt<mod>{1}};. I then use this vector of inverses in the modular inverse function:

inline ModularInt<mod> inv() const {
    assert(value != 0);
    int ans = 1;
    int curval = value;
    while (curval >= invs.size()) {
        int tmp = mod / curval;
        ans = 1LL * ans * (mod - tmp) % mod;
        curval = mod - tmp * curval;
    }
    return invs[curval] * ans;
}

For some reason on codeforces, this function causes division by zero error on line 6. It happens because invs.size() is equal to zero which clearly cannot be the case because vector invs is initialized with two elements. This error happens if I use the inverse operation to declare some global values. However, if I move these computations inside the main function, this problem disappears, and the submission gets AC (see 297350557). On my computer, I cannot replicate this problem. Could somebody please help me to understand why this is happening and how to fix it?

Recently at the AtCoder World Tour Finals tourist shared his latest optimal contest strategy development — the so-called "never submit" strategy: an improvement over the "late submit" strategy. You can learn more about it in the following clip from the stream:

Ranges and views from c++20 are cool. Today I have learned that C++23 brings even more fun stuff from python to c++. For example, zip and enumerate. These are some of the features from python that I missed the most in c++. Also, now there is a thing called cartesian product which helps one to avoid writing 5 nested loops.

I think these things could be pretty handy for competitive programming, so I would like to ask: what other features of c++23 do you find interesting? And when do you think we could get c++23 on Codeforces?

I was waiting for somebody to post this, but I guess I am going to post it for history purposes. Here is the clip:

https://youtube.com/clip/UgkxjClduTG6kL6s3c8BFNNYdE1HVR2wGMxf?si=pFZCy3KapKbTLNCC

They cut it out pretty quickly in the broadcast, but let me tell you what we were seeing from the audience. The team of KNU is coming to the stage. They all have some kinds of pins on their T-shirts with Ukrainian flags. In the clip, you can see it if you pause and look closely. But they switch the camera away quickly. Then the team members and the coach go behind the big screens. Normally other teams go out on the stage pretty quickly, but here nothing is happening for like a minute. Then they walk onto the stage, with no pins anymore. I don't know what happened behind these screens, but it probably isn't hard to make an educated guess. For context: clip from EUC.

Today, the European Championship was held in Prague. The first of its kind. And it was... the worst organized contest I have ever participated in. This is not only sad in isolation but also especially sad as the contest itself (the problems) was actually nice, and I would like to thank the authors for that!

So what was so bad about it?

Let me describe how entering the contest works. One first goes to the cloakroom. Then, one proceeds via a long corridor to another building, where in a relatively small space, all teams gather for half an hour. Then, "id check" begins. I mean... I have never seen this before but in itself, there is nothing wrong with it. They want to check your identity. Makes sense. However, what do you think would be a reasonable way to do it? I would think that one and only reasonable way to do it is the following: one comes to the entrance of the contest area, a volunteer checks their id and matches with their badge, and the contestant comes in. As you could have already guessed, it was not like that. The system works in the following way: you wait aimlessly for half an hour in this relatively tight space, and then they start calling teams one by one in random order. They check the ids of the team they call, and then this team goes further. To the contest area? No no no! To a different tight space where teams slowly gather, and then, after 20 more minutes teams are allowed to go to the contest area. This system literally makes zero sense and does not take into account the interests of participants in any way or form. I felt like organizers think about us like amazon thinks about its goods. Just transport them in the way they want regardless of how much these items need to wait at random spots because amazon products don't have feelings. But to the surprise of EUC organizers... participants have! And then the cherry on the top of this: again for no reason, this process was repeated twice: one day at the dress rehearsal and then the next day at the actual contest. If there was any reason to do it during the dress rehearsal, it could've been to understand that it is an awful system that should be abandoned. But no.

Ok, great! We are in the contest area. Suffering finished, right? Oh no! People put their stuff on the tables and are ready to go to the bathrooms? Huh! "You are not allowed to go to the bathroom before the contest starts". Excuse me? At first, I honestly thought it was a joke. It reminded me of some soviet-minded teachers we had at school. What is that even supposed to mean? Especially considering the fact that this conversation is happening 5 meters away from the toilet. You just kept us for like half an hour in a random tight place with no toilets and now when we arrive to the contest area, we cannot even go to the bathroom? We should wait until the contest starts and then waste our contest time? Is there any reason for that? Hard to believe.

Can't go to the toilet? Oh, maybe I can grab an additional bottle of water because for some reason there are three bottles at the workplace but one of them is sparkling? Oh no! Again. You can only take water when the contest starts. Genuinely. Are these rules there just to have rules?

Well, nevermind, sure, the contest started. What is happening? Volunteers just standing behind your back staring at your screen and loudly talking to each other. Sure... But not only that, no people in the contest area could provide any help to you regarding anything (in terms of guidance). During the dress rehearsals, we were given this transparent file which is supposed to hold a single piece of paper and we were told to leave ALL the things we will need at the actual contest inside this file. For example, food, pens, medication, three team reference materials 25 pages each already inside a larger protective case. Reasonable, right? Can I ask anybody in the contest area about WTH I am supposed to do about it? No! Because nobody knows anything. You are supposed to ask this kind of question in the system. Surely, it is so convenient to assess this kind of situation virtually.

Ok, let's come back to the actual contest. We are sitting in a place that is not made for spending prolonged periods of time there. I don't know what these things are called but it is like an atrium. So the ceiling is glass. At first, it is very cold. Surely, the organizers told you to wear the ICPC T-shirt? Well... You're gonna be freezing. Then... Surprise-surprise: the sun comes out. And it becomes insanely warm. For some, it shines directly into your eyes. For others, into the screen, and they cannot see anything. Clearly, absolutely unpredictable conditions, right? Then it becomes insanely cold again, then hot, and some more times throughout the contest. Magical experience. Loved it.

I would like to point out one red line that goes throughout these stories: random rules that should be followed just... because. I know that ICPC contests overall love random rules just to have rules. But this one... This one was pure fun. As a final rule that comes out of nowhere: link, link2.

I decided to learn some C++20, and now I am trying to incorporate for loops with std::ranges or std::views stuff. I stumbled upon the fact that there are two options: ranges::iota_view and views::iota. They seem equivalent to me, but I wonder whether I am missing something. On the internet, I found a mention of ranges::iota_view being better than views::iota "in terms of performance", but I was not able to reproduce it. On the other hand, views::iota seems shorter and easier to alias: one can just write const auto &range = views::iota; and use Python-like for loops, but const auto &range = ranges::iota_view; wouldn't compile. One could instead use using range = ranges::iota_view<int, int>;, but this now works only for integers (adding template<typename T> to using would force me to always write range<int, int>() because apparently using in C++ does not support argument deduction). I would like to hear your opinion on this. Has anybody thought about the same question before? What did you do?

P.S. I am asking about purely competitive programming usage, not software engineering.

The last two Div. 1 + Div. 2 rounds were not numbered:

In total, in 2023 there were already 7 such "unnumbered" rounds out of 21 rated for Div. 1. Honestly, it completely messes up the folder names on my computer. And I don't really understand why it should be so. There are numbered rounds. There is a separate numbering system for educational rounds. This is ok — two different numbering systems is no problem (like ABC, ARC, and AGC on AtCoder). Then we have Global Rounds. Then we have things like Hello, Good Bye, and April 1st rounds. Already quite a lot of instances but it is still ok, these are understandable regular things. But nowadays we have all these company-sponsored rounds that previously were just normally named rounds (and maybe had the company name added but they still were numbered as normal rounds). Why are they now also separate instances every time? Sometimes I can't even easily understand whether a round is rated or not by just looking at its name. For example, "Harbour.Space Scholarship Contest 2023-2024" does not look rated to me. And if Pinely Round 2 at least makes sense (even though I don't like the fact that we have so many small separate instances), this round name does not make sense to me at all. What is going to happen next year if there is going to be a similar contest? "Harbour.Space Scholarship Contest 2024-2025"? It becomes too messy! Why not just "Harbour.Space Scholarship Codeforces Round 895" or something like that?

One and a half months ago I proposed a challenge to every one of you to get something from your drafts or from your head and actually write a blog post about it. I got a bunch of submissions, and you can find the links to all of them throughout this blog post (I was actually surprised that all entries were meaningful and interesting, so I definitely recommend checking them out). If you submitted an entry and I didn't mention it here, it is not purposeful! Indicate it via a direct message and I will include it here. It was just a bit hard to keep track of all submissions.

I went through all the submissions. Some of them were very complicated, and I tried my best to get the overall idea but I will need to come back to dive deeper into some technical proofs. However, I believe that these technicalities that I glanced through do not affect my decisions. We are ready to present the winners!

Regarding the first place, there was no doubt in my head. Without any hesitations, I give it to Monogon with his blog post about priority-queue-like undoings on data structures. It ticked all the boxes I wanted from this challenge. It is a novel idea that is pretty easy to understand and implement at the same time. The explanation is clear and concise. I highly recommend everybody who is at least orange read it. So congratulations to Monogon. The $300 prize is yours!

Thanks to rafaelgo we also have a prize of $50 for second place. And this decision was much harder to make. In the end, it came down to two candidates:

1. First is adamant with his blog post on online FFT and its generalization. I am a big fan of FFT, generating functions, and similar algebraic viewpoints on combinatorial problems. For me even the online FFT part was new, and even though it was already explained somewhere before, I enjoyed the explanation and the examples. And the generalization just looks like magic even though you understand that "yeah, should work I guess". Definitely not a beginner FFT material though!

2. Second is ko_osaga with his series of blog posts on range longest increasing subsequence queries. It's based on a research paper (with the author of which I actually had an opportunity to work on the related algebraic structure of LIS a couple of years ago but I decided to not do it, maybe I should have...), and hats off to ko_osaga for simplifying and codeforcesifying it. It is fascinating that such a classical simple problem can be viewed from a very different perspective, and tools you wouldn't expect to see arise. I wouldn't lie, I was not yet able to understand everything there, but I got the main ideas. Again, please, don't try to read it if you want to learn LIS. Come back 5 years later.

It was a hard decision but I decided to go with the first one as the topic resonated more with me, and at the end of the day if there are two great ideas, why not go with the one that is easier to understand and implement? :) Congratulations to adamant on the second place! Nevertheless, congratulations to ko_osaga for the third place.

I will contact the first two winners shortly and send them their prizes. (UPD: done)

And now the list of all other entries in no particular order:

• CMS trick by Dragonado. I was happy to see a submission from a purple user. Was sad that there weren't many. Interesting idea, I always like it when two segment trees communicate with each other.
• Convex optimization blog series by chromate00. And blue ones too, right? Math is not as scary as you think it is.
• On variations of string matching by brunomont. There are many different techniques for string matching. Nice to collect them all together. The wildcards one was new to me.
• Centroid decomposition for very sparse graphs by dimss. Simple and at the same time not obvious idea.
• FFT tutorial by -is-this-fft-. Solid tutorial with a good problem selection. I just didn't find any novel ways to explain stuff there for it to be great. Nevertheless, if you want to learn FFT, it is a place to go to.
• Simulated annealing by qwerty787788. External blog with cool animations. More of an exploratory approach to a simple idea that is not that easy to make work properly.
• Sometimes it's not their fault by Lyde. The only non-algorithmic entry in this challenge. I think what I got from this blog is that if I like a contest, I should write a comment about it.
• Push-Free Segment Tree by nikgaevoy. The main idea is pretty simple. I also used it sometimes. But the applications for the 2D case were novel to me. Good stuff.
• Two more blogs by adamant. I decided to not count them towards the win of the entry on FFT because it was a competition of blog posts, not people. The first one on permutation "basis" was very clear and not-too-mathy. The second one as I promised I did not really read into details yet. It is a continuation of a blog from 8 months ago that I also did not yet read. Looks scary and interesting.

Thank you for your attention. Arm Ukraine!

C++ is an excellent language for competitive programming, and most of the top performers use it. However, it has many flaws. Lately, Rust is getting increasingly more popular on CodeForces. I haven't yet written a single program in Rust in my entire life, however from what I have heard about it, I feel like there is actually a possibility that in 15 years it will be the most popular CP programming language as now is C++ and as 15 years ago was Pascal (don't quote me on that).

So this Saturday, January 21st at 11:00 AM UTC I will be streaming and trying to solve a CodeForces round using Rust, learning it along the way and seeking help from viewers. Additionally, we will be raising money for a great non-profit organization that helps Ukraine. More details at the beginning of the stream.

The link to the stream.

TL;DR: Write an interesting CodeForces blog post until February 15th and win $300.

UPD: Second place will receive $50.

UPD2: Competition is over, The results are available here.

I am a huge fan of CodeForces and specifically CodeForces blog posts! There are tens and hundreds of gems posted on this platform throughout the years. Thankfully, recently there was added the catalog page where a lot of cool articles can be found. Personally, if I want to remember some classical algorithm, I would go to websites like cp-algorithms, but CodeForces is the place where new or rare stuff is born, where new points of view emerge. I think it is one of the most valuable functions of this website, and I would like to facilitate its growth. I know that many people have cool ideas in their minds that they came up with or maybe something that is known only in their community on a spoken basis, and they were always too lazy to share it with the world :) Now it is time!

That's why I am proposing the "Codeforces Month of Blog Posts", and I encourage everybody to participate. The rules are simple:

• Post something on CodeForces no earlier than January 1st (00:01 UTC) 2023;

• Send me a link to your blog post as a direct message on CodeForces before February 15th (23:59 UTC) 2023, and indicate that you are participating. I also recommend you post a link to your blog post in the comments here if you feel like it.

I would appreciate it if you also include a one-sentence explanation at the beginning of your blog post explaining this challenge and a link to the blog post you are reading right now so that more people can learn about it and participate, but it is not obligatory in any way, I am not forcing you to do so.

And the juicy part is: at the end of this 1.5-month period I will choose the winners, and the first place will receive a prize of $300 from me! And also thanks to rafaelgo we will be able to reward the second place with a $50 prize. But I hope you all understand that money is just a little motivation for you and the point of this is not money per se but fun.

Your blog post may be about anything you want but let me explain what I expect. As I said at the beginning, I love new ideas. So I would enjoy seeing blog posts that either introduce some cool new/rare algorithm/idea, a new interesting point of view on an already known algorithm, simplification of a classical complicated algorithm, some CP-related fascinating math construction, novel way of stress testing, etc. I think you get the point. Just create some unique piece of content related in any way to competitive programming.

I am excited to see all your amazing blog posts! Don't hesitate to share your thoughts in the comments. I am open to any suggestions. Maybe, you think that 1.5 months is not enough for you, and you want the deadline to be extended? Maybe, I didn't specify something precisely in the description of the challenge? Maybe, you would like to increase the prize fund and join the jury? Ask it in the comments or direct messages!

I wish you all a happy peaceful New Year. And talking about peace, I would like to remind you that there is a war going on in Europe right now. Ukraine is bravely standing against Russian aggression, and it needs your support. There is an uncountable number of ways you may help: both with money and your time. I will just list a couple of trusted volunteer organizations: https://wfu.world/en/, https://u24.gov.ua/, https://rassvet.world/en/sunrise/.

UPD: schedule, list of guests, and questions form for guests added.

UPD2: link to the stream: https://youtu.be/WZKOdorb1Dg

I know that lots of you were saying that Codeforces should stay out of politics when there were lots of blog posts supporting Ukraine a couple of weeks ago. Well, I respect your opinion, but I can't agree. If you see a binary search tutorial on the "Top" page, do you complain about it if you're not interested in binary search, or do you just ignore it? And at the end of the day, it's not really about politics, but about people's lives.

Having said that, I'd like to invite you to join my 8-hour long live stream on YouTube against the Russian invasion of Ukraine next Sunday (27th of March) from 10 AM till 6 PM Ukrainian time (be careful, 27th of March is a daylight saving start in Ukraine and a lot of other countries, but it may not be the case for your country, so check your timezone using this link).

Сurrent plan is (all time periods are in Ukrainian timezone; if you want to ask questions, go here):

10:00-10:30 — Intro, tricky interesting problems for chat

10:30-11:00 — Interview with Matt tehqin Fontaine (author of Algorithms Live! youtube channel)

11:00-11:30 — Solving problems blindfolded

11:30-12:00 — Interview with Nikita nskybytskyi Skybytskyi (author of Nikita Skybytskyi youtube channel)

12:00-13:00 — Lecture: Everything I know about lambda optimisation (aliens trick)

13:00-13:30 — Interview with Alex Um_nik Danilyuk (ICPC 2020 champion team member, author of umnik_team youtube channel)

13:30-14:30 — Solving problems blindfolded

14:30-15:00 — Interview with Kamil Errichto Debowski (author of Errichto and Errichto2 youtube channels)

15:00-15:20 — Lunch break

15:20-16:00 — Cool little algorithms nobody talks about

16:00-16:30 — Interview with Anton antontrygubO_o Trygub

16:30-16:45 — Talking to chat

16:45-17:15 — Interview with Jay Geothermal Leeds (author of Jay Leeds (Geothermal) youtube channel)

17:15-17:45 — Interview with Ildar 300iq Gainullin (IOI 2019 2nd place)

17:45-18:00 — Outro

And during this stream, I'd like viewers to donate money to Ukraine. Here I'd like to get some help from you. Please, leave some organizations that help Ukraine to which we could donate money in the comments. Also, I'd like to have a counter on the stream that says how much money was donated by the viewers, but I don't understand how it is possible if they will not be donating it to me. If you know how to do it, also suggest your ideas. Of course, it's possible to donate the money to me, and then at the end of the stream I could send them to charity organizations, but first of all, you should 100% trust me in this case, and second of all, I'm a Russian citizen, so it's really hard for me to have any kind of PayPal, etc at the moment to collect money :)

If you are my friend or anyone who would like to be a guest on this stream, please DM me on Codeforces or Telegram. Don't be shy! If you have any ideas on what I should do during this stream, also write them in the comments.

Hope I'll see you in a week! NO WAR!

I really like good blog posts. And that's the main reason I like Codeforces. But as we all know, it's hard to find good blog posts here. So let's help each other and share our favorite posts, which were uploaded to Codeforces in the last year! I will share my top 10, and I encourage you to share some of your favorites in the comments.

10. Heuristic algorithm for Hamiltonian path in directed graphs by Rewinding

An absolutely incredible algorithm which kinda sometimes solves the Hamiltonian path problem on some random and special kind of graphs.

9. I compiled a list of almost all useful blogs ever published on Codeforces by parveen1981

This blog has a purpose that's similar to the purpose of the blog you're reading right now. A great source of interesting blog posts!

8. Fast modular multiplication by orz

Some really interesting algorithms that help multiply 64-bit numbers modulo without int128.

7. Competitive Programming Hall of Fame — cphof.org by Ra16bit

A new awesome resource, that collects all the different achievements of CP-legends.

6. The Ultimate Topic List and (The Ultimate) Code Library by YouKn0wWho

These are two different posts, but I would like to combine them. This is a really nice collection of materials and implementations of tons of different algorithms and data structures needed for competitive programming.

5. My opinion on how to practice competitive programming by Radewoosh

Some really interesting thoughts from Radewoosh and a really long and engaging discussion in the comments.

4. C++20 Is Released by MikeMirzayanov

The main treasure of this blog post is the comments! So many interesting tricks and tips for C++20.

3. [Tutorial] GCC Optimization Pragmas by nor

I never used pragmas because I didn't understand what they're doing. Finally, there is a resource where I can close this gap in my education :)

2. Lambda optimization certificate by never_giveup

A really interesting discussion about an algorithm which is around for 5 years but still isn't really understood by the public. I learned a lot from this blog post and after that started researching a lot of things about lambda optimization (a.k.a. Lagrange optimization a.k.a. aliens trick) on my own and figured out that I didn't really understand a thing about it before.

1. [Tutorial] Li Chao Tree Extended by rama_pang

In my opinion, it is the best blog post and the best new data structure of the year. It's absolutely incredible and simple at the same time.

I hope you learned something new today. I'm looking forward to reading your favorite blogs. Merry Christmas and Happy New Year.

Hi!

I wanted to make a new fun screencast. In this video, I'm solving Codeforces Round #747 (div. 2) but there are two main differences from a regular screencast:

1. It's a highlight video which means that it's not a 2-hour long video of me thinking about problems but just some fun, interesting, exciting moments.

2. It's something I called a "Challenge Screencast" which means that there is a challenge I need to complete during the contest. This time the challenge was to not use any loops in the code. So no for loops, no while loops... At all!

https://youtu.be/imGdtb_lB_U

I hope you'll enjoy it! I'll be happy to hear any comments and suggestions for the future challenge screencasts!

As some of you asked me, I'd like to share a video in which I'm talking about my competitive programming setup (especially codeforces). I'm talking about my hardware, google chrome extensions for codeforces, vim setup + snippets, c++ template, and much more.

If you're interested in something specific, you may want to use timestamps in the description. All the links to everything I'm talking about in this video are in the video description.

Link to the video

When you use C++ and the input is really big you can't just use cin and cout. You need to speed up it with

ios::sync_with_stdio(0);
cin.tie(0);

Someone argues that the second line is unnecessary but it's not true. if the input and output alternate then adding the second line makes I/O more than twice faster. But then... Someone argues that we also need to use cout.tie(0).

I personally never use this and I don't know any case where it can help. So my question for today is the following: "Is there any case where we actually need cout.tie? Or is it completely useless?"

Hi!

In the new video, we’re going to talk about the amazing data structure called Segment Tree Beats, which allows us to support a huge number of operations that a regular segment tree can’t handle. We will learn how to take numbers on a segment modulo some number, apply the min= and max= operations, add += to them, and also find GCD on a segment with these operations. And all the proofs are gonna be super simple, so don’t be scared, it will be easy! In the next video, we will cover even more awesome queries, so stay tuned.

Link to the video

You can check out my previous videos on my channel

Contest on Segment Tree Beats (and others) is here

Also, there's the Russian version of this video if you speak Russian here

Original article in English

Original article in Chinese

Implementations of algorithms from this video:

%= on a segment, = in a point, sum on a segment

Ji Driver Segment Tree (min= on a segment, sum on a segment)

min= on a segment, max= on a segment, += on a segment, = on a segment, sum on a segment, minimum on a segment, maximum on a segment

Everything from the previous implementation but also GCD on a segment of algorithms from this video:

%= on a segment, = in a point, sum on a segment

Ji Driver Segment Tree (min= on a segment, sum on a segment)

min= on a segment, max= on a segment, += on a segment, = on a segment, sum on a segment, minimum on a segment, maximum on a segment

Everything from the previous realisation but also GCD on a segment

There's a really weird situation with the last Educational Codeforces Round 107. risujiroh is top 1 but his solution for problem G is $$$\mathcal{O}(n^2)$$$. A bunch of people tried to hack him but all these tests work like 4.6 seconds and TL is 5 seconds.

So here goes my challenge. I'm really interested in how to hack it so the first person who will hack risujiroh's solution in the next 24 hours (until April 14th 2021 19:15 UTC) will get $50 from me if you'll share your test generator with me.

Good luck if you're interested!

UPD. I'm sad to announce that nobody accomplished it. I wasn't expecting this scenario so I decided to donate $50 to charity. I chose this. It's a Russian organization that helps people to overcome domestic violence problems.

Hey! I decided to record myself while solving rounds. It's my first attempt and an experiment for my channel. Check out my Educational Round 107 screencast.

Leave a comment if you have anything to say. Did you find it helpful? Is it just a waste of time? Or maybe I should improve something? I've already noticed that in the future I should be aware of the fact that I've got my camera in the right bottom corner so I shouldn't draw there. Maybe you noticed anything else?

When I was in high school I once learned about wavelet tree and I was really impressed. But over time when I learned more tricks I started thinking: is there any essential need in it? Because it seems like merge-sort tree with fractional cascading solves all the same problems and its time complexity is $$$O(\log n)$$$ which is better than $$$O(\log C)$$$.

So, am I right or not? Does anyone know any cases where it's helpful to use wavelet tree?