Вчера закончилось важнейшее мероприятие в жизни любого ACM-щика из России и стран бывшего СССР, кроме Украины и Молдавии. Сегодня я сижу в торговом центре "Невский" около Московского вокзала и пишу этот пост.

Часть 1: регистрация

30 ноября мы приехали в Санкт-Петербург. Отсидевшись несколько часов на вокзале, попутно иногда согреваясь в кафешках типа "Теремок" (надо сказать, погода была мерзкая, и теплая куртка не особо помогала), мы заселились в хостел (который находился прямо около вокзала), немного отдохнули и поехали в университет.

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

В комнатке для регистрации нас ждали огранизаторы полуфинала, которые отметили, что мы все-таки приехали, сотрудницы Яндекса, которые попросили заполнить их анкетки, сотрудницы Mail.ru, которые дали нам небольшое задание — его надо было отправить по интернету в специальную форму и получить возможность выиграть небольшой приз, и сотрудницы Jetbrains, которые предложили пройти несложный тест по языку Kotlin. Тест мы прошли сразу же. Без маленьких багов не обошлось, но тем не менее они решили дать нам приз. Можно было выбирать из футболки, чайника, кружки и лицензии на один из продуктов Jetbrains. Я подумал, что ворованную IDEA Ultimate IDEA Community Edition я могу и так поставить, поэтому выбрал футболку.

Дальше мы вернулись в гостиницу, решили задания от Mail.ru, немного считерив, воспользовавшись решалкой судоку, решалкой японских кроссвордов и распознавателем QR-кодов, отправили их и дальше весь вечер играли в разнообразные настольные и компьютерные игры.

Часть 2: пробный тур

Наступила зима, а это означало, что пришло 1 декабря и надо ехать на пробный тур. Открытие началось в 11 часов, но из-за неумолимого желания спать, а после пробуждения — еще и покушать, приехали мы примерно в 11-20. Впрочем, это никого не расстроило.

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

Дальше был пробный тур. В качестве пишущего пробный тур был выбран я: по статистике, когда его пишет Hohol, команда сливает контест, а когда я — наоборот. Задачи я решил сдавать в порядке X-Y-Z, т.к. для задачи X требовался стандартный ввод-вывод, а для остальных задач — файловый.

Привыкать к клавиатуре было некогда, поэтому я делал кучу опечаток, но потерял в сумме немного — секунд 30-40 и все-таки сумел получить суммарный штраф 6. К сожалению, с ИТМО-1 бесполезно конкурировать даже на пробном туре: нельзя просто так взять и выиграть пробный тур. Компьютер работал достаточно быстро, PCMS вроде бы тоже не тупил, так что единственное, чем мы остались недовольны — расположением компьютеров в зале. Например, я мог одним движением руки выключить компьютер Saratov SU 2 и Perm SU 1. Не думаю, что их обрадовала такая перспектива, хоть делать мы этого и не собирались.

На встречу с Яндексом и Mail.ru мы не пошли, предпочтя им очередные партии в сет, шахматы, го, покер, прохождение Hitman на максимальной сложности с максимальным рейтингом, прослушивание музыки и прочие бесполезные занятия.

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

Часть 3: контест

Осторожно: дальше присутствуют спойлеры по задачам!

Итак, наступило 2 декабря, следовательно, надо опять ехать в универ и играть контест. Ну что ж, нам не привыкать, поехали.

В универ приехали за 40 минут до начала. На контест запускали за 15 минут до начала — пришлось подождать в вестибюле. Жюри не гарантировало, что время на компьютерах будет правильное, поэтому я взял у I_love_natalia наручные часы, перевел их на 10.00 и остановил — включу вместе с началом контеста.

3, 2, 1, начали! Hohol берет первую половину комплекта и читает с начала, craus — вторую и читает с конца, я открываю Visual Studio, создаю проект, пишу шаблон. Примерно через 5-6 минут Hohol просится написать задачу A: говорит, изи, решу за 5 минут. Дописываю шаблон — там пара строчек оставалась и отдаю комп, сам читаю с B и дальше. 10:27 — Accepted. Открываем монитор, смотрим: сдают A и G. craus берет G, думает пару минут — идем писать ее.

