Петербургская «Битва интеллектов»

С 30 июня 4 июля в Санкт-Петербурге проходил 37-й по счету финал Международного студенческого чемпионата мира по программированию (International Collegiate Programming Contest, ICPC), проводимого под эгидой Ассоциации вычислительной техники (Association for Computing Machinery, ACM) и неизменной поддержке корпорации IBM.

Входные данные

Россия в этом году впервые получила право проводить самое престижное мировое соревнование молодых программистов ACM-ICPC, именуемое также «Битвой интеллектов» (Battle of the Brains). В качестве принимающей стороны выступил Санкт-Петербургский университет информационных технологий, механики и оптики (сокращенно ИТМО) — вуз, которому, безусловно, есть, чем гордиться. Так, команды ИТМО с 2004 г. успели четыре раза одержать победу в соревнованиях, т. е. больше, чем какой-либо другой вуз (у ближайшего вуза — Шанхайского транспортного (Цзяотун) университета — три победы).

В финальной части чемпионата в этом году состязалось 120 лучших университетских команд из 36 стран мира. Из них 15 из России, две из Казахстана, одна из Беларуси. Украину представляли две команды — от Киевского национального университета им. Т. Г. Шевченко (под названием BZFlags) и от Харьковского национального университета им. В. Н. Каразина (SobolevTeam). Первая была в составе тренера Виталия Бондаренко и участников Романа Едемского, Ярослава Твердохлиба и Андрея Максая. Состав второй: тренер Григорий Жолткевич и участники Дмитрий Соболев, Евгений Соболев и Арсений Челноков.

Детали проведения ACM-ICPC в этот раз опустим (вы можете ознакомиться с ними, например, в нашем прошлогоднем репортаже Варшавская «Битва интеллектов»). Напомним, что для победы командам необходимо за пять часов справиться с 11 предложенными задачами. Они держатся в секрете до начала состязания, но заранее было известно, что основной темой в этом году стали большие данные (Big Data) — технологии сбора и оперативной обработки огромных объемов информации и принятия решений на основе полученных результатов.

Любопытно, что в этом году финал ACM-ICPC в качестве гостя посетила фигура мировой величины мира программирования — автор языка С++ Бьёрн Страуструп (Bjarne Stroustrup). Он провел для студентов лекцию, в которой рассказал о языках программирования, соревнованиях, а также преимуществах участия в мероприятиях, подобных ACM-ICPC. По словам г-на Страуструпа, если нужно выразить алгоритм оптимально, если требуется, чтобы структуры данных были представлены открыто, просто и эффективно, языка, более подходящего, чем C++ не найти.

Большинство студентов отдает предпочтение языку C++

Выходные данные

Главная интрига нынешнего финала — противодействие между программистами России и Китая. Конечно, свое слово должны были сказать представители Польши и нашей страны, стабильно занимающие призовые места. Кроме того, по мнению наблюдателей, большие надежды подавала команда Токийского университета.

Однако интрига как таковая если и была, то минимальная. Практически все время в турнирной таблице на первом месте была команда ИТМО, а Китаю (Тайваньскому университету) удалось вырваться в лидеры в лишь начале соревнований, быстрее других решив первую задачу. После четырех часов состязаний, когда приостанавливается процесс обновления турнирной таблицы, подопечные Андрея Станкевича, доцента кафедры компьютерных технологий ИТМО, были на первом месте с 9 задачами, за ними шли коллективы Шанхайского транспортного (Цзяотун) университета и Токийского университета с 8 задачами.

Уже на самой церемонии награждения победителей стало известно, что в течение последнего часа ИТМО отправили судьям еще две оставшиеся задачи, одну задачу на проверку выслали «шанхайцы» и целых три — «токийцы». Иначе говоря, теоретически, у японской команды был реальный шанс одержать победу, пусть и призрачный. Но они им не воспользовались: ИТМО успешно сдали одну из задач, а Токийский университет ни одной.

В итоге, команда ИТМО смогла дать правильные решения к 10 задачам (причем три задачи решила раньше других — за них полагаются отдельные награды). Призом коллектива стал уже хорошо знакомый кубок ACM-ICPC, золотые медали и 12 тыс. долл.

