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++