Университет ИТМО. Четвертьфинал ACM ICPC

Четвертьфинал ACM ICPC: условия, задачи, победители

В Петербурге завершился четвертьфинал международного чемпионата по спортивному программированию ACM ICPC в северном подрегионе. Команда Университета ИТМО, в состав которой входят Владимир Смыкалов, Иван Белоногов и Илья Збань, единственная решила все одиннадцать задач турнира и заняла первое место.

ACM ICPC, или международный командный чемпионат по программированию Ассоциации вычислительной техники, — крупнейшая и самая престижная студенческая олимпиада по спортивному программированию. Для того, чтобы встать в один ряд с мировыми звездами программирования, нужно собрать команду из трех человек и приехать на региональный отбор в четвертьфинале. Россия наряду с Узбекистаном, Казахстаном, Арменией, Грузией, Киргизией и Азербайджаном входит в северо-восточный регион, разбитый на подрегионы, в каждом из которых проходят свои соревнования. Благодаря этому программистам не приходится ехать через всю страну, ведь присутствовать на отборе нужно лично. Архангельская, Ленинградская, Мурманская, Новгородская, Псковская области и республика Карелия объединены в северный подрегион, и соревнования здесь проводит Университет ИТМО — альма-матер чемпионов ACM ICPC.

У этого турнира есть ряд особенностей, отличающих его от остальных чемпионатов по спортивному программированию. Здесь нет места одиночкам: шансы на победу выше у трех участников, которые умеют работать в команде. Попробовать свои силы могут только студенты вузов моложе 24 лет, причем участвовать в четверть- и полуфиналах можно только пять раз, а в финале — два раза.

Университет ИТМО. Четвертьфинал ACM ICPC
Университет ИТМО. Четвертьфинал ACM ICPC

Задания для региональных этапов составляют члены жюри, среди которых участники и победители ACM ICPC прошлых лет, а также их тренеры. Например, в жюри северного региона постоянный тренер чемпионов Университета ИТМО Андрей Станкевич, двукратные чемпионы мира Геннадий Короткевич, Нияз Нигматуллин, чемпионы мира Павел Маврин, Борис Минаев, Артем Васильев, Максим Буздалов, Павел Кунявский, а также Михаил Дворкин, Дмитрий Штукенберг, Егор Куликов и Виталий Аксенов. Возглавляет жюри заместитель заведующего кафедрой компьютерных технологий Университета ИТМО Георгий Корнеев.

В зависимости от уровня команд в некоторых регионах для решения предлагают упрощенные версии задач. Например, на тех же задачах, что и в Петербурге, проходил четвертьфинал восточного региона в Екатеринбурге, а участники из Армянского, Казахстанского, Азербайджанского и Таврического (республика Крым) подрегионов решали упрощенные задачи. В среднем задач бывает около десяти. Ответы проверяются автоматически через специально разработанную для этого систему, которая подставляет входные параметры и сверяет ожидаемый ответ с тем, который выдает программа команды. Решение должно укладываться в лимиты по памяти и времени выполнения — алгоритм должен обрабатываться, например, не больше двух секунд и потреблять не больше 256 мегабайт оперативной памяти.

Университет ИТМО. Четвертьфинал ACM ICPC
Университет ИТМО. Четвертьфинал ACM ICPC

Кроме того, задачи значительно различаются по сложности (с условиями можно ознакомиться здесь). Для самой первой задачи Anniversary Cake участники должны были составить алгоритм для разрезания прямоугольного торта на две части: на торте две свечи, на каждом куске должно остаться по одной, размер торта выражен в целых числах. Алгоритм должен принимать шесть параметров (размеры торта и координаты свеч) и отдавать четыре — координаты начальной и конечной точки разреза, которые тоже должны быть целыми числами. С решением справились 89 команд из 107, приехавших на петербургский четвертьфинал ACM ICPC. А вот с решением задачи Hard Cuts (разрезать прямоугольник на наименьшее количество квадратов, стороны которых выражены целыми числами) справилась только первая команда Университета ИТМО. В ее состав входят Владимир Смыкалов, Иван Белоногов и Илья Збань.

Три первые строчки турнирной таблицы заняли первая команда Университета ИТМО (Смыкалов, Белоногов, Збань), первая команда Санкт-Петербургского государственного университета (Пышкин, Ершов, Сайранов) и первая команда Санкт-Петербургского академического университета (Богомолов, Подгузов, Смирнов). Всего в полуфинал ACM ICPC прошли 14 команд, среди которых Университет ИТМО представляют 4 команды, 5 команд СПбГУ, по 2 команды из СПбАУ и Петрозаводского государственного университета, а также команда Северного (Арктического) федерального университета. Полуфинал также состоится в Университете ИТМО 3−4 декабря 2016 года.

Добавим, что финал ACM ICPC пройдет с 20 по 25 мая 2017 года в Рапид-Сити (США).

Редакция новостного портала
Персоны
Архив по годам:
Пресс-служба