Вчера я вернулся в Вологду с очередного чемпионата ИГЭУ. С 16 по 18 мая в Ивановском Государственном Энергетическом Университете проходил VIII открытый (участвовать могли не только студенты данного университета и даже школьники) чемпионат по программированию. Небольшой отчёт о поездке под катом.

Как только мне переслали официальное приглашение, я поинтересовался – можно ли на соревнование захватить свою клавиатуру (уж больно я к ней привык). На наш запрос организаторы ответили, что «нет, все участники должны работать на однотипных устройствах» 😮 Хорошое начало, однако. Затевать беседу об однотипности я не стал…

Отбор на чемпионат проходил в университете через выполнение норматива по решению задач. В итоге, на олимпиаду поехал я и Егор Стрешнев.

Как всегда насущным вопросом было – где мы будем жить в Иваново. В этом году мы решили изменить стандартному выбору (гостиница «Иваново») на гостиницу «Турист». Мы посчитали, что можем себе позволить взять 3 отдельных номера + завтрак в гостинице + халявный интернет. Гостиница располагается в центре города, недалеко от весьма крупного ТРЦ «Серебряный город», где мы каждый год появляемся. Вышло примерно по 5000 с человека за 3 ночи.

По пути в Иваново

Поездка началась с автобуса «Вологда-Иваново». До Данилова мы добрались обсуждая записи презентаций сообщества «JUGRu» и конференции JPoint 2013. Performance-инженеры из Оracle в очень живой форме рассказали о том как надо и как не надо делать микробенчмарки Java-кода, какие интересные баги они вылавливали в многопоточке Java, как надо решать проблемы производительности приложений на Java и как, зная принципы работы JVM на конкретных архитектурах процессоров, выжимать максимум производительности. Все данные доклады я крайне рекомендую увидеть тем, кто серьёзно интересуется вопросами производительности Java. Фёдор Меньшиков поделился своим первым опытом программирования под Android. В конце разговор скатился в область грамотного написания многопоточных программ, книжку по которому я сейчас читаю («Java сoncurrency in practice»).

Когда все насущные вопросы мы обсудили каждый решил уединиться. Кто-то пытался спать, кто-то смотреть фильм, кто-то слушал музыку. Но в районе Данилова нашему расслабону пришёл конец – у автобуса была обнаружена неполадка. Водитель начал очень часто останавливаться и бегать вокруг автобуса. После часа такого экшена вроде было даже озвучено, что за нами уже выслали новый автобус и его придётся ждать пару часов. Но чудеса случаются: автобус всё-таки смог дотянуть до Ярославля, где нас уже ждали для экстренной пересадки на другой автобус. Погода в среду стояла жаркая, кондиционер в новом автобусе, несмотря на повышенную шумность, весьма слабовато охлаждал автобус. Когда мы подъезжали к Иваново вдруг началась серия дождей и уже было не понятно что хуже: изнывать от жары или промокнуть под дождём. Общим голосованием было решено добираться в гостиницу на такси.

В Иваново

Местные бомбилы неслабо заламывают цену, так что лучше вызвать такси, обойдётся на 100-200р дешевле. Пока ехали в такси, я решил проверить работоспособность GPS и «Яндекс.Карты». В целом, они отработали нормально и это дало уверенность, что мы не потеряемся в городе 😄

Номера в гостинице совпали с ожиданиями и фото на сайте, но отсутствие кондиционера и неполадки в смесителях немного подпортили проживание. Видимо, пора уже завязывать переставать верить в то, что заявленный WiFi в гостиницах способен нормально работать. У меня получилось к нему подключиться только на 2-ой день и то пришлось выходить в коридор. Когда уже администраторы гостиниц поймут, что нельзя просто поставить один роутер на этаж и надеяться, что этого будет достаточно?

