Чемпионат Урала и поездка в Екатеринбург
Кто сможет прочесть данный отчет от начала до конца, тому я пожму руку при встрече
Вступление
Про чемпионат мы узнали, как и все, на сборах в Петрозаводске, и тут же про него забыли. Вспомнилось все только после анонса на codeforces, через некоторое время был написан отборочный тур. Задачки были не сложными, и мы, признаюсь, писали без особого энтузиазма – все равно поедут все, кто хотел. Но только потом мы узнали, что от вуза допускаются только две команды, и что третья команда была всего лишь на пару задач позади. Правда, удивил тот факт, что команд МГУ сначала было приглашено две, а потом – четыре.
Итак, первый этап был пройден, отборочный тур написан, билеты куплены (в последний момент). И вот, мы уже в Екатеринбурге. Город нас поразил. Это один из самых необычных городов, которые мы видели – широкие улицы, здания самой разнообразной архитектуры. Новостройки и ветхие старинные чередовались с необычайной частотой – доходило даже до того, что в абсолютно новом (с виду) доме можно было найти пару древних стен 50-летней давности.
Гостиница наша была расположена очень удачно – в двух минутах от Уральского университета (в нем проходили открытие и закрытие), правда до места проведения контеста приходилось добираться на трамвае. Кстати, о трамваях, которых было необычайно много – тысячи их! А вот цены в Екатеринбурге совсем не те, что мы ожидали – дешево можно было поесть только в столовой со 100-метровой очередью. Нормальная гостиница тоже стоит недешево, а бюджетные варианты располагались за городом (или «на окраине», как называли это некоторые команды), что доставляло участникам большое неудобство.
Вид из окна гостиницы
Набережная реки Исеть
Организация и пробный тур
Теперь, о самом соревновании. Оно действительно поразило оригинальностью. Первое, чем отличился чемпионат Урала – место проведения. Это был спортивный зал со столами, расставленными в три ряда. На каждом столе был ноутбук или моноблок с клавиатурой – мышки нужно было привозить с собой (о чем предупредили организаторы). Пока народ подтягивался, пробный тур из двух задач уже начался. Пока мы их писали, мы несколько раз прокляли ди-джея (да, там играла музыка) за русскую попсу 90-х, но такой музыкальный ряд был выбран неспроста. Как оказалось, те две задачи были только пробным «пробным туром», а основной был впереди.
Итак, все команды заняли свои позиции, тренеров пригласили на трибуны, и каждому раздали лист со списком 50-ти известных русских исполнителей 90-х. Киркоров, Руки вверх и Наташа Королева – список впечатлял. Участников ждал контест из 13 задач. Друг за другом ди-джей включал песни, и в этот же момент появлялась возможность сдать одну из задач. Решение должно было выводить одно число – номер исполнителя (из выданного списка), песня которого звучит в данный момент. Возможность делать посылки пропадала с окончанием трека. Еще одно интересное условие – решения можно было отсылать не чаще, чем раз в 10 секунд.
Вначале это казалось чем-то безумным. Потом мы начали придумывать различные тактики, например, мы слушали песню достаточно долго, чтобы точно распознать исполнителя и сдать задачу с первой попытки. Но мы не знали и половины исполнителей, поэтому первоначальный план провалился, и уже на третьей песне начали делать перебор по всем разумным вариантам – песня «Бедная овечка» нас подвела. Оказалось, что даже если начать перебирать варианты с первых секунд можно не угадать исполнителя – команда MSU ST поставила рекорд скорости – они успели отослать 27 вариантов (притом, что половина отсекалась, потому что исполнитель – мужчина), но так и не отгадали верный! Лидеры соревнования – команды МГУ – стабильно шли на последних местах, а Unpredictable вообще не пришла. Но были и те, кто отгадывал все песни с первой попытки (у лидера всего лишь три неудачных посылки).
Можно сказать, что пробный тур определенно удался – он повеселил участников, а организаторы смогли проверить тестирующую систему в действительно экстремальной ситуации. Стоит отметить, что тестирующая система далека от идеала – не самая удобная таблица результатов, невозможность задать вопрос через веб-интерфейс. Были в проведении соревнования и некоторые косяки – был поставлен проектор, который показывал таблицу результатов, однако изображение было недостаточно большим, поэтому половина команд просто не могла ничего рассмотреть. Но было много приятных мелочей – Алексей Самсонов пользовался микрофоном для объявлений, всем были розданы очень качественные буклеты о соревновании (привет Питер!) и футболки. Сама идея проведения контеста в одном зале крайне удачна – это как ничто создает нужную атмосферу.
Набережная реки Исеть
Игровой тур
Игровой тур не заставил себя ждать после обеденного перерыва (организации питания не было, но всем вручили карты с хорошими местами для обеда). Это была игра «друг против друга». И чем-то напоминала тетрис. Вы выкладывали фигурки из двух разноцветных шаров на поле 16х8, и уничтожались компоненты одного цвета из 4 и более шаров. Чем больше шаров вы уничтожите за раз (и чем круче «комбо»), тем больше упадет на противника «черных» шаров. Такие шары исчезали, только если рядом с ним была уничтожена цветная компонента (черные компоненты не уничтожались). То есть можно было выиграть, сделав супер-комбо и просто завалив противника черными шарами. Но самое важное, что эти самые черные шары время от времени падали просто так (около 10 штук). Черные шары выпадали на поле в разных местах.
Сразу скажу – тур мне совершенно не понравился, и дело даже не в игре. Многое было неправильно, начиная от непонятной продолжительности (сначала 3.30, потом 4 часа), и заканчивая лишь одним промежуточным тестированием в середине контеста (в нем приняло участие 10-15 команд). Но самое ужасное – это методика тестирования решений. В начале была «швейцарка» из 10-12 туров, потом выбирались 16 команд, которые выходили в плей-офф и играли по олимпийской системе. Основной фейл был в том, что два решения тестировались один раз и только в одной относительной позиции (а условия для игроков не были симметричными), поэтому назвать результаты честными язык не повернется. Кстати, после подведения итогов и просмотра битв финалистов, Сергей Копелиович дал организатором свое решение, и оно «сделало» победителя не напрягаясь.
Команда Саратова
ACM тур
Совсем немного об основном туре. Организаторы делали упор на том, что все задачи оригинальные и нестандартные, и даже если бы у нас был весь e-maxx, нам бы он ни чем не помог. Это действительно так – все задачи оказались очень интересными. Если что-то и можно было назвать стандартным, так это паросочетание в одной из задач (но его написание в решение занимало самую малую часть). Особенно радовали условия – «Число Исенбаева» запомнится нам надолго. Есть неприятный момент, связанный с вопросами жюри: по одному из терминов у многих возник вопрос, но организаторы не сочли нужным отвечать на него. Почти весь контест (кроме начала) команда MSU Unpredictable занимала первое место, а MSU ST – второе, такие места они и заняли, решив 9 и 8 задач соответственно. Третье место заняла команда MIPT Waterogers с шестью задачами. Кстати, в туре участвовала команда тренеров в составе «Жуков, Гольдштейн, Копелиович», которая решила 5 задач.
Те самые трамваи. Главная улица города
Закрытие
Обязательно нужно отметить разбор задач закрытие. Хотя звук был не самым лучшим, и приходилось напрягаться, чтобы что-то понять, каждую задачу (кроме одной) подробно разобрали, рассказали ее историю и вручили призу человеку, который первым сдал эту задачу. Надо сказать, что большинство призов было подобрано в «тему» - нам досталась книга о самураях за задачу о бравом воине, разрезавшим палку своей катаной. Кстати, о той самой «гробовой» задаче, которую так и не разобрали (и как вы догадались ее никто и не решил) – оказывается ей уже 6 лет, а приготовили ее за день до начала основного тура. Завершилось все «фуршетом» из булочек, фруктов и сока.
Пару слов о призах. Победителям игрового тура вручили три приза: PSP, xBox 360 и программируемый конструктор LEGO (мечтаю о таком). Также давали различные головоломки, флешки, настольные игры, жесткие диски. За основной тур давали иные призы. Начали с головоломок и флешек. Мы были первой командой, которой вместо трех флешек (в виде черепа) дали… настольный фонтан, миниатюрную песочницу с камушками и зарядное устройство для ноутбука! Ну в фонтан мы теперь нальем пива и поставим в общагу. Третьему месту дали два простеньких планшета и беспроводные наушники, второму – хорошие планшеты, первому – два нетбука Samsung и еще что-то (не разглядел). Так что почти все остались довольны призами.
Сокомандник с пресловутым фонтаном
Заключение
Ну как же не сказать спасибо уральским ребятам за замечательное соревнование? Спасибо! Ждем следующего года. К сожалению фотографий почти нет, так как помимо меня, там бегало человека три с фотоаппаратами, так что фото отчет нужно искать на оф. сайте.
Укороченная версия статьи для тех, кому некогда читать
- Екатеринбург – классный город, но недешевый.
- Отличное место проведения – большой зал, все сидят вместе, нормальные машины с новым ПО, звуковая аппаратура. Очень качественные брошюры и сувениры.
- Бесподобный пробный тур, проведенный в виде игры «угадай исполнителя песни 90-х».
- Отсутствие организованного питания
- Неплохая игра – некоторое подобие тетриса «друг против друга».
- Ужасная методика тестирования игрового тура и сама организация.
- Отличные задачи на основном туре. Никаких баянов, все условия очень интересные и почти без багов. Немного недоработанная система тестирования (не лучшая таблица результатов, невозможность задать вопрос).
- Интересный разбор задач, необычные и достойные призы (кроме фонтана и песочницы).
- Фуршет в конце, для проголодавшихся программистов.
Ссылки по теме
Это можно простить, потому что организаторы впервые перенесли соревнование из УрГУ в этот спортзал. В УрГУ команды раньше задавали вопросы, сдавали задачи и делали всё остальное через специального клиента.
По-моему это звучит прикольно. Это, по крайней мере, не тупо :о)
Во-вторых, за 4-5 минут проигрывания песни в тестирующую систему приходит несколько сотен сабмитов - прекрасный стресс-тест работы тестирующей системы Timus Offline Judge, которая, насколько я понял, использовалась на контестах такого уровня впервые.
К сожалению, вы не видели монитор пробного тура, а там не было ни одной пустой ячейки, все команды делали попытки по задачам до последнего, ну не бараны же они - думать "омг.. куда я попал, блин" и продолжать пытаться сдавать что-то.
Скажу так - на контесте я был рад что мы не на первых местах, ибо мне большинство из этой музыки не нравиться)
По поводу идеи, на самом деле прикольная. Вот только на мой взгляд надо было сделать более честно по отношению к участникам - и дать музыку всех жанров=)
_________________________
О_о у меня видно со зрением дико туго, т.к. я не нашла ни одного участника (который пришел на пробный тур) без единого плюсика, и так же участников получивших все плюсы тоже не один. Если вы "умудрились", то остается перебор. К нему некоторые прибегали. Цой - конечно хорошо, но если вы при этом не в состоянии узнать ничего более, то это реально странно.
P.S. Кстати, что бы угадать хоть одну песню нужно было хоть один "Новый год" посмотреть телевизор=)
Пару слов про игровой тур.
> Но самое ужасное – это методика тестирования решений. В начале была «швейцарка» из 10-12 туров, потом выбирались 16 команд, которые выходили в плей-офф и играли по олимпийской системе. Основной фейл был в том, что два решения тестировались один раз и только в одной относительной позиции (а условия для игроков не были симметричными), поэтому назвать результаты честными язык не повернется.
Интересно, а какие результаты будут честными в условиях, когда отношение "бот A побеждает бота B" вообще говоря не транзитивно? Кто бы не занял первое место, скорее всего среди остальных участников найдется бот, который побеждает победителя. Так было всегда, и вроде ничего криминального в этом нет. А олимпийская система выбрана, как мне кажется, для более эффектной демонстрации процесса определения победителя :) Единственное, что тут можно сделать более честно, это до начала игрового тура огласить прозрачные правила жеребьевки (randseed'ы и т.п.), но это уже личное дело организаторов и никто их в этом упрекать не может. Вообще рекомендую относиться к игровому туру чуточку попроще, он все таки вторичен по отношению к основному. Едва ли найдутся команды, которые приезжают на ЧУ специально ради игрового тура.
Вы не правы, нам очень интересно было поучаствовать в игровом туре, и не только я считаю его важным. Например, в Новосибирске он влияет на окончательный результат.
Главная проблема была не в швейцарке и не в олимпийской системе, а именно в том, как выяснялось, что "бот A побеждает бота B". Понятно, что транзитивность не выполняется, (как и во всех versus играх, кстати), но чтобы результаты были честным, нужно как минимум:
Можно сказать что в спорте так не делается, но этого не могут себе позволить на ЧМ, так как для проведения 1 мачта нужно много времени (+ команда должна отдохнуть), а тут вопрос пары часов совершенно не критичен! Если уж делать соревнование с реальным призами (хоть и "для фана"), то нужно обеспечить соответствующие условия.
Но далее я не согласен. Игра полностью симметрична - не имеет значения на какой стороне поля вы играете при идеальном рандоме. Т.е. из всех возможных игр, когда один бот играет сам с собой один из них будет выигрывать у другого с вероятностью ровно 50%.
Возможно, Вы имели ввиду несимметричность из-за того, что сид фиксированный - тут тоже не совсем согласен. Никто не знает в пользу какого из участников данный сид будет подыгрывать. Если сид выбрать совершенно случайно - он в 50% случаев будет подыгрывать одному игроку и в 50% - другому. Поэтому тут тоже можно говорить о симметричности игры.
А аргументировать несимметричность игры (или что Вы хотели показать той фразой) тем, что после подведения итогов нашелся внеконкурсный бот, который "сделал" бота победителя, имхо вообще не совсем корректно.
Факт про внеконкурсного бота я привел просто потому что он мне показался забавным, он вообще никак не связан с тестированием (почти уверен, что решение Сергея действительно очень крутое!)
Полностью согласен с тем, что если провести много игр, то игра будет абсолютно симметричной при идеальном рандоме и при запуске эдак 1000 раз. Но вот как раз из-за того, что игра зависит от сида, получается, что это не совсем "рандом", ведь если мы просто много раз запустим игру от одного сида, не меняя позиции местами результат будет всегда одинаков (и тем более именно на этом сиде для одного из игроков может быть "супер-подлянка" и он будет проигрывать именно из-за этого). А если просто поменяем их местами - все может измениться.
Именно для того, чтобы скомпенсировать рандом, нужно как минимум поменять участников местами. А еще лучше провести несколько игр с разными сидами (и рандома и деталек)
Конечно, можно сказать, что найдется такой сид, который будет абсолютно симметричным образом подыгрывать полям наоборот (и выбрать его такая же вероятность, как и данный сид) - поэтому можно и не менять. Но тут я скорее соглашусь с Вами - поменять местами было бы не лишним.
А если серьезно, то да надо было играть минимум до 3 - 5 побед. Но про несимметричность я не согласен, когда тебя ставили налево или направо никто не знал как это отразиться на игре. Более того если бы вас и поменяли местами, черные шары все равно бы выпадали не так как в прошлой игре у противника, ибо был бы просто напросто другой порядок скидывания (скажем ты 1 на него, он 2 на тебя. А теперь 2 на тебя и ты 1 на него). Это не возможно предсказать. То есть симметричности в твоем смысле НЕ БЫЛО БЫ даже если поменять полянами. По этому я считаю что это нормально что все 4 матча в плей офф мы играли справа))))
http://narod.ru/disk/11541374001/MOV00063_xvid.avi.html
Ещё про Timus Offline Judge. Если с вопросами жюри всё понятно (тупо не успели дописать компонент), то про "не лучшую таблицу результатов" хочется более подробного фидбека. Что не так с монитором?
Ждал ваш комментарий!
Я думаю, что можно подводить итоги одновременно с награждением, ведь у вас только в этот раз "открытие" было после игрового тура, а в следующий раз людям придется специально идти, чтобы посмотреть результаты. + Всегда есть возможность распараллелить проверку, если нужно успеть вовремя.
Про таблицу результатов. Просто уже сильно привыкли к двум вещам:
А вот за вопросики - большое человеческое спасибо, это действительно удобной и повышает интерес!