Очень часто люди, даже увлекающиеся темой программирования, не знают как проходят соревнования по так называемому спортивному программированию. Люди же далёкие от этой темы зачастую невольно улыбаются, когда слышат слова "спортивное" и "программирование" в одном предложении. Сегодня я хочу рассказать как проходят контесты (англ. contest) по программированию.
Существует очень много различных форматов проведения контестов, но самый популярных из них - это формат ACM. Этот формат или похожие форматы проведения соревнований используются на большинстве школьных и университетских, региональных и международных соревнований, а также на Чемпионате мире по программированию ACM ICPC. Про соревнования в этом формате и будет дальше речь.
В контесте продолжительностью 5 часов участвуют команды по 3 человека, чаще всего защищающих честь школы или университета.
Состав команды может быть любой, но зачастую есть один алгоритмист (специалист по алгоритмам и структурам данных), один математик (дискретная математика, геометрия, теория вероятностей...), а также один кодер (быстро, качественно пишет и отлаживает код). Конечно же, эти роли могут совмещаться или состав может меняться из стратегических соображений. У меня в университетской команде, например, было 3 программиста и не было математика, и мы достаточно неплохо выступали, просто пропуская сложные математические задачи, так как обычно их немного.
Каждой команде выдаётся один компьютер с настроенным для разработки окружением, таким образом одновременно писать код может только один человек. Окружение включает в себя среды разработки для всех разрешённых языков программирования - обычно это C++, Python, Java, иногда C, Pascal. Доступ к Интернету и любым другим источникам информации или кода закрыт. Более того, командам строго запрещено общаться между собой, иногда на соревнованиях и в туалет сопровождают, чтобы удостовериться в соблюдении правил fair play.
В точно назначенное время контест начинается и все участники начинают читать условия задач. Кто-то читает задачи последовательно всей командой, обсуждая задачи, а кто-то делит их на троих, а затем обсуждают кто что прочитал и какую задачу брать первой - это дело привычки и тактики.
Количество задач в среднем варьируется от 8 до 12, из которых 1-2 очень простые (для разогрева), а еще 2-3 - невероятно сложные (такую задачу называют "гроб"). Количество начисляемых очков за каждую задачу не отличается, поэтому критично важно найти и решить самые простые задачи, а также не тратить время сразу на "гробы".
Задача всегда состоит из описания в свободной форме, описания формата входных и выходных данных, ограничений по времени и памяти, а также примеров. На любых международных или серьезных региональных соревнованиях задачи описаны на английском языке. Формат входных данных гарантируется организатором, а формат выходных данных необходимо строго соблюдать. Любой лишний пробел или округление числа до 2 точек после запятой вместо 3 может не засчитаться как правильный ответ. Таким образом, будущих разработчиков учат быть внимательными, не допускать ошибок и многократно проверять свой код.
Вот пример элементарной задачи с тренировочного портала Codeforces. Естественно, что задачу такого уровня вы не встретите даже на городских олимпиадах учеников средних классов:
Достаточно длинное описание задачи, но еще на середине программисту становится понятно, что решение этой задачи - обычная сортировка по возрастанию. Тут сразу необходимо обратить внимание на ограничения входных данных - 100 символов, это очень мало, и сортировка успешно выполнится за миллисекунды.
Однако, это не самое эффективное решение. Мы знаем, что в формуле есть только сложение и числа 1, 2 и 3, поэтому можно схитрить - посчитать сколько у нас есть в формуле символов "1" (A), "2" (B) и "3" (C), а затем вывести по порядку A однёрок, B двоек и C троек, вставляя плюсы между ними. Этот алгоритм линейный и будет работать быстрее, что не критично конкретно в этой задаче, однако скорость выполнения алгоритма является ключевым фактором при больших входных данных.
Алгоритмисту очень важно знать и уметь оценивать скорость работы алгоритмов - будет обидно потратить 1 час на решение задачи, чтобы понять, что нужно более оптимальное решение, но ты его не знаешь; и не менее обидно потратить 1 час на очень производительное решение задачи с помощью сложных алгоритмов, когда задачу из-за маленьких входных ограничений можно было решить простейшим решением "в лоб" за 5 минут.
После того как команда реализовала и протестировала своё решение оно загружается на сервер, который компилирует и исполняет решение, подставляя тестовые входные данные и сверяя их с ожидаемыми выходными данными. То есть, автор задачи придумывает несколько разных вариантов входных данных и указывает какой правильный ответ должна дать программа участника.
Главным фактором победы является максимальное количество решенных задач, а при их совпадении - суммарное время (в минутах) каждой попытки решения всех решённых задач.
То есть, если решение команды с первого раза успешно прошло все тесты, то команде начисляется +1 к количеству решенных задач, а также начисляется время (штраф), равное количеству минут с начала контеста. Решив первую задачу спустя час после начала команда получит 1 решенную задачу и 60 минут штрафа.
Если же на каком-то из тестов решение "упало" (выдало ошибку или неверный ответ, превысило лимит памяти или "не успело" выполниться за указанное время), то это никак не влияет на текущий штраф. Однако, если эта задача всё же будет решена, к штрафу прибавится сумма минут штрафа всех попыток. Например, если команда неуспешно отправила задачу на 20-й минуте, затем неуспешно на 40-й минуте и сдала задачу на 60-й минуте, то команда получит 120 минут штрафа.
Именно поэтому как в разработке программного обеспечения, так и в спортивном программировании критично важно потратить время, чтобы качественно проанализировать и протестировать своё решение, выявить и проверить все граничные тест-кейсы и стресс-тесты (с данными, ожидаемо приводящими к максимально долгой работе решения).
Также важно выбрать оптимальную тактику и порядок решения задач, правильно и согласованно распределить роли. Например, стоит взять задачу посложнее, которую ты точно решишь без лишних попыток, чем простую, но получить штраф за попытки. У меня однажды были соревнования, на которых было 4 понятных, но непростых задачи, а также одна очень сложная и непонятная - эта сложная задача была отдана одному из программистов, который искал решение к ней, исписав все черновики, в течение 4 часов - столько же времени понадобилось нам, чтобы решить первые 4 задачи. Он выдал нам готовое решение, мы реализовали решение и завершили контест со всеми решенными задачами. Если бы мы взялись за эту задачу в конце, то точно бы не успели её решить.
Верхняя часть таблицы результатов региональных соревнований ACM ICPC в северо-восточной Европе в 2016-2017 году:
Данная таблица доступна всем участникам на портале соревнований в реальном времени. Таким образом, все участники видят какие задачи смогли или не смогли решить другие команды. На таблице видно, что задачи A и F были простыми, их достаточно быстро и почти без ошибок решили больше 150 из 228 команд, а задача I - классический "гроб", так как ни одна команда так и не смогла решить эту задачу.
За один час до окончания соревнований данная таблица обычно замораживается и участники больше не видят изменения в таблице. Иногда участникам предоставляют информацию о попытках других участников, но не говорят успешными они были или нет. Это самый волнительный час для участников контеста - особенно тех, кто находится в самом верху этой таблицы.
Спустя ровно 5 часов после начала контеста приём задач завершается, подводятся итоги и награждаются победители.
Результаты финала Чемпионата мира по программированию 2017 года:
Как проходит Чемпионат мира ACM ICPC? Как попасть в команду?
ACM ICPC - это студенческий чемпионат мира, поэтому каждый участник должен быть студентом университета, чьё имя он защищает.
У каждого хорошего IT-университета есть несколько команд - олимпийский состав, который усиленно (а иногда не очень усиленно) тренируется в течение года, отправляется за счёт университета на международные сборы и соревнования по всему миру. Для того чтобы попасть в этот состав зачастую достаточно просто собрать свою команду и показать себя на внутренних тренировочных соревнованиях, либо дополнив список команд в олимпийском резерве, либо заменив в резерве самую слабую из текущих.
Чаще всего спортивным программированием начинают заниматься не в университете, а еще в 7-9 классе, поэтому зачастую университеты "хантят" со школы успешных олимпийцев, предлагая им гранты, скидки, международные сборы и свободное посещение занятий.
Раз в год проходит четвертьфинал ACM ICPC (отборочные, внутри страны), каждая страна определяет свои правила и города для организации отборочных. Например, в Казахстане четвертьфинал проходит в Алматы, а каждый университет может выставить не более 10 команд. В Казахстане эти отборочные рассматриваются Министерством образования и всеми университетами как чемпионат Казахстана. В России квоты более строгие и университету нужно постараться, чтобы выбить каждое дополнительное место для участия на четвертьфинале.
По результатам внутристрановых соревнований команды отбираются на полуфинал ACM ICPC (региональные соревнования). Регионы строго регламентированы оргкомитетом.
Наш с вами регион называется NEERC - с 2017 года регион именуется Northern Eurasia (северная Евразия), ранее назывался "Northeastern Europe Regional Contest" (северновосточная Европа). Соревнования в регионе NEERC проходят одновременно (параллельно) в 4 городах: Санкт-Петербург, Барнаул, Тбилиси и Алматы. Ближайший полуфинал будет 2-3 декабря 2017 года. Каждый человек может не более 5 раз участвовать в региональных соревнованиях.
Затем, лучшие из каждого региона участвуют в финале, который проходит ежегодно в разных городах. У каждого человека есть возможность только дважды участвовать в финале, так что важно эти две попытки использовать с умом, когда готов.
Хорошее выступление на финале ACM ICPC гарантирует вам грант практически в любой технический ВУЗ, а также предложение по работе в ведущие технические корпорации мира.
Ну и напоследок повод для гордости. Победители ACM ICPC последних 6 лет:
Примеры задач финалов ACM ICPC (PDF):
2014 год, 2015 год, 2016 год, 2017 год
С удовольствием расскажу еще или отвечу на вопросы.
