kactl

КАКТЛ

В этом репозитории хранится KACTL, справочный документ группы ICPC KTH. Он состоит из 25 страниц кода C++, допускающего копирование и вставку, для использования в соревнованиях по программированию в стиле ICPC.

См. kactl.pdf для окончательной, доступной для просмотра версии и content/ для необработанного исходного кода.

Устремления

Алгоритмы KACTL должны быть: полезными, короткими, достаточно быстрыми, хорошо протестированными и, если применимо, читаемыми и легко модифицируемыми. Они не должны быть слишком общими, поскольку код набирается вручную, а это только увеличивает накладные расходы. Из-за нехватки места мы также исключаем очень распространенные/простые алгоритмы (например, Дейкстры) или очень редкие (общее взвешенное сопоставление).

Если вы чувствуете, что чего-то не хватает, что-то можно исправить или заметили ошибку, сообщите о проблеме или отправьте запрос на включение!

Настройка KACTL

Хотя KACTL можно использовать как есть, его также легко изменить, если вы хотите создать персонализированную копию. В частности, вы можете изменить титульную страницу или самостоятельно выбрать алгоритмы для включения — из-за нехватки места не все алгоритмы из репозитория включены в PDF-файл. Вы также можете включить цветную подсветку синтаксиса.

content/kactl.tex — это основной файл KACTL, и его можно редактировать, изменяя название команды, логотип, подсветку синтаксиса и т. д. Он импортирует файлы chapter.tex из каждого подкаталога content/ , которые определяют содержимое каждой главы. К ним относятся исходный код, текст и математические вычисления в форме LaTeX. Чтобы добавить или удалить код из главы, добавьте или удалите соответствующую строку kactlimport из файла chapter.tex . Для лучшего выравнивания вы можете вставить команды hardcolumnbreak , columnbreak или newpage , хотя обычно это делается только перед важными соревнованиями, а не в основной ветке. Алгоритмы, не включенные в PDF-файл, оставлены закомментированными в chapter.tex .

Чтобы собрать KACTL, введите make kactl (или make fast ) на машине *nix — это обновит kactl.pdf . (Windows также может работать, но не проверялось.) doc/README есть еще несколько примечаний по этому поводу.

Советы:

1. Проверьте, что исключено по умолчанию, запустив make showexcluded . Конфигурация по умолчанию выбрана таким образом, чтобы обеспечить разумный баланс для начинающих и продвинутых команд.
2. Воспользуйтесь преимуществом хеширования при вводе этих алгоритмов. Каждый алгоритм имеет 6-значный хэш MD5 в правом верхнем углу. Этот хеш можно сгенерировать с помощью hash.sh или команды :Hash из .vimrc . Хеширование игнорирует пробелы и комментарии.

Стиль кодирования

KACTL использует относительно краткий стиль кодирования с несколькими макросами/определениями типов, определенными в шаблоне, которые помогают сократить код. Ширина строки — 63 символа, с отступами табуляции (в PDF-файле табуляция = 2 пробела).

Каждый алгоритм содержит заголовок с указанием автора кода, даты его добавления, описания алгоритма, статуса его тестирования, а также желательно источника, лицензии и временной сложности.

kactl.pdf должен быть объемом 25 страниц + титульный лист. Иногда сгенерированный файл kactl.pdf сохраняется в репозитории для удобства, но не слишком часто, поскольку это замедляет операции git.

Тестирование

KACTL стремится к высокому уровню уверенности в правильности алгоритма. Тестирование проводится как на онлайн-судьях, так и (для новых алгоритмов) с помощью стресс-тестов, которые сравнивают результаты с более простым алгоритмом для большого количества случайно сгенерированных случаев. Эти тесты находятся в каталоге stress-tests и запускаются с помощью CI при каждом коммите. CI также проверяет, что все заголовки компилируются (за исключением списка исключений в docs/scripts/skip_headers ) и компилируется латекс.

old-unit-tests содержит пару неработающих модульных тестов, последний раз обновленных около десяти лет назад.

Лицензия

Как обычно для конкурсных программ, ситуация с лицензированием немного неясна. Многие исходные файлы помечены лицензией (мы стараемся использовать CC0), но многие и нет. Однако, по-видимому, следует ожидать доброй воли со стороны других авторов, и во многих случаях разрешение не требуется, поскольку код не распространяется. Чтобы облегчить отслеживание событий, в исходных файлах отмечаются источники и авторы.

В stress-tests все неявно CC0, кроме эталонных реализаций, взятых из Интернета.