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!

Check out top 1: https://vm.tiktok.com/ZSebupBUg

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.

Recently, there've been at least two blogs that were called "petitions". I have no idea why people use this exact word in this context but for me, it seems... overly posh. So this blog is a petition to stop calling every suggestion a petition.

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!

В мае я уже рассказывал про то, что я занимаюсь созданием нового ресурса для изучения сложных алгоритмов и структур данных для спортивного программирования, о которых сложно где-то найти информацию (особенно на русском языке), и не только. Тогда он был доступен только в формате pdf-документа, что, очевидно, не всегда является наиболее удобным способом потребления информации. Но теперь после длительных страданий я все таки смог переделать все это в формат сайта, который теперь доступен по адресу peltorator.ru. Если вам удобнее пользоваться pdf-версией, не переживайте, она все еще будет обновляться параллельно с сайтом.

Теперь мне не нужно больше так много страдать с вебом, так что новые статьи будут совсем скоро :)

Буду рад любым замечаниям, предложениям и помощи:

• Как можно улучшить интерфейс сайта
• Какие есть ошибки и опечатки в текстах статей
• Если вы хотите помочь мне в написании какой-то статьи на неизвестную тему, в которой вы разбираетесь, я буду рад
• Если вы знаете какую-то неизвестную тему, но не хотите сами ничего делать, все равно буду рад, если вы мне сообщите о существовании этой темы: тогда я смогу ее изучить и написать статью

Обо всем этом можно писать мне в телеграме. А если вам совсем не лень, то ваши замечания можете делать в формате пул-реквестов на гитхабе проекта.

Всем привет!

Начинается новый учебный год, вместе с ним стартует и сезон олимпиад. Этот пост будет полезен школьникам, которые хотят заниматься олимпиадным программированием, но не знают где.

Сейчас открыт отбор в кружок по олимпиадному программированию «Тинькофф Поколение». Один из классных плюсов кружка — он абсолютно бесплатный, но нужно написать вступительный контест, который открыт до 12 сентября включительно. Зарегистрироваться и начать решать можно здесь: algocode.ru.

Ниже мы постараемся подробнее описать как все устроено в кружке. Если у вас останутся вопросы, задать их можно в комментариях к посту или в telegram (внизу есть наши контакты).

Каждый год мы стараемся быть лучше и действительно полезными, так что в этом году кружок будет еще интереснее.

Про формат занятий

По результатам отборочного контеста мы разделим участников на учебные параллели. У каждой параллели есть своя группа преподавателей, которые будут читать лекции, помогать с решением задач и написанием кода. Их всегда можно будет попросить объяснить непонятную тему, подсказать тест или найти ошибку в программе.

В начале занятия проводится разбор предыдущих туров: тематического и дистанционного. Далее идет лекция или семинар (а иногда и то, и другое). На лекциях преподаватели рассказывают новые алгоритмы, а на семинарах школьники сдают задачи с листочка преподавателям, и по ходу занятия задачи разбираются.

После каждого занятия будут опубликованы тематические туры на пройденную тему. Кроме тематических туров, каждую неделю будут выдаваться дистанционные туры к различным этапам Всероссийской олимпиады школьников по информатике:

• с сентября по декабрь — к муниципальному этапу;
• с сентября по январь — к региональному этапу;
• с сентября по март — к заключительному этапу.

Занятия будут проходить по субботам с 16:00 до 21:00 по московскому времени.

В прошлом году из-за пандемии мы проводили очные занятия для школьников из Москвы и онлайн для ребят, которые не могли посещать занятия очно. В этом году планируем продолжить опыт гибридных занятий: очно+online (каждый год во время анонса кружка прилетают вопросы про участие в кружке ребят из других стран. Мы будем рады всем, но нужно понимать, что основной фокус на школьников из России, и во время подготовки к олимпиадам есть своя специфика).

1. Онлайн

Мы проводим занятия для участников из всех регионов. Лекции проводятся в Zoom. Занятия проводят преподаватели, которые также очно преподают в московском кружке и принимают участие в подготовке олимпиад и проведении сборов. Это возможность заниматься на равне со школьниками из крупных городов.

