10 декабря 2018
Командный чемпионат мира по программированию проводится c 1977 года. Команды из России участвуют в нем с 1993 года. Тогда чемпионат мира проводился в два этапа: региональный отборочный и финальный. В 1996 году для команд, представляющих страны, входившие ранее в состав СССР, был выделен Северо-Европейский отборочный регион, ныне называемый Северо-Евразийским. В связи с возросшей популярностью соревнований с 1999 года чемпионат мира стал проводится в три этапа. C 2017 добавился еще один этап - квалификационный. В этом году в чемпионате мира на разных этапах приняли участие около 50000 человек более чем из 3000 университетов 111 стран мира.
В этом сезоне от ИГУ в квалификационном этапе участвовало десять команд. Одна команда представляла физический факультет, остальные - институт математики. Все они успешно преодолели квалификацию и получили право участвовать в четвертьфинале Восточно-Сибирского региона, который включает в себя Красноярский край, Бурятию, Хакасию, Иркутскую и Читинскую область. Этот этап успешно преодолели четыре команды ИМЭИ ИГУ, занявшие девятое, восьмое, седьмое и первое место. Победителями стали студенты третьего и четвертого курсов: Михаил Латышев, Кирилл Антонов и Андрей Чумаченко. По правилам отбора, в полуфинале от ИГУ смогли принять участие только три команды.
Полуфинал проходил одновременно на четырех площадках: в Алма-Ате, Тбилиси, Барнауле и Петербурге. Более пятидесяти команд Сибири и Дальнего Востока соревновались в Барнауле. Всего в полуфинале Северо-Евразийского региона приняли участие около трехсот команд.
Для решения был предложен набор из тринадцати задач разной сложности. Традиционно, задачи не упорядочены, и участники должны сами определять, какие из задач им по силам. На двух относительно простых задачах L и G проверялась готовность участников к соревнованиям такого уровня. Для их решения требовалось умение понимать условие задачи, навыки составления алгоритмов и работы с базовыми структурами данных.
В третьей по решаемости задаче E требовалось составить последовательность из заданного количества ходов шахматной ладьи, которое позволило бы переместить ее из клетки a1 в клетку h8 так, чтобы никакая клетка не была посещена дважды. Несмотря на простую формулировку, эта задача требовала рассмотрения многих особенностей и частных случаев, поэтому отняла достаточно много времени у большинства команд. Четвертая задача F стала медианой в турнирной таблице, с ней справились менее половины участников. Решение этой задачи требовало знания основ теории чисел на уровне решения линейных диофантовых уравнений с двумя переменными. Эта тема достаточно распространена на факультативных занятия по математике в школе, и существенная часть участников региональных олимпиад по математике справляется с подобными заданиями. Сложности, возникшие при решении этой задачи у большинства команд из региональных вузов, хорошо демонстрируют гиперцентрализацию высшего образования в России. По сути, на математических факультетах большинства региональных вузов России, включая федеральные университеты, почти нет студентов с углубленной математической подготовкой на уровне школы. Пятая задача A представляла замаскированную ловушку, в которые попались многие подготовленные команды. В ней для стандартных правил волейбола требовалось определить могли ли команды набрать x и y очков соответственно за матч. Многие команды, в том числе и наша, потратили много времени на попытку рассмотрения всех случаев, что было практически невозможно. Правильное решение заключалось в переборе средствами динамического программирования. В шестой задаче M требовалось реализовать из кубиков заданный граф в трехмерном пространстве. Команды, решившие пять или шесть задач, получали дипломы третьей степени Северо-Евразийского региона.
Седьмая по решаемости задача K, помимо неочевидной идеи решения, требовала знания довольно специфической техники групповых отложенных операций. Задача С традиционно была посвящена кактусам. Кактусом называется граф специального вида, обобщающий понятие дерева. Многие алгоритмы работы с деревьями в существенно усложненном виде переносятся на кактусы, поэтому задача С традиционно является одной из самых нерешаемых. Многие команды даже не стали ее читать, а зря - в этом году задача C была достаточно простой и вполне берущейся. Команды, решившие семь и более задач получали дипломы второй степени и путевку в финал чемпионата мира. Прочие задачи требовали нестандартного подхода и сложной техники решения, поэтому с ними справились лишь единицы.
Команда ИМЭИ ИГУ выступила довольно успешно. Решив пять задач, ребята заняли второе место среди команд Сибири и Дальнего Восток. Результат мог бы быть более высоким, если бы на задачу A было потеряно меньше времени. Но даже это выступление стало самым успешным за всю историю участия ИГУ в этих соревнованиях. Никогда прежде иркутские команды не попадали даже в десятку лучших команд Зауралья, а среди команд Восточной Сибири только в 2013 легендарная команда "Бизоны" из ИМиФИ СФУ смогла достичь второго места. Первое место заняла команда Новосибирского университета с шестью задачами, третье -- Северо-Восточного федерального университета. При этом школьная сборная Иркутска и Ангарска прошлого года, участвуя вне конкурса, решила шесть задач и немного не добила седьмую. Ребята сейчас учатся в СПбГУ на первом курсе и даже не смогли пройти отбор на соревнования. Первое место во всем Северо-Евразийском регионе с одиннадцатью задачами заняла команда МГУ - действующие чемпионы мира. Второе место с десятью задачами - команда МФТИ. В составе команды МФТИ был еще один иркутянин - выпускник лицея № 36 Илья Степанов.
Существенную помощь в подготовке мероприятий, проходящих в Иркутске в рамках командного чемпионата мира по программированию, оказали IT компании "Форус" и "ISPsystem". Успешное выступление иркутян стало еще одним результатом сотрудничества этих компаний с Институтом математики экономики и информатики ИГУ.
Уже несколько лет в ИМЭИ проводятся регулярные тренировки, в ходе которых студенты учатся работать в команде, изучают техники написания и отладки программ, нетривиальные алгоритмы и структуры данных. В этом году интенсивность таких занятий заметно увеличилась, проводятся специальные тренировки для первокурсников, которые организуют члены топ команды ИГУ Андрей Чумаченко и Кирилл Антонов. По правилам чемпионата мира, нынешние команды ИГУ смогут участвовать в соревнованиях еще два сезона, поэтому, можно надеяться, что это не последний успех студентов ИМЭИ ИГУ на этих престижных соревнованиях.
К. Д. Кириченко,
доцент кафедры алгебраических
и информационных систем ИМЭИ
