Всем привет!

В новом видео мы поговорим про удивительную структуру данных 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!

Привет!

Я сделал видео про disjoint sparse table. Это некоторое обобщение обычного sparse table'а, который расширяет возможности его применения.

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

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

Я собираюсь регулярно выпускать видео по алгоритмам в будущем. Как по основам (префиксные суммы, бинарный поиск, сортировки и тд), так и по провинутым темам (heavy-light декомпозиция, link-cut tree, лямбда-оптимизация, FFT и другие). Так что если вам это интересно, подписывайтесь на канал, чтобы их не пропустить!

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

Самая простая

Удобная версия с шаблонами

Без дополнения до степени двойки

Группа с контестом

Спасибо за внимание!

Привет всем!

Пару дней уже пытаюсь найти адекватную реализацию пересечения полуплоскостей, но никак не получается. Кто-нибудь мог бы, пожалуйста, подсказать, где можно найти код, который по данным прямым находит стороны фигуры, которая получается при пересечении полуплоскостей, соответствующих данным прямым, за $$$O(n \log n)$$$.

P.S. Желательно, чтобы прямые хранились в виде $$$(a, b, c)$$$.

Куда делись все анонсы/соревнования Вк-капа? Он умер?

Здравствуйте!

Уже несколько месяцев я нахожусь в раздумье: какой новый ник поставить себе на КФ. У меня столько вариантов, даже не знаю, какой выбрать. А может быть вы мне предложите какой-нибудь вариант? Лайкайте комменты с понравившимися вариантами, победителя определим до 10 января, обещаю поменять ник на тот вариант, который наберет наибольшее количество лайков (ну или наименьшее количество дизлайков). P.S. Поминковые ники не рассматриваются, сорян.

Мне кажется, что вкладка "рейтинг(все)" не работает. Нет никакой разницы между вкладками "рейтинг" и "рейтинг (все)". Но есть ershov.stanislav, который должен быть в топе на вкладке "рейтинг (все)".

Несколько дней назад 300iq написал в блоге, что он покрасит волосы в розовый на неделю, если он не станет легендарным гроссмейстером до нового года, но 300iq уже успел стать им((( На самом деле у нас есть еще один шанс! Если мы соберем 300 iq лайков под этим постом, 300iq ПОКРАСИТ волосы в розовый! Давайте сделаем это вместе.

График результатов контеста не очень удобный. Если навести на точку(раунд), высвечивается ссылка на него, но если рядом с этим контестом есть другие, то навести на эту ссылку очень сложно, а иногда вообще не представляется возможным. Может было бы удобнее, если бы можно было нажимать на саму точку для перехода по ссылке. Или что-то в этом роде

7 ноября 2017 года мы с соавтором отправили на проверку div1+div2 раунд. На момент 13 мая 2018 года координаторы Codeforces не ответили нам вообще ничего, хотя при публикации раунда пишется: "После публикации ориентировочно через пару дней — пару недель вы получите фидбек от Codeforces в виде комментариев к предложению контеста и задачам". Также я знаю, что некоторые раунды проверяют реально в течение недели с момента их публикации, а раунды некоторых авторов проходят с разницей в неделю, во всем этом есть какая-то несостыковочка( В последнее время мы всякими способами пытались выйти на координаторов Codeforces, но единственное, что нам отвечали — это "раунды проверяются по порядку". Не поймите меня неправильно, я не пытаюсь наезжать на координаторов Codeforces или что-то еще. Я просто хочу понять, как такое происходит? Даже если координаторам не понравился наш раунд, то они бы оставили хоть какой-то фидбек, я думаю. И я очень сильно сомневаюсь, что им не понравились сразу ВСЕ задачи раунда(судя по качеству задач на некоторых раундах в последнее время(а еще задачи, которые дают еще раз в практически такой же формулировке спустя 3 месяца на Educational'ах или просто общеизвестные div3 F), на CF любые задачи пропускают).