2. Очно

Очные занятия проходят в Штаб-квартире Тинькофф

• Москва: Штаб-квартира Тинькофф,  ст. м. Водный стадион, БЦ «Водный», Головинское шоссе 5А

Если наберется, достаточное количество участников, мы готовы проводить занятия очно в Центре Разработки Тинькофф в Санкт-Петербурге по адресу:

• Санкт-Петербург, ул. Херсонская, дом 12\14, БЦ «Ренессанс Правда»

Описание параллелей

Параллель А

Параллель рассчитана на опытных олимпиадников: участников и дипломантов Всероссийской олимпиады по информатике прошлого года. Научим решать сверхсложные и нетипичные задачи.

Преподаватели: Филипп grphil Грибов и Егор peltorator Горбачев

Примеры тем:

• Нетривиальные алгоритмы и задачи теории чисел.
• Декомпозиции деревьев: centroid, heavy-light, ladder.
• Задачи на графах: паросочетания, остовы и их применение в задачах.
• Продвинутые структуры данных: неявные деревья отрезков, двумерные структуры, персистентные структуры, segment tree beats.
• Корневая декомпозиция.
• Быстрое преобразование Фурье.
• Строковые структуры данных: Ахо-Корасик, суффиксный массив, суффиксный автомат.
• Алгоритмы поиска потоков в сетях, алгоритмы поиска минимальных глобальных разрезов.
• Продвинутые геометрические алгоритмы: вращающийся scanline, пересечение полуплоскостей, диаграмма Вороного, триангуляция Делоне.
• Splay-деревья, link-cut.
• Нетривиальные алгоритмы на графах: венгерский алгоритм, алгоритм двух китайцев, дерево доминаторов.
• Матроиды.
• Алгоритмы во внешней памяти.
• И многое-многое другое...

Параллель A'

Для опытных олимпиадников — участников финала Всероса по информатике, Открытой олимпиады и других перечневых олимпиад.

Преподаватели: Иван isaf27 Сафонов, Константин KiKoS Амеличев и Дмитрий _overrated_ Умнов.

Примеры тем:

• Структуры данных: от дерева отрезков до splay-дерева.
• Оптимизации динамического программирования: convex hull trick, meet-in-the-middle, разделяй и властвуй
• Декомпозиции деревьев: centroid, heavy-light, ladder.
• Задачи на графах: паросочетания, потоки, dinamic connectivity problem.
• Геометрия: выпуклые оболочки, сумма Минковского.
• Строки: хэши, Ахо-Корасик, суффиксный массив.
• Полезные трюки: STL, битовые оптимизации, стресс-тестирование.

Параллель B

Для тех, кто владеет С++ или Java и уверенно проходит на региональный этап Всероса.

Преподаватели: Максим DebNatkh Деб Натх, Артем SoMuchDrama Рябов, Игорь Siberian Маркелов.

Примеры тем:

• Графы: BFS, DFS, их применения. Алгоритмы поиска кратчайших путей во взвешенных графах (алгоритмы Форда — Беллмана, Дейкстры и Флойда). Минимальные остовные деревья. Паросочетания, алгоритм Куна.
• Деревья: алгоритм поиска наименьшего общего предка в дереве. Эйлеров обход. Декомпозиции дерева (heavy-light, centroid).
• Строки: префикс-функция, Z-функция, бор, автомат Ахо-Корасик, хеширование, суффиксный массив.
• Динамическое программирование: одномерное, многомерное; по подмаскам, подграфам, подотрезкам, подмножествам, профилю и изломанному профилю.
• Структуры данных: дерево отрезков с массовыми операциями, декартово дерево, sparse table, система непересекающихся множеств, дерево Фенвика.
• Геометрия: базовые примитивы, алгоритмы построения выпуклой оболочки, построение касательной к выпуклому многоугольнику.
• И много других тем: теория Шпрага-Гранди, корневая декомпозиция, метод разделяй и властвуй, решето Эратосфена, задача дискретного логарифмирования, meet-in-the-middle.

