Всем привет!

Вчера прошел Московский четвертьфинал ACM. На нем было много необычного, например, два ВУЗа-организатора и интерактивная задача как на полуфинале. Сейчас я расскажу, как это было =)

Во-первых, я хочу сказать спасибо организаторам и членам жюри за отличную организацию контеста в целом, адекватные задачи с понятными условиями и красивыми решениями. Очень приятно, что кроме фразы "все было как надо" мне нечего сказать про техническую составляющую и можно остановиться только на спортивной.

Во-вторых, поздравить парней из МГУ, захвативших весь пьедестал почета, с абсолютной победой. И персонально Илью Корнакова, который с разными командами выигрывает четвертьфинал третий раз подряд! Причем каждый раз с отрывом не менее одной задачи и два раза полностью закрыв контест. Awesome achievement!

В-третьих, пора представиться. В этом году мы впервые выступаем в качестве команды МФТИ. Хотя это наш четвертый сезон. Почему так получилось?) Потому что до этого года мы учились в МГТУ им. Баумана, и ребята, с которыми два года ездили в Саратов на летние сборы, скорее всего помнят нас именно как "команду Бауманки". Раньше мы назывались "BMSTU nuBO" (ACM/Opencup) или "Жыгуль и Сэмки" (Новосибирск); теперь, соответственно, "MIPT Guinness" и "Гиннесс и Фисташки". Прогрессируем =)

Вообще, специфика московских четвертьфиналов прошлых лет такова, что выступает очень много команд МГУ, которые обычно борются за весь топ и все, что около него, и еще выстреливает команда от какого-нибудь другого ВУЗа (Физтех, ГУ-ВШЭ). Остальные сражаются за оставшиеся путевки, при этом высоко не поднимаясь, так что иногда выходят команды аж из третьего десятка. В этом году контест обещал быть более жарким, так как очень много хороших команд появилось на Физтехе. Так много, что МФТИ тоже стал ВУЗом-организатором наряду с МГУ. Оптимизма это, мягко говоря, не прибавляло, так как из Бауманки можно было спокойно выходить в полуфинал из второго десятка, здесь же это было исключено полностью.

Итак, контест начался. Почти сразу стало понятно, что контест обещает быть очень жестким, в том плане, что было много несложных задач. Одна ошибка или жесткий затуп - и все, бай-бай. То есть чтобы не отставать, надо все 5 часов решать быстро и четко. Поначалу нам это не очень удавалось. Не то, что бы мы где-то явно лажали, нет, задачи потихоньку решались и тем не менее, от первой десятки мы были далеко. Кроме того, нас обгоняло много команд нашего ВУЗа, что было совсем плохо. Где-то после двух часов контеста нас постиг fail - интерактивная задача никак не хотела заходить. Сначала нашли баги, потом выяснилось, что надо писать другой алгоритм. Новый алгоритм был правильный, но ловил TL. Еще между всеми этими проблемами случился WA #1 - при таком штрафе мелочь, но настроение вконец испортило. К тому моменту, как мы ее запихали, прошло больше половины контеста и мы безнадежно отставали от нескольких наших команд. До фриза мы чисто сдали еще одну задачу. Фриз наши команды встретили с одинаковым числом задач, но разница по штрафному времени была существенная и отнюдь не в нашу пользу. Через 10 минут мы сдали еще одну задачу. Дальше был трудный выбор - писать техническую задачу на геометрию или подумать над динамкой. На наш выбор повлияло два фактора: динамку можно было придумать, а можно было и не придумать, в то время как решение другой задачи было очевидно, но непросто, и число решивших задачи было явно не в пользу динамики. Поэтому было решено пойти ва-банк и бросить все силы на геометрию. В итоге написать ее мы так и не успели, а после контеста выяснилось, что динамка оказалась просто элементарной. Epicfail. Две наши команды решили по 9 задач (у нас было 8) и мы уже собирались домой. EPICFAIL.
Но тут буквально произошло чудо: выяснилось, что нам сказочно повезло - совпали сразу 3 фактора:
1) квоту нам увеличили до 3 команд (за проведение)
2) команда, которая тоже решила 8 задач, умудрилась проиграть нам по времени
3) и самое неверотяное - ни одна из двух команд, которые нас обыгрывали по времени, не смоли сдать ни одной задачи после фриза. Для одной из них стала роковой все та же геометрия.

В итоге мы прошли с десятого места, выпив тонну валидола. Представляю, каково командам МГУ, у которых и топовые команды сильнее наших и при этом каждый год такая жесть. Любопытно, что последняя из прошедших команд заняла 37 место. Еще любопытно, что среди первых 23 команд 20 - из МГУ и МФТИ. При том, что еще две команды школьников СУНЦ МГУ участвовали вне конкурса. Из других ACM-команд в первые 23 попала только команда МИФИ, причем вошли в десятку и обогнали нас, молодцы парни! Не могу не сказать, что следом за этой группой идет команда ребят, с которыми мы учились на одной кафедре в МГТУ и с двумя из них мы в разное время тренировались. Еще чуть ниже - наши одногруппники, с которыми мы вместе перешли из МГТУ. Понятно, что на полуфинал они не едут, хотя обогнали многих из тех, кто едет. И еще одна команда из тех, кто прошел, команда ГУ-ВШЭ (AMI 01), как вы уже догадались, тоже учились с нами на ИУ9. Вот так нас много =)

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

Финальные результаты
Задачи
Upd: Разбор задач