31 марта 2013

XVI Межвузовская олимпиада, Вологда, 2013

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


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

Делая выводы по результатам проведения предыдущей олимпиады было решено продолжить использовать мою разработку - S4RiS StanD для проведения процедуры разморозки контеста.

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

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

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

Пробный тур

Как всегда, всех желающих ждал пробный тур. После небольших проблем с клавиатурами в прошлом году, в этом году было предложено всем принести свои. Я не мог от этого отказаться и принёс свою домашную 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 :-)

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

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

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

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


4 комментария:

  1. В судоку на самом деле на олимпиаде надо понимать, что из-за ограничений на существование и единственность решения придется достаточно жестко ограничивать неправильные решения, а из-за довольно скудного количества методов ограничения (20-25 подсказок) придется резать сразу очень большие ветки перебора. Поэтому какие-то очень простые эвристики должны проходить. Дальше можно либо придумать что-то простое и, если не пройдет, оптимизировать дальше (как я действовал), либо построить несколько реальных примеров (взять заполненное судоку и выкидывать из него числа, до тех пор, пока не теряется однозначность) и посмотреть, сколько неверных веток посещает наш алгоритм. Первая эвристика посещает ~1000 неверных веток, поэтому она будет работать очень быстро.

    ОтветитьУдалить
    Ответы
    1. Для меня это было первым опытом решения данной задачи, никаких общеизвестных приёмов я не знал, действовал по-интуиции :-)

      Удалить
    2. Там не надо было использовать приемы конкретно судоку. Там использовалась стандартная идея о том, что надо для каждой позиции перебора посчитать количество подходящих для нее значений и перебирать сначала те позиции, где подходящих значений мало. Это стандартная практика всех переборных задач, где позиции могут сильно различаться по количеству вариантов, это всегда хорошо работает.

      Удалить
    3. Ты не поверишь, но идеологически моё решение основывалось на этой же идее :-)
      Просто оказалось, что не все эвристики одинаково полезны.

      Удалить