Доброго времени суток!

Несмотря на то, что с четвертьфинала центрального региона 2012 прошло уже прилично времени, воспоминания о нём всё ещё живы в памяти и я решил поделиться ими. Хотелось бы предупредить, что в посте присутствует много информации, которая не относится непосредственно к сабжу, но которую я посчитал важной для упоминания на случай, если кому-то пригодится подобный опыт подготовки к соревнованиям. Ну и немного лирики. Если вам это не интересно – смело пропускайте первые 2 заголовка.

За пару месяцев до соревнования

В 2012 году я закончил специалитет в ВГПУ и встал вопрос о дальнейших планах. Не так давно на факультете открылась магистратура и нас активно в неё зазывали. Всё бы ничего, но вкалывать по 10 часов 6 дней в неделю хватило уже на 5-ом курсе и продолжать это крайне не хотелось. В результате моё желание учиться в магистратуре было обосновано на 80% тем, что у меня оставался ещё один сезон участия в ACM ICPC. Да, этот призрачный шанс не давал мне покоя, несмотря на то, что сухой расчёт и статистика была не на моей стороне. Со своим предложением я обратился к своим сокомандникам, и они поддержали задумку подготовить последнее выступление команды.

Как только я был принят в магистратуру тут же начался этап подготовки команды. Несмотря на «рабочее лето» всех участников, мы всё-таки нашли силы собираться в выходные и решать задачи с Тренировок Codeforces. Но этого явно было мало для команды, в которой участники решают задачи только перед какими-то onsite-соревнованиями. Пришлось искать подход как выжать из команды максимум.

План подготовки

В результате, был проведён анализ предстоящего соревнования, выведены общие идеи, которые я оформлял по ходу подготовки в своём блоге. Если кратко, то я выделил сперва круг задач, которые предстоит решать на соревновании, определился с ролями в команде (кто какие задачи будет решать) и выработал план подготовки каждого участника.

Ивану Суворову было поручено дополнительно «в темпе вальса» научиться переводить Яву на C++ (на работе он собственно на нём и пишет): были выбраны задачи с Тимуса и сгруппированы по примерно 15-и темам в духе «использование мапа в C++», «форматированный ввод/вывод чисел». Зачем это? Просто в том году впервые на моей памяти сильно зерешал выбор правильного языка для решения задач и я не хотел, чтобы команда второй раз наступила на те же грабли.

Антону Серкову я старался обратно вернуть навыки программирования на Java (он на работе писал на Objective C) и отучить от привычки браться за задачи по его любимой теме (геометрия), которые зачастую бывают весьма трудоёмкими, особенно когда есть более простые задачи. На эти грабли команда также наступила на предыдущем соревновании.

Из особенностей команды можно было выделить то, что перечисленные участники обладают весьма хорошим навыком решения ad-hoc задач и способны закодить их, но знания «классики» им явно не хватало. Этим собственно занялся я сам.

В общем, летом команда более-менее активно готовилась к предстоящему соревнованию. Было понятно, что тупо решая задачи на соревновании нам ничего не светит и чёткой организации процесса решения задач стоит уделить чуть ли не большую часть моего внимания. В сентябре у ребят добавилась нагрузка в универе и было решено сбавить темп. В свободное время я старался довести свой проект – S4RiS StanD, до уровня, когда его можно будет кому-то предложить использовать. И, судя по всему, это получилось 😄

День первый. Приезд

Непосредственно поездка в Рыбинск прошла без особых изменений. Вузовский ПАЗик за 4 часа довёз нас до Рыбинска. Мы заселились в «Рыбинск» и пошли на традиционную прогулку по городу. В кой-то раз с погодой нам повезло и прогулка по обновлённой набережной оставила самые тёплые воспоминания.

Особенно нам запомнилось предложение нашего тренера покормить уточек и других пернатых в пруду около главного здания РГАТУ. «Хорошая идея» – подумали мы. «Сейчас я их всех накормлю» – наверно подумал тренер 😄 Каково же было наше удивление, когда Фёдор Владимирович вышел из магазина с 8-ью батонами хлеба 😆. Подойдя к пруду, мы начали весьма активно скармливать весь этот хлеб, следя за нешуточными баталиями местных птиц. Кажется, я ещё никогда не видел, чтобы утка с хлебом в клюве удирала по воде с такой скоростью.

Вернувшись на позитиве вечером в гостиницу мы случайно увидели людей, которые входили с улицы держа в руках продукцию всем известного Macdonald’s и в тот же вечер мы нашли его расположение (оказалось он открылся в этом году и совсем не далеко) и решили посетить для разнообразия это заведение.

День второй. Открытие и пробный тур

Открытие прошло в очередной раз в ОКЦ (Общественный культурный центр), на котором организаторы отметили большое количество (не менее половины) школьников и студентов, которые первый раз приехали на данное соревнование. В такие моменты ощущаешь себя реально постаревшим. Прямо бальзамом на душу стало заявление о том, что в этом году у жюри для всех задач есть решения на Java и что только одна задача будет использовать максимум половину от бедных 64 мб памяти.

