Студенты ФКН заняли восемь мест в топ-12 на соревновании Moscow Regional Contest

ICPC Moscow Regional Contest

7 и 8 ноября прошел Moscow Regional Contest — четвертьфинал Международной студенческой олимпиады по программированию ICPC. 119 команд из 24 вузов встретились на площадке в комплексе «Измайлово», чтобы определить, кто будет представлять московский регион в полуфинале.

Как отметили члены жюри, в этом году в контесте не было «нерешаемых» задач. Тем не менее уровень сложности остался высоким, и ни одна команда не смогла справиться со всеми 13. Среди тем встретились бинарный поиск, сравнение чисел, не попадающих в стандартные числовые типы языков программирования, свертка многочленов с помощью быстрого преобразования Фурье, динамическое программирование на деревьях с использованием техники slope trick, строковые алгоритмы и задача с двойным запуском.

Вышка повторила прошлогодний рекорд — от университета участвовала 31 команда. 13 из них получили дипломы Moscow Regional Contest: решившие семь задач — третьей степени, восемь или девять — второй, десять и более — первой.

Чемпионом соревнования стала команда BasketBobr студентов бакалавриата «Прикладная математика и информатика» ФКН Антона Степанова (четвертый курс) и Алексея Васильева (третий курс) и студента второго курса магистратуры «Современные компьютерные науки» Алексея Михненко.

Топ-12 команд Moscow Regional Contest

1. BasketBobr (НИУ ВШЭ: Антон Степанов, Алексей Михненко, Алексей Васильев);
2. Colasaurus (МФТИ);
3. labubu with matcha (НИУ ВШЭ: Прохор Ларичев, Глеб Устименко, Артём Агафонов);
4. Sussy Muffin (Университет «Синергия»);
5. value discuss (НИУ ВШЭ: Иван Алексеев, Владимир Звездин, Александр Скворцов);
6. Og kustiki absolute prime (НИУ ВШЭ: Сергей Дьяконов, Вадим Кустов, Матвей Макаров);
7. Ctrl+XD (МФТИ);
8. Philosophical life (НИУ ВШЭ: Валерий Родионов, Григорий Евгеньев, Ренат Каримов);
9. On pashet, ya krasivaya (МФТИ);
10. idk (НИУ ВШЭ: Александр Макнил, Антон Мартынов, Иван Пискарев);
11. K U P I T b: TUBE&TURJ ARBOZ (НИУ ВШЭ: Максим Матюпатенко, Михаил Любин, Георгий Возмилов);
12. DDOS PIZZA (НИУ ВШЭ: Рамир Зиганшин, Андрей Кандрашкин, Карим Сулейманов).

Полная таблица результатов доступна здесь.

Чтобы попасть в четвертьфинал, команды должны были пройти отборочный этап московского региона, который состоялся 11 октября. Здесь организаторы также подготовили 13 задач по таким темам, как теория чисел, комбинаторика, структуры данных на деревьях, геометрия, динамическое программирование, производящие функции, а также интерактивные задачи и задачи с двойным запуском.

Вышку на отборе представляли 149 команд, победителем стала все та же BasketBobr — только команда ФКН смогла решить все 13 задач. Другие команды студентов НИУ ВШЭ также заняли места на вершине рейтинга: value discuss — третье место, Philosophical life — шестое, mog department (Ян Дрожецкий, Дмитрий Трусов, Данг Зунг Хо) — десятое, labubu with matcha — 11-е и kuda my lezem (Артем Степанов, Максим Бессолицын, Михаил Бугрышев) — 12-е.

Антон Степанов
Студент четвертого курса бакалавриата «Прикладная математика и информатика», член команды BasketBobr

Четвертьфинал в московском регионе всегда собирает множество сильных команд, поэтому контест имеет соответствующую сложность. Его достаточно трудно «закрыть» за отведенные пять часов. После неудачной попытки сдать задачу К мы сосредоточились на оставшейся части контеста, чтобы минимизировать штрафное время. В итоге грамотный тайм-менеджмент и удачное распределение задач внутри команды помогли удержать лидерство. Мы улучшили прошлогодний результат, сохранив отрыв от второго места в одно верное решение.

Артём Шулятьев
Эксперт Центра студенческих олимпиад ФКН

Контест четвертьфинала этого года вышел очень сбалансированным. Каждую задачу решила хотя бы одна команда, но при этом никто не справился со всеми 13. Организаторам удалось добиться плавного роста сложности — все лидеры сдали разное количество задач.

Самыми сложными оказались G и K. Первая была посвящена теории игр на графах, которая сводилась к не самой известной формуле Татта — Бержа и алгоритму поиска максимального паросочетания в произвольном графе. Во второй участники должны были перевести стереометрическую структуру из условия в иной формат и только после этого приступить к решению. Многие сильные команды справились с первой частью, но проверку системы прошел лишь один ответ. За первые четыре часа контеста никто даже не попытался сдать задачу K, поэтому тратить на нее много времени было рискованной затеей, и команды предпочитали сосредоточиться на других задачах.

Густокашин Михаил Сергеевич
Директор Центра студенческих олимпиад

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

Результаты четвертьфинала в очередной раз показывают, что НИУ ВШЭ готовит сильнейших программистов региона. Вышка побеждает в Moscow Regional Contest третий год подряд. Места в топ-3 заняли опытные участники соревнований, для которых прошедший четвертьфинал был хорошей тренировкой перед Чемпионатом Северной Евразии. Результаты же команд первокурсников позволяют предположить, что Вышка продолжит победную серию и в следующем году.

На полуфинале Международной студенческой олимпиады по программированию ICPC, который пройдет в декабре в Санкт-Петербурге, Вышку будут представлять пять команд, показавших наилучшие результаты на Moscow Regional Contest.