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-овские исходники статей и другие материалы доступны на гитхабе.
Со списком статей, которые уже написаны, можно ознакомиться в оглавлении документа, но я также продублирую его здесь:
- Префиксные суммы (стандартная тема, но я попытался затронуть более продвинутые моменты, которые очевидны опытным участникам, но нигде, кажется, не прописаны)
- Разреженные таблицы (здесь нет особо ничего нового, эта статья нужна скорее как пререквизит к статье про disjoint sparse table, которой пока нет)
- Дерево отрезков снизу
- Segment Tree Beats
- RMQ offline. Вариация алгоритма Тарьяна
- Алгоритм Фараха-Колтона и Бендера (советую обратить внимание на конец статьи, потому что там представлен занимательный линейный алгоритм, который одновременно очень просто пишется, и при этом сильно быстрее ФКБ на практике)
- Дерево Ли Чао (с улучшениями: минимум кусочно-линейных функций и ленивые обновления)
- Двоичные подъемы с линейной памятью
- Персистентный Convex Hull Trick
- Нахождение обратных ко всем остаткам за $$$O(p)$$$ (два самых простых метода)
- Поиск факториала по простому модулю
- Поиск факториала по простому модулю за $$$O\left(\sqrt{\min(p, n)} \log n\right)$$$
- Обращение Мёбиуса, свертка Дирихле
- Квадратный корень по простому модулю за $$$O(\log p)$$$
- Дискретное логарифирование (+ вариация для ответа на много запросов)
- Преобразование Уолша-Адамара и xor-and-or-свертки, SOS-DP
- Рандомизированный алгоритм поиска пары ближайших точек на плоскости за $$$O(n)$$$
- Рандомизированный алгоритм проверки пересечения полуплоскостей на непустоту за $$$O(n)$$$
- Рандомизированный алгоритм поиска минимальной покрывающей окуржности множества точек на плоскости за $$$O(n)$$$
- Поиск пересечения полуплоскостей при условии, что известна точка внутри этого пересечения
- Генерация случайных чисел, и все, что с этим связано
- Стресс-тестирование
- Быстрый ввод-вывод в C++
Было бы здорово, если бы вы оформили свой труд не в виде одного pdf-документа, а в виде сайта с отдельными статьями (например, mediawiki, как у neerc.ifmo, или чего-то блогоподобного, как у algorithmica, brestprog или usaco.guide). Так и ссылки давать, и комментировать стало бы проще, а вы могли бы прицеплять к статьям собственные видео, повышая тем самым связность.
Даже если сборник продолжит существовать в виде pdf, было бы удобнее, если бы вы вывели на титульный лист дату последнего изменения, как сделали pllk и darren_yao (или на отдельную страницу — краткий лог последних правок, как на e-maxx).
В любом случае, спасибо за вашу работу.
Да, я согласен!
Насчет сайта. Я к сожалению ничего не понимаю в вебе и т.п., так что это не тривиальная задача для меня. Но я тоже убежден, что это нужно сделать.
Насчет лога. Да, я сделаю специальную страницу с изменениями, когда таковые начнут появляться. Идея с датой последнего обновления тоже хорошая, возьму на вооружение.
Все же хотелось бы в то же время иметь вариант в виде PDF. Скорее всего это относится к тем, кто любит читать с листа, а не с монитора из-за меньшей нагрузки на глаза. Думаю, что таких людей немало. Плюс, в подобном варианте можно отобразить последовательность чтения, которую предполагает автор для лучшего понимания, в отличии от e-maxx, на котором есть только разделение на темы. Наверняка можно сделать и то и другое без сильных затрат на поддержку PDFки с помощью пары скриптов. Но идея подобного проекта действительно отличная. Удачи!
Я не знаю, почему ваш коммент задизлайкали) Да, если будет сайт, то одновременно с ним будет существовать и pdf-ка, это не проблема. Однако я не совсем понимаю, почему на сайте нельзя оставить последовательность повествования. Там же точно так же список статей упорядочен и разделен на темы.
Большое спасибо за интересные темы, красивую верстку и оформленный код. Исходник определенно сделан в LaTeX, так же сделан и e-maxx. Люди, которые переводят e-maxx на английский https://cp-algorithms.com/ , используют Markdown на гитхабе https://github.com/e-maxx-eng/e-maxx-eng/ , но через pandoc можно конвертировать LaTeX в HTML не хуже.
Несколько усовершенствований, такие как упрощенная коллаборация и доступность в веб-форме, решается использованием GitHub, на котором хранится LaTeX и картинки. Они компилируются pandoc в HTML-файлы, которые заливаются в тот же или соседний репозиторий и доступны через GitHub Pages по адресу username.github.io. Буду рад помочь в телеграме, если понадоблюсь.
Да, можете написать мне в телеграме. На данный момент я все таки придерживаюсь мнения, что LaTeX — добро, а Markdown — зло, так что хотелось бы остаться в латехе. Я нашел вот такую вот штуку, но не уверен, что это то, что нужно.
Шрифт для вставок кода не очень хороший, так как из-за больших пробелов между символами сильно ограничивается вместимость одной строки.
Ну да, действительно. А еще я заметил, что если копировать код из латеха, то отступы все едут. Интересно, можно ли как-то решить эту проблему или нужно везде добавлять ссылки на pastebin? Вдруг кто-нибудь знает.
Большое спасибо за статьи!
Мне кажется, что в разделе про дискретное логарифмирование есть неточность (или я не вполне понимаю то, что там написано). Кажется, что идея с ответами на много запросов работает только для $$$p^{\alpha}$$$ и $$$2p^{\alpha}$$$, иначе первообразного корня не будет существовать.
И еще по поводу поиска обратных за $$$O(p)$$$: идея поиска обратных через факториалы может быть легко переделана для поиска обратных к первым $$$n$$$ числам за $$$O(n)$$$ (просто, кажется, в статье это указано как плюс второго варинта). Для этого достаточно $$$n!$$$ посчитать за $$$O(n)$$$, после этого ровно тот же код проходит
Спасибо за замечания!
Первое уже было найдено и исправлено. Появится в ближайшем обновлении документа.
Второе — это интересно. Действительно. Почему-то раньше об этом никогда не задумывался, добавлю.
Добавил страницу с последними изменениями, внес минорные тестовые исправления, поставил дату последнего обновления на титульный лист и полезные ссылки на следующую страницу.
Мое мнение про статью "ДО снизу": мне кажется что лучше делать n не фиксированным, а зависимым от входных данных. Тогда надо будет дополнять n до степени двойки так:
n = 1 << (__lg(n - 1) + 1). Понятно, что тогда нуженvector. И еще: может лучше классом?(From: https://habr.com/ru/company/otus/blog/485194/ and https://habr.com/ru/post/115026/)
Лето подходит к концу, так что скоро будут новые статьи. А пока что я выложил все теховские исходники в открытый доступ на гитхаб.