Параллель B'

Для тех, кто на базовом уровне владеет С++, Python или Java и участвовал в муниципальном этапе Всероссийской олимпиады школьников по информатике прошлого года.

Преподаватели: Глеб Glebodin Лобанов, Александр rationalex Гришутин и Андрей forestryks Одинцов.

Примеры тем:

• C++ с нуля.
• Структуры данных: система непересекающихся множеств, sparse table, дерево отрезков.
• Динамическое программирования: от самых базовых задач до динамики по подстрокам, подмножествам и цифрам.
• Алгоритмы на графах: от обходов графа до поиска мостов, точек сочленения, построения минимального остововного дерева.
• Алгоритмы на деревьях: LCA, LA, эйлеров обход.
• Базовые алгоритмы на строках: префикс-функция, Z-функция, хеши и бор.
• Геометрия: от векторов и прямых до многоугольников и выпуклой оболочки.

Параллель C

Параллель рассчитана на школьников, которые никогда не занимались олимпиадным программированием или неуверенно себя чувствуют в базовых темах и хотят познакомиться с ними поближе. Необходимо знать синтаксис любого языка программирования и уметь решать простейшие задачи по математике и программированию. В эту параллель не зачисляются школьники, которые перешли в 11 класс.

Преподаватели: Егор w8_m8 Гутров и Полина Romanchenko Романченко.

Примеры тем:

• C++ с нуля.
• Сортировки: квадратичные, сортировка слиянием, быстрая сортировка.
• Бинарный поиск: обычный и по ответу.
• Теория чисел: алгоритм Евклида, разбиение числа на простые.
• Простейшие структуры данных: vector, set, map, стек, очередь, дек.
• Базовое динамическое программирование: с нуля до задач о рюкзаке, НВП, НОП.
• Подсчет комбинаторных объектов.
• Базовые алгоритмы на графах: хранение, поиск в глубину, ширину, алгоритмы Дейкстры, Флойда, Форда — Беллмана, конденсация графа.
• Простая геометрия: векторы, прямые, окружности.

Зарегистрироваться и начать решать можно по ссылке: algocode.ru.

Другие направления

Кроме алгоритмов и структур данных у нас также есть несколько других интересных направлений: олимпиадная математика, машинное обучение и глубокое обучение.

Контакты

Если хотите узнать что-то подробнее, можете написать Тане TKolinkova Колинковой в телеграм @Tatyana_Kolinkova или на почту [email protected].

Иногда я нахожу всякие прикольные штуки про спортивное программирование и связные области, и хочется поделиться этим со всем миром. Обычно в таком случае люди дают задачи на найденные трюки на своих контестах, но я задачи придумывать не умею, так что я решил просто рассказывать о них в телеграме.

Ссылка на телеграм канал

Подписывайтесь, если вам такое интересно :)

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

TL;DR Хочется сделать новый e-maxx с актуальными алгоритмами и удобными реализациями с упором на продвинутые алгоритмы, про которые мало где можно прочитать. Сейчас уже есть 23 статьи, собранные по ссылке: peltorator.ru/cp_book.pdf. Последние изменения доступны по ссылке. TeX исходники доступны на гитхабе. Веб-версию можно найти по сссылке peltorator.ru.

Всем привет!

Я хотел бы показать, над чем я работал последние 4 месяца. Начнем издалека. Все мы любим e-maxx, все мы им пользуемся. Однако я уверен, вы тоже чувствуете, что он не идеален. Во-первых, он уже не обновлялся 9 лет, и за это время появилась куча разных новых актуальных алгоритмов, о которых можно прочитать только в случайных статьях на codeforces и подобных сайтах, да еще и в основном только на английском языке (или китайском). Во-вторых, часто коды, которые есть на e-maxx'е, используются по принципу "я не знаю, что там написано, но оно работает, поэтому не буду трогать". Хочется все же, чтобы к статьям по возможности были приложены красивые, удобные и понятные реализации.

