Экскурс в ACM/ICPC

Экскурс в ACM/ICPC

ACM/ICPC (или просто ICPC) — крупнейшая студенческая командная олимпиада по программированию. Это мероприятие приравнивается к чемпионату мира по программированию. Данная статья открывает новую одноименную категорию на сайте, где мы будем разбирать интересные олимпиадные задачи.

Начну с небольшого экскурса в историю и правила проведения чемпионата. Четвертьфинальные и полуфинальные этапы чемпионата проходят независимо в своих регионах, победители которых проходят в следующий этап. Лучшие команды из каждого региона по итогам полуфинала собираются вместе в одном из городов мира и выясняют отношения в финале. Чемпионат командный, в каждой команде три участника. В распоряжении команды один ПК, некоторое количество времени (обычно 5 часов) и ряд поставленных задач (как правило, 5-10 задач). Каждая задача имеет условие, формат входных и выходных данных, ограничение по времени и по памяти. Решением задачи является программа, написанная на одном из доступных правилами языков программирования (обычно пишут на C). Программы-решения проверяются в автоматическом режиме. Система автоматической проверки выполняет несколько тестов, подавая проверяемой программе входные данные и анализируя выходные согласно условию задачи. Если программа на выходе дает неправильный ответ, превышает лимит допустимой оперативной памяти, выполняется дольше положенного времени (не компилируется, выпадает в runtime error, ну и так далее), то тест не пройден. Задача считается решенной, если программа удачно проходит все тесты, предложенные системой. Вариантов “почти решенная”, “наполовину решенная”, как вы понимаете, нет. При подсчете баллов учитывается количество решенных задач, время и количество попыток, затраченных на их решение.

Российские вузы впервые приняли участие в чемпионате осенью 1993 года, когда был организован новый Восточно-Европейский регион. Регион зарекомендовал себя как очень сильный, а команды из России регулярно занимали и занимают высокие места, не раз становились чемпионами.

Мне посчастливилось побывать на трех четвертьфиналах чемпионата мира по программированию в Дальневосточном четвертьфинальном подрегионе. Пройти выше, к сожалению, не получилось. Для этого необходимо довольно много тренироваться командой, иметь очень опытного руководителя. Четвертьфинал в этом подрегионе проходит в Дальневосточном государственном университете (ДВГУ). Организация на должном уровне, атмосфера замечательная. Эти поездки были, несомненно, одними из самых ярких моментов в студенческую пору. В первый день соревнований по графику регистрация команд, торжественное открытие, а вечером пробный тур, на котором предлагается решить три задачи и, главное, освоиться с системой автоматической проверки решений. Система у них своя, разработана местными умами. Кстати, находится в свободном доступе по адресу http://imcs. dvgu. ru/cats/, можно заходить и практиковаться, есть архив задач, результаты прошедших чемпионатов.

Во второй день непосредственно соревнования. Каждой команде выделяется один ПК, дают ручки, бумагу. С собой ничего приносить нельзя :). В середине действа подают чай с бутербродами. В системе Cats есть возможность задать вопрос жюри по условию задачи, но формулировка вопроса должна подразумевать ответ “да/нет”. Ах да, сами условия на английском языке. Есть также страница статистики в реальном времени, которая к последнему часу соревнований “замораживается” для сохранения интриги и “размораживается” уже на торжественном закрытии.

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

На этом, я думаю, стоит закончить с вводной информацией. Тематика раздела, я думаю, понятна и интересна многим посетителям Винкода. До встречи!


Карта сайта


Информационный сайт Webavtocat.ru