Команда ФКН приняла участие в финале ACM ICPC

С 20 по 25 мая, в Рапид-сити (Южная Дакота, США), состоялся финал международной олимпиады ACM ICPC. В этом году команда Random Shuffle в составе Никиты Зетилова, Андрея Кашина, Романа Александрова, заняв 26 место в полуфинале, отправилась в США на финал. К сожалению, в неполном составе.

Команда ФКН приняла участие в финале ACM ICPC

День первый. Прибытие.

Андрей летел из Лондона, Рома всё ещё ждал визу, которую так и не получит, поэтому добирались мы поодиночке. Первое, что бросается в глаза по прибытию — крохотный аэропорт для внутренних рейсов, Рапид-сити — город совсем небольшой. Второе — избыточное пространство в номере на двоих, в котором со мной должен был жить Роман. Рейсы были поздние, так что на регистрацию своевременно мы не успели и отложили на утро второго дня.

День второй. Начало финала.

Для участия в любых мероприятиях уже требовались бейджи финалистов, поэтому рано утром пришлось пройти все необходимые формальные процедуры. Дальше мы вне записи вписались на экскурсию в шахту Homestake — ранее самую большую золотую шахту в Америке, а ныне лабораторию по изучению нейтронов и тёмной материи SURF. Вниз нам спуститься, конечно же не дали, но прочли небольшую лекцию в центре для посетителей, а также дали возможность сфотографироваться на фоне карьера шахты. После этого мы поехали к главной достопримечательности в окрестностях Рапид-сити, да и во всём штате, к мемориалу на горе Рашмор, в которой высечены профили четырёх президентов США.


День третий. Ещё мероприятия.

Третий день прошёл под знаком различных мероприятий от IBM, от конференции с участием сотрудников компании в костюмах покемонов, до общения с Watson, суперкомпьютером IBM, который пытался по короткому диалогу определить психотип личности.

День четвёртый. Репетиция.

На четвёртый день нас ожидал… финал. Точнее, его репетиция, что-то вроде пробного тура. Но всё было ничуть не менее серьёзно: командные футболки и бейджи обязательны, ничего лишнего в холл, уставленный командными компьютерами, проносить не разрешалось, вот только задачи уже были знакомы опытным участникам. Довольно лениво мы протестировали работоспособность всего, что нам может понадобиться днём позже, так что задач мы решили, кажется, всего две.

День пятый. Тот самый день.

Кажется, это всё уже было, не далее как вчера. Вновь приходится сдавать личные вещи и переносить длительное ожидание в обеденном холле. Но на этот раз впереди пять часов реального соревнования. Проход сквозь коридор аплодирующих волонтёров и зрителей. Рукопожатие с Биллом Паучером, директором соревнований. Обязательно потрогать кубок, который уже совсем скоро достанется чемпионам, — на удачу.

Обратный отсчёт.


И, наконец, задачи, выбивающие все посторонние мысли из головы. Относительно быстро нахожу выглядящую лёгкой задачу. Успешные попытки по ней в таблице результатов подтверждают гипотезу, код пишется довольно быстро, буквально парочка тестов, сдаю на проверку… Первая сданная задача на финале! Совместно расправляемся с ещё двумя, пока рашаем Андрей предлагает идею по задаче A. Забегая вперёд, она окажется самой неоднозначной из решённых нами. Мысль проста, доказательство корректности мы выводим довольно быстро, но понимаем, что реализация отнимет немало времени (типичная задача на геометрию).

Тем временем Андрей придумывает и сам же решает задачу, четвёртую для нас — все сданы с первой попытки! Это обеспечивает нам неплохое штрафное время. Так как других идей, в которых мы уверены, пока нет, я сажусь реализовывать решение A. Андрей тем временем думает над другими задачами.

За пару часов до окончания контеста вроде бы всё готово, идёт посылка… Неправильный ответ! Понимаем, что в решении никак не избежать разбора частных случаев, про которые мы сразу не подумали. Около часа работы и несколько неудачных посылок наконец выливаются в код, в правильности которого мы уверены, и вот он, вердикт тестирующей системы «Accepted!».


Как выяснилось позднее, нескольким командам, которым эта задача в итоге не поддалась, она стоила медалей чемпионата мира. Мы же за оставшиеся 50 с небольшим минут попытались увеличить количество решённых нами задач до 6, но не преуспели. На церемонии награждения мы выясняем итоговое место нашей команды, 42 (два последних результата команд Вышки совпали, такое же место в 2015 году заняла команда из первокурсников ФКН), мы обходим многие команды с полным составом, а также оказываемся выше некоторых команд-лидеров по своим регионам.

Интрига с победителем держалась практически до последнего, но в итоге Санкт-Петербург продлил свою гегемонию благодаря команде ИТМО. Тем же вечером состоялось закрытие соревнований и поездка к Crazy Horce Memorial, где мы стали свидетелями лазерного шоу. Впереди было лишь возвращение домой, которое также таило в себе множество сюрпризов, но это уже немного другая история.