А переполнения не будет? Что-то я очкую. Пошли на Java напишем. Открываю Eclipse, создаю проект, в это время craus выводит на бумажке формулы. Класс создан, перебиваем решение. Тесты проходит, с TL тоже нормально. Сабмит, WA на примерно 35 тесте. Ctrl+P, Enter, дебаг. Что за фигня? Все вроде работает. Давай посчитаем побольше коэффициентов. Какого черта ответы разные? Ничего не понимаю. Что еще решают? H решают. Hohol идет решать H. Эй, почему тут (k·k)²ⁱ? Надо или (k·k)ⁱ, или (k)²ⁱ! Исправляю, теперь все тесты проходит, даже злобные вроде "64 2". 46:09. Сабмит, Accepted.

Что по H? Ничего? Хреново. Я пошел над ней думать. Комп простаивает. Что еще решили? Во, E решили. craus читает E. Да там же просто жадность! Hohol садится писать. Я в это время придумываю что-то по H: давайте хранить для каждой буквы префиксные суммы по модулю 2, а потом слева направо пересчитывать. Нужно будет что-то вроде ксор-равно на отрезке и сумма на отрезке. craus — а давай в сете хранить все, что слева. В мапе? В мапе. Ммм, 52 * 300000 * логарифм мапы. Не зайдет же. Да ладно, сервак быстрый, если что, на хешмапу переделаем. Ну окей, готов писать.

Hohol дописал E. Сажусь тестить. Вроде все нормально. Сабмит — WA. Что за чушь? Эй, q_i тоже long long! Исправляем. 94:25. Сабмит, Accepted.

Сажусь писать H. Очень быстро дописываю, сабмит, TL. Что? Генерирую макстест, локально 1.8 секунд. Быстрый сервак, говорите? Сабмичу это на уже сданную задачу E — TL. Ну да, быстрый сервак, так мы вам и поверили. Исправляю map на hash_map. Локально 0.8 секунд. Сабмичу на E — Presentation Error. Ну ладно, вроде так успевает. Убираю генератор теста, сабмичу на H. Accepted. Время 118:05. Смотрим монитор. Наша вторая команда отстает от нас на 7 минут штрафа.

Что еще сдают? B сдают, C сдают. craus: мы тут вроде бы запруфили, что ответ равен , но это за квадрат, придумай, как побыстрее. Окей, придумываю. Значит, при фиксированном a_i у нас неравенство . Похоже на уравнение прямой. Давайте нарисуем в плюскости (i, b_i). Похоже, все точки должны лежать по одну сторону от какой-то прямой. Похоже на какую-то касательную к выпуклой оболочке этих точек. Отдаю craus: иди, придумай что-нибудь, вроде все правильно, остались детали.

В это время пишу проверку по задаче B: что, если собрать статистику, сколько какая вещь встречается? Давайте проэмулируем случай 9 и 10 одинаковых вещей, сильно ли они различимы. Хм, совсем не различимы, нельзя так решать. craus: я все вывел, пойдем писать. Ну пойдем. Пишем, тесты проходит. Тестируем, правильно ли написали выпуклую оболочку — все нормально. 179:05. Сабмит — Accepted.

Hohol придумывает решение задачи B: давайте вначале уберем все предметы из рюкзака, а потом положим туда все предметы, не убирая в процессе. Так мы узнаем все веса. Решаем рюкзак, дальше убираем те вещи, которые не нужны в оптимальном ответе. Немного думаю над J, ничего не получается. Начинаю тестить B. Выявляем штук 5 багов. Исправляем, сабмитим. Время 215:38. Accepted.

Что решать: J? Смотрите, еще F сдают. О, да она наверное проще, давайте ее решать, две все равно не успеем. Следующие 20 минут пишем решение, считающее, что поворачивающиеся и неповорачивающиеся элементы змейки чередуются. Блин, да оно семпл не проходит! Нахрена мы это все писали? В семпле они не чередуются! Ладно, тогда вместо динамики пишем просто перебор, наверняка зайдет. Пишем, до конца контеста 10 минут. Семпл прошел. Сабмитим, PE 5. Что, ответ не выводим? Пофиг на штраф, если что, поменяем время на задачу. Ставим assert на то, что не нашли ответ. RE 5. Все-таки не находим. Почему? Непонятно. Contest is over.

