Рыбинск'12 или последний шанс для Vologda SPU 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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