Привет!

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

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

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

Если вы еще не видели, можете также посмотреть мое видео про 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 любые задачи пропускают).