Победители — команда ИТМО (SPb NRU ITMO 1): Михаил Кевер, Нияз Нигматуллин, Геннадий Короткевич и бессменный тренер команды Андрей Станкевич

Золотыми призерами и обладателями награды в 6 тыс. долл. стали команды из Азии — Шанхайского транспортного (Цзяотун) университета (9 задач), Токийского университета (8 задач) и Национального университета Тайваня (8 задач). Кроме того, первые четыре команды получили предложение от IBM о работе/стажировке в корпорации.

«Серебро» и награду в 3 тыс. долл. получили Санкт-Петербургский государственный университет, Варшавский университет, Киевский национальный университет им. Т. Г. Шевченко и Белорусский государственный университет — все команды справились с 8 задачами. Мы поздравляем наших ребят с этим достойным результатом!

Серебрянные призеры ACM-ICPC 2013 — команда КНУ им. Т.Г. Шевченко в составе тренера Виталия Бондаренко и участников Романа Едемского, Ярослава Твердохлиба и Андрея Максая

Бронзовые медали и 1,5 тыс. долл. увезли из Санкт-Петербурга команды Ягеллонского университета (Польша), Московского государственного университета, Университета Карнеги-Меллон (США), Университета Циньхуа (Китай) и Пермского государственного университета.

В региональном рейтинге победители распределились следующим образом: Университет Карнеги-Меллон (Североамериканский регион); Санкт-Петербургский государственный университет информационных технологий, механики и оптики, Россия (Европейский регион); Арабская академия науки и технологии, Египет (регион Ближнего Востока и Африки); Технологический институт аэронавтики, Бразилия (Латиноамериканский регион); Шанхайский транспортный (Цзяотун) университет (Азиатский регион); Университет Нового Южного Уэльса, Австралия (Южно-тихоокеанский регион).

Отдельно необходимо отметить, что вторая украинская команда — SobolevTeam — с 5 решенными задачам расположилась на 37-м месте.

Интересно, что в список из 11 команд, не справившихся ни с одной задачей и не набравших ни одного балла, вошли 5 университетов США, откуда, собственно говоря, пошел чемпионат, а также по одному вузу из Японии, Канады, Сингапура и Египта. Видимо, это был не их день.

В завершение несколько слов о задачах. По словам экспертов, самой простой задачей стала задача F (о распределении блоков питания в двухпроцессорном компьютере), ее решили 105 из 120 команд. Самая сложная — задача B, о расчете выигрыша в азартной игре с произвольной вероятностью выигрыша и количеством ставок. Эту проблему решила лишь команда ИТМО. Ни одна из задач набора не была решена всеми командами, также нет ни одной проблемы, которую не решил хотя бы один коллектив. Полный разбор всех задач доступен в блоге компании «Яндекс», официального спонсора трансляции финала ACM-ICPC 2013.

Финальная таблица (здесь доступна полная версия)

P.S.: Встретимся в столице Урала

На официальной церемонии закрытия олимпиады по традиции было объявлено место проведения следующего финала чемпионата мира по программированию среди студентов. Им стал российский город Екатеринбург, сами же соревнования будут проходить на базе Дворца игровых видов спорта «Уралочка», на площадках Уральского федерального университета, а торжественное закрытие — в ККТ «Космос». Пусть никого не удивляет такой неочевидный выбор, принимающая сторона не обязательно должна быть в числе победителей ACM-ICPC (хотя справедливости ради следует отметить, что студенты Уральского федерального университета, участвующие в финале соревнований с 1998 г., уже трижды становились бронзовыми призерами, а в нынешнем году команда УрФУ заняла довольно высокое 16-е место). Все зависит от заявки.

Билл Поучер: «Поздравляю Санкт-Петербург и ИТМО с обладанием культурой превосходства!»

Как отметил Билл Поучер (Bill Poucher), профессор Университета Бэйлора (Baylor University) и исполнительный директор ACM-ICPC, Россия — пока единственное государство, которое удостоено права два года подряд проводить «Битву интеллектов». «Оргкомитет не мог сказать «нет» ни Санкт-Петербургу, ни Екатеринбургу. На тот момент это были лучшие заявки в мире, представленные нам на рассмотрение», — подчеркнул Паучер.