Такие мысли и привели меня к идее сделать в некотором смысле e-maxx 2.0. Безусловно, это очень большая работа, поэтому на это уйдет много времени, но уже сейчас я хотел бы поделиться некоторым промежуточным результатом. Чтобы это не было источником, в котором в сотый раз рассказывают, что такое DFS и BFS, я решил пойти с обратной стороны и начать с тех алгоритмов, о которых сложно найти какую-либо информацию. Тем более на русском языке. На данный момент это существует в виде LaTeX-документа, расположенного по адресу peltorator.ru/cp_book.pdf. В будущем, думаю, стоит перевести это в сайт.

А еще помимо текста там есть картиночки! Кажется, они помогают пониманию. И в конце почти каждой главы есть список задач для практики.

Также для ускорения процесса я думаю, что стоит привлечь соавторов. Пока что я собираюсь попросить своих знакомых, однако если вам это интересно, то можете написать мне в телеграме, буду рад любой помощи!

Буду очень признателен любым комментариям и пожеланиям под этим постом. Если вы нашли опечатку или тем более ошибку, то тоже обязательно сообщите мне о ней (если вам не лень), я в срочном порядке все исправлю. Актуальный документ всегда будет находиться по той же самой ссылке. Возможно, стоит создать еще страницу, на которой будут перечислены все последние важные изменения в документе.

P.S. Если вы начинающий участник соревнований по программированию, то, пожалуйста, не воспринимайте это как todo-лист. Алгоритмы, конечно, играют роль в спортивном программировании, но намного большую роль играет практика решения задач.

UPD: Теперь последние изменения документа доступны по ссылке. Также на титульной странице документа теперь написана последняя дата обновления, а следующая страница содержит полезные ссылки.

UPD2: Теперь TeX-овские исходники статей и другие материалы доступны на гитхабе.

Со списком статей, которые уже написаны, можно ознакомиться в оглавлении документа, но я также продублирую его здесь:

1. Префиксные суммы (стандартная тема, но я попытался затронуть более продвинутые моменты, которые очевидны опытным участникам, но нигде, кажется, не прописаны)
2. Разреженные таблицы (здесь нет особо ничего нового, эта статья нужна скорее как пререквизит к статье про disjoint sparse table, которой пока нет)
3. Дерево отрезков снизу
4. Segment Tree Beats
5. RMQ offline. Вариация алгоритма Тарьяна
6. Алгоритм Фараха-Колтона и Бендера (советую обратить внимание на конец статьи, потому что там представлен занимательный линейный алгоритм, который одновременно очень просто пишется, и при этом сильно быстрее ФКБ на практике)
7. Дерево Ли Чао (с улучшениями: минимум кусочно-линейных функций и ленивые обновления)
8. Двоичные подъемы с линейной памятью
9. Персистентный Convex Hull Trick
10. Нахождение обратных ко всем остаткам за $$$O(p)$$$ (два самых простых метода)
11. Поиск факториала по простому модулю
12. Поиск факториала по простому модулю за $$$O\left(\sqrt{\min(p, n)} \log n\right)$$$
13. Обращение Мёбиуса, свертка Дирихле
14. Квадратный корень по простому модулю за $$$O(\log p)$$$
15. Дискретное логарифирование (+ вариация для ответа на много запросов)
16. Преобразование Уолша-Адамара и xor-and-or-свертки, SOS-DP
17. Рандомизированный алгоритм поиска пары ближайших точек на плоскости за $$$O(n)$$$
18. Рандомизированный алгоритм проверки пересечения полуплоскостей на непустоту за $$$O(n)$$$
19. Рандомизированный алгоритм поиска минимальной покрывающей окуржности множества точек на плоскости за $$$O(n)$$$
20. Поиск пересечения полуплоскостей при условии, что известна точка внутри этого пересечения
21. Генерация случайных чисел, и все, что с этим связано
22. Стресс-тестирование
23. Быстрый ввод-вывод в C++

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?"

Всем привет!