Смотрим на замороженный монитор: мы на 9 месте, если убрать лишние команды. Выходим в вестибюль. Говорят, Саратов чуть ли не не проходит. Спрашиваю у Fefer_Ivan: Saratov SU 1, 2, 3 по 5 задач. Ололо, близится сенсация. А, Saratov SU 2 все-таки обогнали JKeeJ1e30? Ну ладно, ололо становится поменьше. Ребята уходят кушать в Subway, я иду в столовку, встречаю там Izhevsk STU. Сколько кто сдал? Ижевск — 7 задач, СПбАУ — 7 задач. Окей, мы теперь 11-ые. Уфа — 6, по штрафу мы лучше. Кто там еще нас может обогнать? University of Latvia — встречаю их в актовом зале, говорят, у них 5. Petrozavodsk SU с 4 задачами сделали три сабмита — спрашиваю Дениса Власова, говорят, ничего не сдали. Странно, Петрозаводск вроде неплохая команда. Подходит yarrr, ему страшно, он не сдал шестую задачу. Смотрим вместе с ним монитор — а ведь их команду мало кто обгоняет. Кто там еще? Altai STU, Moscow SU of Steel and Alloys имеют 5 задач и два вопросика. Ну ладно, мы в худшем случае 13-ые, вроде проход, в том году было 16 команд, а ведь еще и финал в Петербурге.

Разбор задач. Говорим наше решение задачи C, зал дружно смеется. Ну и пихайте дальше ваш бинпоиск с даблами :D Наше решение на самом деле очень небольшое и быстро пишется, сложность только в придумывании. Скоро награждение.

Монитор начинает размораживаться снизу вверх. Наша вторая команда занимает 42 место и получает диплом третьей степени — к сожалению, задачу C они в заморозку не решили. Никогда еще вторая команда СГАУ не была так высоко. Сразу перед ними — две команды Belarusian SUIR, одна из которых — действующий бронзовый призер финала. Сенсации только начинаются.

Дальше команды с 5 задачами. Среди них Moscow IPT The Sun, как мне казалось, самая сильная команда МФТИ (простите, если кому-то казалось не так), команда Новосибирска, почти весь Саратов. Altai STU — оба вопросика превращаются в минусы, тоже 5 задач. Теперь мы точно 11-ые, если удалить лишние команды. Выходим на сцену, получаем благословление от руки Petr.

IITU сдали 8. Молодцы, хорошо сыграли, я рад за эту команду. А по рейтингу на Codeforces такого и не предположишь! SPbSU 4 таки сдают свои 4 задачи в заморозку. Belarusian SU сдают последнюю свою задачу на 299:36 и выходят на второе место! Moscow SU ST сдают последнюю задачу на 299:57 и выходят на второе место! ITMO 1 не сдает задачу K, the hardest problem ever given on NEERC. Контест удался.

Объявляют команды, прошедшие на финал. Мы 11-ые, Ufa SATU 12-ые. Так, команды с 5 задачами все-таки проходят. Алтай, Каунас, МАИ. 16 место достается Saratov SU 2 — предполагаемый гнев MikeMirzayanov должен несколько спасть. 17, 18! 18-ое, как позже выяснилось, предпоследнее место достается Perm SU, которые, по их словам, даже и не надеялись. Скоро становится доступна информация, что квота на самом деле 19, и последними на подножку уходящего финала запрыгнули Novosibirsk SU. Результаты доступны на сайте NEERC, а также у Снарка, где красным цветом выделены прошедшие команды.

Заключение

Мне очень понравился контест. Задачи классные, намного лучше, чем в 2010 и 2011 годах. Почти не требуется знаний каких-то жестких алгоритмов и структур данных, зато подумать надо, и много, этим славится NEERC, и мне кажется, что это хорошо. А решать меньше 7 для команд, которые ставят цель выйти на финал, на этом контесте, вроде бы, позор. Меньше 6 — совсем позор. Квота 12 команд, по мнению некоторых, была бы очень кстати. Но не мне это решать, меня и так все устраивает :)

ACM-карьера продляется до 3 июля. Увидимся на ACM ICPC World Finals 2013!