Пожалуй переоборудую этот канал под блог про мои тренировки в СП) Буду прикреплять ссылки на все алгоритмы о которых говорю.

Сегодня я наконец-то написал алгоритм МО здорового человека. Раньше как то все стороной обходил, а сегодня подвернулся крутой повод написать МО на дереве! Обычный МО работает на отрезках, но благо с путями и поддеревьями можно работать как с отрезками. Вот ссыль на задачу если кому тоже интересно.

Еще из интересного познакомился с преобразованием адамара. Хотя я все еще не полностью понимаю как его применять. Тут и тут еще чуть теории. Если коротко, то преобразование позволяет делать крутые трюки с битовыми оперциями на множествах. Так например можно найти все попарные xor-ы не за O(n^2), а за O(nlogn)!

Вчера пытался порешать ИОИ за 2018 (2 день) и здоровски так пососал) Ни одной так и не смог отправить! Жесткие задачи, но план был больше попробовать, а потом серьезно взяться за разбор и дорешку. Так я уже разобрал первый день и неплохо так прокачался. Вообще очень советую прорешивать задачи с ИОИшек. Они самые топовые, отборные и развивающие!

Решил прорешать этот проблемсет: cses.fi/problemset

Создатели собаку съели на написании книг по СП, так что их вкусу в задачах можно доверять. Основная идея данного проблемсета приводит меня в оргазм! Они задумали сделать ахуительный, тщательно подобранный сет из 1000 задач на почти все топики и техники в СП. Пока что там 300 задач.

Интерфейс очень приятный и удобный. Задачи разделены по топикам. Многие задачи это баяны которые должен знать каждый.

Всем очень рекомендую!

Подборка задач которые я не умел решать, либо решал слишком сложно.

Nearest Smaller Values за линию
Missing Coin Sum
Movie Festival без структур
Towers нвп обычным сетом)
Grid Paths научиться в оптимизацию
Elevator Rides 3^n не пройдет)
Stair Game
De Bruijn Sequence

Сегодня впервые написал дерево фенвика и HLD)

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

А хлд вполне можно написать за 100 строк! Только главное, что следует помнить - чем меньше запросов к ДО, тем лучше!

Если кому интересно, то вот задачи которые я решал
Фенвиком: Path Queries
HLD: Path Queries II

Посмотрел крутую лекцию по матроидам. Звучит страшно (для меня звучало), но все оказалось очень просто и красиво (знание линала приветствуется). Теория матроидов позволяет доказать жадные алгоритмы вроде алгоритмов Краскала или Куна. Всем рекомендую!

Побудила меня узнать про матроиды эта задача: Card Collector

Сегодня узнал, что есть алгоритм МО для динамического массива. Очень красиво как по мне!

Вот задача: Минимальная разница

Лол)

Я проверил, у чувака акк здорового кодера, точно не читер. Но код мы с ним написали идентичный, прям 1 в 1 с пробелами (с точностью до изоморфизма переменных) XDD

Сегодня порешал пару задач по сведению к Max Flow. Если коротко, то Max Flow = Min Cut. И в задачах, где надо разделить объекты на два множества за минимальную цену можно этим воспользоваться.

Для того чтобы изучить тему предлагаю сначала освоить алгоритм Диница.

Вот задачи которые я решал (разбор можно найти во вкладке Editorial):
Zebraness
MUL

Очень интересная теорема о связи максимального паросочетания и минимального вершинного покрытия в двудольных графах пригодилась мне сегодня для решения задачи Coin Grid. Всем рекомендую тоже порешать!

Просто очень полезный блог

Крутая теорема о том как за куб можно найти количество остовных деревьев графа!

Натолкнула меня на нее задача Spanning Tree

Веселая теорема о связи целочисленных многоугольников и внутренних точек с целочисленными координатами. Все же когда-то надо начинать учить геому)

Задача: Грегор и нечетные коровы (простая версия)

Еще узнал, что кроме генерирующих функций есть еще приколы с биномиальными коэффициентами. Ссылки на них:

http://e-maxx.ru/algo/binomial_coeff
https://en.wikipedia.org/wiki/Hockey-stick_identity
https://en.wikipedia.org/wiki/Pascal%27s_rule
https://en.wikipedia.org/wiki/Vandermonde%27s_identity

С того же контеста: Три поросенка

Задача на интересную технику: White and Black Balls (смотреть Editorial)

Идея решения плотно связанна с доказательством чисел каталана (кол-во правильных скобочных последовательностей)

Как обычно, у аткодера лучшие обучающие контесты!

На этот раз я порешал задачу на строки, узнал про алгоритм построения LCP (longest common prefix для пар соседних элементов в суффиксном массиве)

Задача: Common Prefixes

Неожиданность которая стоила мне часа дебага: __builtin_popcount определен только для int (т.е. считать битики в лонгах он не умеет).

Это дополнение открыло мне глаза! Теперь я понял почему я не красный)

Советую посмотреть акки гроссмейстеров и соотнести со своим.

Just for fun)

https://silverfoxxxy.github.io/rating-converter