В новом видео мы поговорим про удивительную структуру данных Segment Tree Beats (Анимешное дерево отрезков), которая позволяет поддерживать огромное количество операций, с которыми не справляется обычное дерево отрезков. Узнаем, как брать числа на отрезке по модулю, применять операции min= и max=, добавлять к ним +=, а также еще и искать НОД на отрезке с этими операциями. Все это с понятными доказательствами, так что не бойтесь, все будет несложно! В следующей части мы рассмотрим еще больше удивительных запросов, так что не пропустите.

Ссылка на видео

There's also the English version of this video here

Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями и идеями насчет новых видео. Также можете написать мне в телеграм, если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!

Можете зайти на мой канал и посмотреть другие видео, если вы их еще не видели.

Контест с задчами на Segment Tree Beats.

Оригинальная статья на английском

Оригинальная статья на китайском

Реализации алгоритмов из этого видео:

%= на отрезке, = в точке, сумма на отрезке

Ji Driver Segment Tree (min= на отрезке, сумма на отрезке)

min= на отрезке, max= на отрезке, += на отрезке, = на отрезке, сумма на отрезке, минимум на отрезке, максимум на отрезке

Все то, что было в прошлой реализации, но еще и поиск НОДа на отрезке

P.S. Спасибо Golovanov399 за адаптацию названия.

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?

Привет!

Очередное видео! На на этот раз тема немного экспериментальная. В этом видео я в сжатом формате рассказываю все, что надо знать про операцию MEX для того, чтобы решать задачи, в которых она применяется.

Ссылка на видео

There's also the English version of this video here

Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями и идеями насчет новых видео. Также можете написать мне в телеграм, если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!

Можете зайти на мой канал и посмотреть другие видео, если вы их еще не видели.

Контест с задчами на mex.

P.S. Я уверен, что я что-то упустил, так что буду рад, если вы поделитесь в комментариях своими трюками про MEX.

Привет!

Я продолжаю делать видео по алгоритмам, на этот раз тема более базовая. В этом видео я рассказываю про префиксные суммы и то, как с их помощью можно искать сумму на отрезке. Также вы сможете узнать, как легко обобщать префиксные суммы для двумерного, трехмерного, четырехмерного и т.д. случаев. Кроме этого, мы еще поговорим про такую простую концепцию как разностный массив, которая помогает очень легко решать задачи, в которых с первого взгляда хочется использовать всякие сложные структуры данных типа дерева отрезков. И в конце научимся прибавлять на отрезке в массива константы, арифметические прогрессии и даже квадратичные функции.

Ссылка на видео

Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями или идеями насчет новых видео. Также можете написать мне в телеграм, если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!

Если вы еще не видели, можете также посмотреть мое видео про disjoint sparse table тут.

Codeforces группа с контестом

Реализации можно посмотреть по ссылкам:

Поиск одномерных префиксных сумм

Префиксные суммы на структурах для поиска суммы на отрезке

Поиск двумерных префиксных сумм двумя методами: раз, два

Поиск одномерного разностного массива

Разностный массив на структурах для прибавления на отрезке

I've never been good at solving problems about permutations. I find it really hard to illustrate and solve in mind (or on paper) even small examples. Of course, I know that it's a good idea to split a permutation into a set of cycles, but it doesn't really help! I think you understand what I'm talking about. You have these elements that are not in their original positions and you want them to be in the right places. But when you start to make swaps, you should always draw a new picture for every swap to track what's going on.

Yesterday's global round featured this problem about permutations. And it wasn't that hard, but I spent a lot of time trying to figure out what's going on. And this case is even harder because you don't only have a permutation, but also its elements are being flipped every time.

So I'd like to ask you how do you represent permutations and work with them while solving problems?

I personally found out a pretty nice way to do it yesterday. I cut cards out of paper and swapped them with my hands.

You can see that there are two cycles: 123 and 4567. And I could manually swap them and flip while swapping.

It really helped me, but it was still kinda confusing. I needed to perform the same operations several times to figure out what's going on.

I'll be glad if you share your own methods!