Привет.

Меня зовут Ватолин Александр. Я несколько лет занимаюсь обучением людей в разных областях IT — кому-то заходил с алгоритмами, кому-то системный дизайн, кому-то прикладное программирование. Последнее время стало всё больше ML. И в какой-то момент поймал себя на ощущении, которое долго не мог сформулировать: накопилось.

Накопились заметки, которые я писал для одного ученика. Накопились объяснения, которые я повторял по двадцать раз — и каждый раз чуть точнее. Накопились задачи, которые я отбирал руками, потому что в стандартных подборках они либо слишком скучные, либо слишком жестокие. И вот это всё хочется наконец достать из черновиков и отдать наружу — людям, которым это пригодится.

Так появилась идея серии. Начну со спортивного программирования — потому что это та область, где у меня больше всего материала и где, как мне кажется, в рунете до сих пор не хватает спокойных разборов без академического надрыва или излишне завышенных ожиданий. На Codeforces в целом много чего есть, так что мои посты — скорее сублимация моих мыслей и мнений и не претендуют на истину в последней инстанции.

Сегодняшний пост — обзорный: про что вообще CP (спортивное программирование), зачем оно, и как будет устроена серия дальше. Серия постов ориентирована больше на новичков, но я всегда буду рад критике и предложениям от ветеранов.

Что такое спортивное программирование

Если в одно предложение: дана хорошо известная задача из Computer Science — реши её как можно быстрее. Это прекрасное описание я приведу из книги CP4, которое собственно меня натолкнуло на мысли об этой серии постов

В этой фразе три важных слова, и про каждое стоит сказать отдельно.

«Хорошо известная» — значит, задача уже решена. Это не research, никто не ждёт, что вы откроете новый алгоритм. Автор знает решение, и сотни людей до вас его находили. Ваша работа — поднять свой уровень до того, чтобы узнать задачу и применить нужный инструмент.

«Решить» — значит, написать код, который выдаст тот же ответ, что и у автора, на его скрытых тестах, в рамках лимита по времени. Скрытые тесты- отдельная важная штука: они заставляют самому продумывать краевые случаи, а не вычитывать их из условия.

«Как можно быстрее» — это спортивная часть. Без неё CP не было бы CP. Да и решить можно как просто быстрее своего соперника, так и иногда твое решение может оказаться быстрее. Об этом подробнее как-то потом.

Выливается это примерно в это

Возьмём простую задачу. Есть $$$N$$$ стойл на прямой в точках с координатами $$$x_1 \lt x_2 \lt \dots \lt x_N$$$. Нужно расставить в них $$$C$$$ коров так, чтобы минимальное расстояние между любыми двумя коровами было максимально возможным. Никто не любит быть в тесноте, даже коровы.

А теперь смотрите, как с ней справляются разные люди.

Новичок А видит «расставить так, чтобы максимизировать минимум» и пробует перебор: какие $$$C$$$ из $$$N$$$ стойл выбрать. Получается $$$C$$$ из $$$N$$$ — при $$$N = 10^5$$$ это никогда не досчитается. Time Limit Exceeded.

Новичок B пробует жадность: ставим первую корову в первое стойло, дальше — каждый раз в ближайшее свободное, где помещается. Не работает — Wrong Answer. Жадность здесь нечестная: оптимальный ответ зависит от того, какое минимальное расстояние мы целимся обеспечить, а оно заранее неизвестно.

Опытный C говорит: Ага. Мы не знаем, какое расстояние $$$d$$$ достижимо, но если зафиксировать $$$d$$$, то проверка становится тривиальной — жадно ставим коров слева направо, каждую следующую не ближе $$$d$$$ от предыдущей, считаем, поместились ли все $$$C$$$. И заметьте: если $$$d$$$ работает, то любое меньшее $$$d$$$ тоже работает. То есть ответ монотонен по $$$d$$$. Значит — бинпоиск по ответу. Пишет за полчаса, получает Accepted.

Спортсмен D видит фразу максимизировать минимум и сразу пишет бинпоиск по ответу. Десять минут. Эта связка у него рефлекторная.

Разница между B и D — не талант. Разница в том, что D однажды узнал паттерн максимизируй минимум / минимизируй максимум — попробуй бинпоиск по ответу, увидел его в десятке задач и теперь распознаёт автоматически. Этому можно и нужно научиться. Собственно, в этом весь смысл тренировок. К слову, как мне кажется эти 4 уровня в целом сочетаются с 4 дивизионами, что мы видим на CF.

Зачем мне это (и, возможно, вам)

Скажу важное: CP — не самоцель. Никто не платит зарплату за решённые задачи на Codeforces или других платформах.

CP — это средство. Средство стать инженером, который:

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

Эти навыки потом окупаются везде — от собеседований до системного дизайна, от research до обычной продакшен-разработки. Не зря IOI и ICPC изначально задумывались как способ воспитать разностороннего инженера, а не как самостоятельная дисциплина.

Как будет устроена серия

План такой:

• Каждый пост — одна тема. Попробую начать с базовых тем, а потом уйдем в дебри. Может чего необычного из этого и выйдет.
• Посты в целом будут про то, как до алгоритмов дойти, как их запомнить, какие есть признаки для их использования.
• В конце — подборка задач на Codeforces и на моём сайте: от базовой интерпретации алгоритма до сложных задачек.
• Разборы всех задач вы уже найдете и без меня. На CF разборы обычно есть у большинства задач. На моем сайтике я тоже разборы публикую. Ну и там в основном будут задачи попроще.

Если откликается — оставайтесь. В следующем посте начнём с самой базовой, но от не менее полезной техники полного перебора. Постараюсь выпустить его поскорее.

До встречи. Буду рад вашим задачам, вопросам и пожеланиям в комментариях.

Все статьи серии найдёте по тегу #EDU-M.