После размещения (а это было около 20.00 вечера) в гостинице мы отправились ужинать в ТРЦ. За год там особо ничего не поменялось, как всегда каждый мог найти себе еду по вкусу. Чуть позже в нём мы нашли и магазинчик Baskin-Robbins, где можно было отведать известный бренд. На 1ом этаже ТРЦ располагается гипермаркет, который поражал не только своей площадью, но и очередями у касс. Каждый день мы в нём закупались и каждый день стояли в очереди по 10-15 минут :-( По приходу в гостиницу я предложил распланировать следующий день. Открытие чемпионата было в 14 часов и хотелось бы чем-то заполнить кучу времени до него. Выбор пал на поход в тот же ТРЦ в кинотеатр на «Стартрек: Возмездние». Идти мы собирались в 11 часов и ожидалось, что хоть и день премьеры, но в это время народу будет не много. После этого мы разбрелись по своим комнатам. Интернета у меня не было и я решил в кои то веки посмотреть телевизор. Нашёл известный канал Наука 2.0 и смотрел его пока не начал засыпать.

Первый день олимпиады

На следующий день позавтракав, мы отправились в кинотеатр. Не знаю каким образом, но нам за 120р дали билеты на сеанс с 3D. Дежурная бабушка на входе в зал прифигела от такого расклада и не хотела нас пускать. Видимо, не мы одни купили такие «весёлые билеты» (оказалось, что кассир была «новенькая») и в итоге нам всё-таки организовали сеанс 3D за такую смешную сумму да ещё и в день премьеры. В рекламе до фильма были эпичные трейлеры фильмов «RED 2», «Война миров Z», «Иллюзия обмана». На каждый из них мне непременно захотелось сходить. Спойлерить по поводу самого «Стартрек»-а не буду, но скажу, что фильм вполне в духе первой части и его было весьма интересно смотреть.

После сеанса мы пошли на открытие чемпионата. Ничего особо интересного. После этого был пробный тур, на котором Егор занял 1-ое место, а я – последнее 😄 В самом чемпионате было заявлено около 36 участников, среди которых были студенты 4-ёх университетов, одна академия и много школьников. По моим подсчётам на контесте было 4 моих реальных соперника. Но план-минимум состоял в том, чтобы войти в Top 3.

После пробного тура мы отправились в пиццерию, где пообедали всем что смогли съесть. Ну и какая поездка в Иваново без традиционной пешей экскурсии по городу. После плотного обеда да и в жаркую погоду я всячески пытался отговорить от данной затеи, но мы всё-равно отправились в прогулку по улицам города, параллельно слушая рассказы об истории некоторых зданий, улиц и памятников. В гостиницу я пришёл еле живой. И это за день до основного тура! Хорошо, что запасы питьевой воды и вечерняя прохлада смогли привести меня в чувство.

Основной тур

В день основного тура мы спокойно добрались на троллейбусе до здания университета, встретили участников из Рыбинска и Коврова. Начался тур. И вот тут начались «сюрпризы». Вчера организаторы нас уверяли, что контест будет простой, т.к. падает средний уровень участников и много школьников. Но первая же халявная задача С на поиск количества компонент связаности в графе дала всем лидерам по нескольким «брёвнам». Причина была в том, что размер графа был порядка 10^6 и стандартный поиск в глубину не втискивался в ограничение 64 мбайт. На Java стандартный размер стека около 1 мбайта и очень глубокая рекурсия вылетает с ошибкой Stack Overflow. Для обхода этой неприятности я добавил создание потока на почти 64 мбайта и проверил, что в худшем случае его вроде должно хватать. Я стал получать вердикт WA 29. Проведя серию опытов локально, я решил, что на самом деле потоку и 64 мбайт может не хватать и мой поток просто тихо дохнет с тем же исключением, но проверяющая система это исключение не регистрирует. В итоге, получив 3 «бревна» я решил переписать всё на поиск в ширину и оно успешно прошло все тесты. Отличное начало, ничего не сказать 😄

Дальше зашли ещё 2 халявки. После сдачи 3-ей задачи я даже оказался на первом месте. Но вскоре меня обогнал будущий победитель – он решил задачу на геометрию и тернарный поиск (E). Я сразу же переключил своё внимание на неё. Геометрии там оказалось совсем немного, а формулу для объёма конуса откуда-то вытащило подсознание 😄 В результате, на 4-ом часу соревнования я занял 2-ое место и началась финишная прямая. Я долго и упорно пытался написать «технический гроб» контеста – задачу в которой требовалось реализовать проверку на совпадения регулярного выражения из букв и символов * со строкой. Я думал, что это было мне вполне по силам: решение постепенно совершенствовалось, я накопил около 10 тестов для проверки, но довести до конца его так и не успел. Также я понял, что в задаче A надо найти гамильтонов цикл но был без понятия как это сделать. У задачи B было красивое техническое решение, но до него можно было дойти, если долго и упорно рисовать решения задачи для разных размерностей.

В конце контеста я оценил возможные сценарии во время заморозки и стало понятно, что выпихнуть меня со 2-ого места можно только если кто-то сдал 5 задач. Но таковых не оказалось.

Итоги

На закрытии был проведён разбор задач. Разморозки результатов не было – просто начали с первого места выдавать дипломы и подарки. В этом году фонд соревнования видимо подрос – была и компьютерная переферия и книжки. Также были спонсоры, которые для Top 3 организовали дополнительные подарки. Мне от них досталась эргономичная клава «Natural Ergonomic 4000», а от организаторов я выбрал себе беспроводную компактную управляемую аудио-систему.

От 1-ого места я отстал на 10 штрафных минут. Не сделай я столько глупых попыток по первой задаче и всё было-бы совсем иначе, но и этот результат меня вполне устроил. После закрытия мы отправились в McDonald’s, где поужинали и закупились в обратную дорогу.

Вот таким мне запомнился мой последний чемпионат ИГЭУ. Результат вполне достойный для «старичка». Олимпиадный год на этом закончился. Прошёл он на редкость успешно, что хоть как-то успокоило моё «олимпиадное эго», истерзанное за эти 5 лет. Что дальше делать с олимпиадами пока не знаю. Сейчас планирую доразобраться в многопоточке Java.