Пробный тур прошёл как всегда не без проблем. Написав шаблоны решений для C++ и Java и сдав 2 задачи на 4ой минуте тура мы отправились ужинать в весьма достойную кафешку в супермаркете напротив гостиницы.

Это был, наверно, первый год, когда вечером перед соревнованием я успешно отгонял от себя мысли «ну надо что нить порешать/почитать». Мы решили, что если не пройдём в полуфинал (а шансов было мало с учётом появлений новых сильных команд у Ярославля и Рыбинска и «титанов» в лице Вятки, Иваново, Ярославля, Орла), то особо и не опечалимся. С этой мыслью и в гармонии с самим собой перед контестом мы отправились отдыхать.

День третий. Основной тур и закрытие

Подкрепившись опять в местном кафе мы отправились на основной тур. На моей памяти это было впервые, что в день тура не было дождя, что вселяло спокойствие и умиротворённость. В очередной раз мы не смогли пройти мимо уток 😄

Придя на место, порадовались, что наши настройки сред и заготовка остались нетронутыми. Контест как всегда начался весьма задорно, мы постоянно плавали в Top 10 и решили особо на это не обращать внимания.

Тактика, отработанная на тренировках, весьма не плохо нам помогла. Где-то в середине соревнования команда начала «буксовать». У соперников была сдана хитрая задача A, к которой нам долго не получилось подобрать хоть какого-то решения (в последствии решение-трэшак придумал Иван), я пытался вспомнить алгоритм конденсации графа к задаче про сеть (в который раз уже ощущаю, что мои теоретические знания слабо подкреплены практикой).

После того, как вторая команда Ярославля сдала задачу H, в которой изначально был намёк на дерево отрезков с извращениями (которое я писал раза 2-3), я решил более внимательно к ней присмотреться. В голову пришла идея, что дерево отрезков тут совсем не нужно. Достаточно двумерного массива префикс-сумм. Оценив, что памяти должно хватить, я быстро закодил решение и со словами «либо я прав и оно сейчас зайдёт, либо я хз что тут делать» я отправил решение и оно получило AC. На закрытии, когда были видны результаты сабмитов других команд по данной задаче я упорно не понимал, как её можно сдать с брёвнами. Может участники реально ломанулись писать это дерево отрезков с битсетами, либо попались на ловушку, в которую попала Vologda SPU 2 - как многим известно, скорость доступа к элементам массива в одной строке намного больше скорости доступа к элементам в одном столбце (из-за «прыжков», которые приходится делать для индексации). В результате, если вы делаете массив [10000][256], то проходы по количеству цветов делаются очень быстро и выполучаете AC, а если создадите массив [256][10000], то для прохода по одному цвету процессору придётся постоянно производить уже более сложные операции. Вот такая тонкая вещь, эти массивы

Последние 1.5 часа Антон провёл в активных попытках сдать задачу I, но, как оказалось, его идеи были далеки от верного решения. Мы же с Иваном пытались таки добить задачу про сеть. В середине 5ого часа я разрешил команде подкрепиться чаем с пирожками. Уже было понятно, что шансов что-то доделать маловато.

Ничего не сдав за последний час, я вышел из аудитории и отправился ко второй команде. У них тоже было глухо и мы с ними обсудили причину того, что их решение с массивом [256][10000] не прошло. По дороге встретил Максима Делюкина. По его выражению лица было понятно, что их команды закончили тоже не на подъёме. Выходя из здания мы пытались оценить свои шансы. В принципе, мы были уверены, что с таким хорошим штрафным временем шансы на Top 5 точно есть. В приподнятом настроении мы опять покормили уточек и отправились на закрытие.

Усевшись на первый ряд, мы начали ждать результатов. Я очень порадовался за школьников «Единства» и опечалился сливом «ВМЛ».

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

Подведение результатов получилось слегка сумбурным, жюри явно не поспевало за программой и вообще наглядности и интриги не хватало. Я поймал себя на мысли, что мой S4ris StanD в этом плане чуть более продуман.

Самый экшен начался, когда на экране стало видно команды с 6-ю задачами и «замороженными» попытками. Наша команда гордо находилась на первом месте и одного пинка ей бы хватило, чтобы от туда свалиться. Эти 5 минут, когда проходила разморозка 7-ых задач я запомню надолго. Ощущение, когда вместо зелёных вспышек видели только красные, передать сложно. Финалом эпика стала разморозка результатов команды-хозяина чемпионата. Передать эмоции, когда оказалось, что они так и не запинали 7-ую задачу, было сложно. Они выходили грустные, а мы уже во всю и весьма громко отмечали победу абсолютно не стесняясь на первом ряду 😄 Призы были весьма достойные (Galaxy Tab 2.0 c 3G и 7Гб памяти от JetBrains ). Ну и в конце было общее фото команд-участниц полуфинала.

Позже для особо любознательных был проведён разбор задач. Возвращались мы в гостиницу уже через супермаркет, где закупились тем, чем потом в номере отметили победу ещё раз 😄 На следующее утро нас уже ждал наш ПАЗик и дорога домой. Вот так эпично команда Vologda SPU 1 образца 2011-2012 г провела свой последний четвертьфинал.