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

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

За несколько дней до олимпиады

Сделав выводы о результатах проведения предыдущей межвузовской олимпиады, было решено продолжить использовать мою разработку (S4RiS StanD) для проведения процедуры разморозки контеста. Ещё было желание добавить в процедуру разморозки немного подходящего музыкального фона, как это делается на полуфиналах в Питере. Так как специально обученного дабстеппера или битбоксера у нас не нашлось – решили подобрать что-то более простое. Выбор пал на трек с официального демо-видео S4RiS StanD.

Последние дни перед соревнованием я пытался уговорить Фёдора Меньшикова добавить в его систему более информативное отображение хода соревнования во время «заморозки» с использованием всем известных знаков ?X, что сигнализирует, что «в заморозку» были отправки решений по задаче участниками. В результате, мне было предложено реализовать это самому, с чем я вроде-как справился буквально за день до пробного тура, впервые не только изменяя эту систему, но и вообще разбираясь в программе на Perl 😄

Зачем всё это? Просто, мне не безразлично то, как проводятся контесты, к которым я имею отношение, я ценю старания организаторов контестов, в которых я принимаю участие, и стараюсь «прокачивать» и то, в чём выступаю сам как часть организационного или технического комитета олимпиады. Пора уже всем организаторам уделять внимание не только качественному проблемсету, но и относиться к олимпиадам как к званным ужинам, где хозяева пытаются угодить гостям буквально во всём. Это не дорогое удовольствие, просто надо немного больше «побегать». Самим же потом будет приятно обо всём этом вспоминать, как о подвиге, а не как «слава богу провели». Вообще, дух челленжа на олимпиадах должен быть не только в участниках, но и организаторах. Именно тогда рождается что-то реально крутое.

Пробный тур

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

После того как я пересел на «механику» дома, я начал испытывать очень сильный butthurt, когда приходится сидеть за мембранными клавами. Такое ощущение, что вдавливаешь камни в песок. Руки устают очень быстро.

На пробном туре в этом году были даны 2 задачи. «Халявка» и «Судоку». В итоге, первую задачу все сдали минут за 10, а самые отчаянные стали писать судоку. Я, честно говоря, никогда «Судоку» сам полностью не решал и пытался подойти к решению эмулируя то, что стал бы делать человек при решении. Я попытался выбрать эвристики, которые бы сокращали перебор, но час кодинга и почти 300 строк так и не превратились в AC. На разборе были предложены другие эвристики, которые были более затратные по памяти, чем моё решение (которое прошло 35 тестов из 60), но никаких доказательств, того, что именно эти эвристики нужно было использовать, приведено не было. Для меня эта задача сразу же скатилась до уровня «придумай хорошую эвристику и, если повезёт, то её сдашь». Да уж, хорошо, что эта задача не попалась на основном туре…

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

Основной тур

На основном туре было предложено 11 задач. Все начали искать задачи для себя. В который раз меня уже не подводит тактика – быстро посмотреть все задачи и определиться с тем, чем стоит заняться прямо сейчас. В результате, я начал решение с задачи «Круги». Сама по себе задача – практически клон задачи с одного из раундов Codeforces, только тут надо было ещё посортировать (и авторы не упустили возможность добавить AntiQuickSort-тест), внимательно прочитать условие и не хранить целые числа в даблах. Вообще стоит отметить, что в нескольких задачах авторы пытались валить QuickSort Паскаля и Явы, вроде как были даже AntiHash-тесты. Хорошо ли это – вопрос спорный. Лично мне кажется это весьма не спортивным так жёстко хакать решения новичков, когда все опытные участники про это в уже в курсе.

Потом прошла задача «Барабан», которую я решил не красивым способом через GCD, а какими-то своими левыми соображениями.

Задача «Кондукторы» казалась весьма безобидной. Читая её по-диагонали вполне понимаешь, что от тебя требуют, но когда твоё решение не проходят тесты из условия… Зачем-то авторам захотелось изменить классическое условие «счастливого билета» на «счастливый по-питерски» (сумма на нечётных позициях равна сумме на четных). Вторым гвоздем стало то, что не совсем понимаешь зачем тебе дают информацию по всем кондукторам, когда нужно найти ответ только для первого. Оказалось, что мало найти ответ для первого. Надо чтобы ещё вся информация по остальным кондукторам тоже сошлась в выбранном диапазоне билетов. Капец, ладно. Сдал и забыл.

Потом на выбор было либо возвращаться к задаче A («Факториал») или H («Игра»). В обоих задачах казалось, что есть какая-то красивая идея, которая их позволяет решить. Так нет: в первой надо было тупо написать «длинку», ибо бигинты получали TL, а в «Игре» надо было просто построить стандартный ациклический граф игры и всё в нём посчитать. Как скучно. Где же оригинальные идеи, которые так часто встречались в задачах межвузов ранее?

Не добившись успехов в этих двух задачах, я решил посмотреть другие. Внезапно я нашёл две задачи на графы. В задаче «Путь» использовалась баянная идея двоичного поиска по ответу с поиском в ширину, в задаче «Синонимы» всё было ещё проще – по словам строим компоненты связности, для каждой компоненты в TreeSet храним все слова, которые в неё входят (это делается прямо во время DFS). После чего выводим ответы на запросы. Решение хоть и немаленькое и пестрит объектами и структурами данных, но пишется только влёт. Решая именно эти 2 задачи в конце соревнования я поймал себя на мысли, что вот наконец-то опыт решения задач дал шанс написать такие задачи с такой скоростью, с которой можешь набирать текст 😄

Контест подходил к концу, мой сокомандник (Иван Суворов) всё-таки расквитался с 5ой задачей до «заморозки», но с очень большим штрафом, что позволило мне его обойти в заморозке. 6-ую задачу никто из нас не решил.

Перед уходом с контеста я сделал 3 левых сабмита по 3-ём задачам, которые вообще не решал. Чисто, чтобы создать интригу. Прикольно, что я знаю, как будет происходить разморозка и зрителям, наверно, было бы эпично видеть, как после 3-ёх «брёвен» я получу AC 😄

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

Для всех желающих так-же был проведён разбор задач.

Процедура разморозки прошла весьма успешно, участники получили подарки от «Playrix», «Тензор», «R-Style», «Трилан».Спасибо им за поддержку студенческого олимпиадного движения. В конце было сделано групповое фото участников. Надеюсь, что фотоархив будет доступен для скачивания.

PS

Так получилось, что несмотря на проверку моей программы для «разморозки» я не видел финальных результатов и интрига для меня сохранялась. Я приятно удивился своему результату. 8-ое место на соревновании, 1-ое место среди студентов Вологды. Я получил долгожданную грамоту об успешном участии и наушники от «Playrix», в которых сейчас сижу и пишу этот отчет. Программу-минимум по соревнованию я выполнил, можно строить дальнейшие планы.