Dmitry Kovalioff
28.03.2006 17:27
О чём эта статья
Мой взгляд на X Чемпионат Урала, проходивший в Екатеринбурге с 23 по 26 марта. Это уже третья подобная статья. Кому интересно, можете почитать "ЧУ 2004 - Black & White" и "ЧУ 2005 - White & Black", посвящённые двум предыдущим ЧУ.
Дисклеймер
Содержание статьи является отражением моей личной позиции. И ещё - чтобы моя критика не была понята неверно - мне на самом деле понравился этот ЧУ, и я готов назвать его лучшим из тех, в которых я участвовал.
Правила
В связи с тем, что ЧУ в этом году проходит не в рамках ACM ICPC, в правилах отсутствуют дурацкие ограничения на возраст и количество участий где бы то ни было. В остальном всё по-прежнему. В списке языков программирования не был упомянут Java, несмотря на то, что он был доступен на чемпионате.
Отдельно хочу пройтись по языкам программирования. Организаторы не пошли по пути балбесов из IBM / ACM / руководства ICPC (мне всё равно) и не стали исключать Delphi. Другое дело, что иначе ЧУ недосчитался бы половины команды - но тем не менее такая позиция мне импонирует. Ситуацию с Delphi на предстоящем в октябре четвертьфинале я буду обсуждать непосредственно с организаторами.
Официальный сайт
Отсутствует. Ссылка http://acm.usu.ru вела на главную страницу сайта "Уральские олимпиады", откуда можно было попасть на страницу ЧУ из списка предстоящих соревнований. Конечно, это неправильно. Если уж было принято решение отказаться от создания полноценного сайта (что само по себе плохо), то ссылка должна была вести непосредственно на страницу ЧУ. Сама страница состоит их нескольких типовых разделов ("Общая информация", "Расписание чемпионата" и т.д.). Раздел "Досуг" я обнаружил только по возвращении домой после чемпионата - очевидно, его добавили в последний момент, но всё равно спасибо. Разделы "Новости", "Фотографии" и т.п. организаторы посчитали ненужными. Печально.
Регистрация команд выполнялась организаторами вручную по заявкам, а это неудобно, т.к. модифицировать информацию о команде было невозможно, да и таблица обновлялась не сразу. Форма для заполнения этих заявок, как я понял по названиям полей в HTML-коде, была позаимствована со страницы какой-то школьной олимпиады. Добавлять поле "Название команды" было, наверное, неправильно. Я предлагаю всё-таки использовать номер команды. А так в таблице получилось странное смешение номеров и названий команд и университетов, да ещё и на разных языках.
Видно, что здесь организаторы пошли по пути наименьшего сопротивления. Я допускаю, имела место нехватка времени, но в любом случае web-страница выглядит несерьёзно.
Проживание
Похоже, гостинице "Рось-92" наконец-то пришёл конец. Побочным эффектом этого приятного факта стало то, что все остальные гостиницы оказались переполненными. Отдельная благодарность организаторам и лично тов. Гальперину за предоставленные места в профилактории УрГУ. У некоторых команд были проблем с заселением из-за нехватки мест, но нас поселили сразу же. Единственный существенный недостаток - туалет был на другом этаже и через коридор (зато какой коридор ;) ), а так всё просто замечательно. Хороший и чистый номер с телевизором. Душ буквально за дверью. На первом этаже неплохая столовая. Добираться до УрГУ и обратно относительно удобно.
В общем, предлагаю организаторам бронировать места в этом профилактории и на октябрьский четвертьфинал.
Регистрация и брошюры
Процедура регистрации прошла быстро и без проблем. Зачем-то спросили, была ли наша команда на полуфинале, и после утвердительного ответа выдали сертификаты участников, брошюры ЧУ, значки и наклейки на системный блок. Значки маленькие, но стильные, а наклейку на системник я уже использовал по назначению. Забавно - на брошюрах и указателях, расклеенных по стенам, присутствовала символика ACM ICPC.
Большая часть брошюры посвящена задачам ЧУ 2005 и их решению (ну и как решается "Мизер" за 1 секунду? и кто хочет подарить мне решение "Звезды смерти", чтобы я не парился с перемножением векторов в 3D?). Также имеется пара небольших статей и рейтинг вузов под редакцией тов. Асанова (может быть, придёт день - и однажды название моего университета всё-таки исправят с "Tumen SOGU" на "Tyumen SOGU"?). На месте организаторов я бы добавил ещё и расписание чемпионата.
Также выдавали памятки, но я их особо не разглядывал, поэтому ничего конкретного сказать не могу. Насколько помню, всё то же самое, что и в прошлом году, т.е. это весьма полезная штука для тех, кто на ЧУ первый раз.
Раздевалки, питание и общие сборы
К работе раздевалки претензий нет. Обед в первый день был организован в главной столовой УрГУ. И совершенно напрасно - толпа желающих отобедать участников была дополнена не меньшей толпой студентов УрГУ, в результате чего подносов для еды не хватало даже больше, чем столов. Представляю себе тему курсовой работы: "Моделирование системы массового обслуживания на примере столовой УрГУ". Ситуация повторяется уже третий год, и это не предел, т.к. по словам тов. Клепинина столовая неплохо защищена от административных воздействий. Однако где-то в подвале УрГУ обнаружилась ещё одна столовая, где и был проведён обед второго дня. Нагрузка на эту столовую оказалась существенно меньше, поэтому время ожидания в очереди было вполне приемлемым.
Все запланированные мероприятия прошли более или менее в рамках расписания. Организаторы наконец-то начали использовать микрофоны, поэтому на этот раз, по крайней мере, было всё слышно. Да и актовый зал отремонтировали - теперь сидеть стало удобнее.
Открытие прошло довольно быстро и ничем особенным не запомнилось. Очевидной ошибкой организаторов была выдача задания на турнир программ перед открытием, поскольку потом все читали и обсуждали это задание, не обращая особого внимания на выступления спонсоров и организаторов.
Так называемый "мастер-класс" оказался скучнейшим повествованием о тщете всего сущего. Сдаётся мне, что поднятую в этой лекции тему (о связи промышленного и спортивного программирования) можно было раскрыть более интересно. А лучше было бы вместо этого рассказать, скажем, о методиках подготовки команд УрГУ, сайте Timus Online Judge, прошлых Чемпионатах Урала, кубке CBOSS, ACM ICPC вообще и полуфинале/финале в частности и т.д. В сущности, не более трети присутствовавших команд имели какие-то реальные шансы на участие в более крупных соревнованиях, поэтому было бы неплохо просветить и заинтересовать остальных.
Пробный тур
Тексты задач опять были выданы заранее. Говорю второй раз и готов повторить ещё - это просто глупо. Не вижу ни одной причины для досрочной выдачи текстов. Что мешало положить их под клавиатуру, как на основном туре? Хотя бы из соображений элементарного порядка. Проверяющая система по-прежнему дико тормозила - задачи проверялись по 10 минут (на основном туре ситуация улучшилась, но даже 2-3 минуты - это всё равно долго), монитор загружался через раз, а клиентская оболочка, перерисовываясь, подвешивала на несколько секунд всю систему. И ещё прошу добавить вертикальную полосу прокрутки к полю для ввода вопроса жюри - сейчас длинные вопросы приходится набивать в блокноте.
Турнир программ
В этот раз организаторы по примеру финала и Всесибирской Олимпиады решили устроить своего рода творческий тур - так называемый турнир программ. Для решения была предложена задача моделирования действий муравья по сбору еды на дискретном поле. Но организаторы не учли того факта, что функции dll позволяют использовать глобальные переменные, если библиотека загружается статически. Короче говоря, программа TestRoom, визуализирующая действия муравьёв, допускала использование глобальных переменных, поэтому размер памяти муравья не имел никакого значения (нужен был только 1 байт под идентификатор), а маркировка запахом оказалась просто бесполезной. Но нужно отдать должное организаторам - задача была на самом деле интересной. Может быть, не стоит ждать ЧУ 2007, а взять и провести турнир программ в первый день четвертьфинала?
Информационная безопасность
Специально выделяю под это дело целый параграф, т.к. это предельно важно.
Перед основным туром (в отличие от полуфинала) содержимое рабочих папок ничто не чистил, поэтому на пробном и творческом турах за 4 часа можно было вбить изрядно типовых алгоритмов типа QSort или интервального дерева.
Во время контеста народ прогуливался по аудитории и за её пределами без всяких ограничений. Контроля со стороны организаторов не было вообще - обслуживающий персонал либо не был проинструктирован, либо просто решил на всё забить. Если бы я принёс с собой ноутбук и Кормена с Романовским, ничего бы не произошло. А уж незаметно воткнуть флэшку с несколькими мегабайтами электронной документации и исходников - так это вообще было раз плюнуть. Готов спорить, что некоторые так и поступили.
В свете всего этого было исключительно забавно наблюдать, как перед контестом члены команды УПИ, высунув от напряжения языки, обычной шариковой ручкой перекатывали с тетрадки какой-то алгоритм себе на запястья - прямо как школьники перед экзаменом :lol:
Короче говоря, с информационной безопасностью нужно срочно что-то делать. Иначе скоро кто-нибудь точно сдаст задачу на венгерский алгоритм на пятой минуте контеста.
Контест
Тексты задач опять выдавались из расчёта один комплект на команду. Ну ладно, будем считать это традицией Чемпионатов Урала.
Проблемсет мне очень понравился. Три однозначно халявных задачи позволили проранжировать команды нижней половины таблицы. Я уже сдал все задачи на Timus Online Judge, поэтому могу высказать свои соображения по поводу некоторых из них:
A. Интервальное дерево без всяких оптимизаций порвало таймлимит в 6,5 раз. Странно, что эта задача считалась организаторами самой сложной. То есть идейно-то она элементарная, но вот вбивать это дерево во время контеста... В общем, надо было с собой на флэшке приносить.
C. Идея достраивания имеющегося графа до эйлерова уже где-то использовалась, но всё равно задача классная - довольно сложная, но тем не менее решаемая. У меня с двукратным запасом по времени зашло решение с линейным удалением рёбер из списков смежности при построении эйлерова цикла, хотя, в общем, это можно сделать и за логарифм.
D. Моё решение долго не могло зайти по времени, т.к. нужное приближение достигалось лишь при очень малом dh и соответственно большом времени - обратные тригонометрические функции вычисляются медленно. Я уже думал об интерполяции по Лагранжу, но оказалось, что начальные условия взяты немного неправильно. После этого всё зашло очень быстро. Организаторы были правы - задача на самом деле не сложная, а просто неожиданная - на интернет-контесте в воскресенье её никто не решил. Да, такие задачи тоже полезны.
I. Легко зашло решение, использующее обычную дихотомию, так что более продвинутые методы не понадобились. Всё равно хорошая задача.
Отдельный респект тов. Васильеву за отличные тексты задач. Я сейчас как раз пишу тексты к Timus Top Coders: Second Challenge, но там они выдержаны в несколько иной стилистике :)
Награждение и заключительный ужин
Несмотря на позорное выступление (и что самое обидное, не по моей вине :evil: ), нашу команду наградили дипломом третьей степени. Точнее, "третей" степени. Да, велик и могуч русский язык.
На этот раз призы за первые три места были более чем приличными - сотовые телефоны, КПК, mp3-плееры и т.п. По всему видно, что спонсоры изрядно потратились. Правда, у победителей и сотовые телефоны, и mp3-плееры наверняка уже были. Может, лучше деньгами? ;)
Заключительный ужин - без претензий. Немного пообщался с тов. Клепининым и посмотрел на команду местных первокурсников. Надо же, люди прямо на фуршете подходят к тренеру и просят увеличить количество тренировок. Эх, мне бы таких первокурсников - и можно начинать завоевание галактики. Хоть сейчас собирать вещи и переезжать в Свердловск :)
Итого
Вот так оно и бывает. Вроде бы собирался на пенсию ещё в прошлом году, а теперь сильно подозреваю, что приму участие ещё и в своём пятом ЧУ на следующий год, не говоря уже о четвертьфинале (который станет моим шестым официальным четвертьфиналом - как я понимаю, абсолютный рекорд ;) ). Это к тому, что я крайне заинтересован в том, чтобы последние в моей карьере участника ЧУ и четвертьфинал были проведены на ещё более высоком уровне, чем этот.
P.S. Пользуясь случаем, приглашаю всех желающих принять участие в интернет-контесте Timus Top Coders: Second Challenge. Контест пройдёт на Timus Online Judge ориентировочно 22 апреля.
Мой взгляд на X Чемпионат Урала, проходивший в Екатеринбурге с 23 по 26 марта. Это уже третья подобная статья. Кому интересно, можете почитать "ЧУ 2004 - Black & White" и "ЧУ 2005 - White & Black", посвящённые двум предыдущим ЧУ.
Дисклеймер
Содержание статьи является отражением моей личной позиции. И ещё - чтобы моя критика не была понята неверно - мне на самом деле понравился этот ЧУ, и я готов назвать его лучшим из тех, в которых я участвовал.
Правила
В связи с тем, что ЧУ в этом году проходит не в рамках ACM ICPC, в правилах отсутствуют дурацкие ограничения на возраст и количество участий где бы то ни было. В остальном всё по-прежнему. В списке языков программирования не был упомянут Java, несмотря на то, что он был доступен на чемпионате.
Отдельно хочу пройтись по языкам программирования. Организаторы не пошли по пути балбесов из IBM / ACM / руководства ICPC (мне всё равно) и не стали исключать Delphi. Другое дело, что иначе ЧУ недосчитался бы половины команды - но тем не менее такая позиция мне импонирует. Ситуацию с Delphi на предстоящем в октябре четвертьфинале я буду обсуждать непосредственно с организаторами.
Официальный сайт
Отсутствует. Ссылка http://acm.usu.ru вела на главную страницу сайта "Уральские олимпиады", откуда можно было попасть на страницу ЧУ из списка предстоящих соревнований. Конечно, это неправильно. Если уж было принято решение отказаться от создания полноценного сайта (что само по себе плохо), то ссылка должна была вести непосредственно на страницу ЧУ. Сама страница состоит их нескольких типовых разделов ("Общая информация", "Расписание чемпионата" и т.д.). Раздел "Досуг" я обнаружил только по возвращении домой после чемпионата - очевидно, его добавили в последний момент, но всё равно спасибо. Разделы "Новости", "Фотографии" и т.п. организаторы посчитали ненужными. Печально.
Регистрация команд выполнялась организаторами вручную по заявкам, а это неудобно, т.к. модифицировать информацию о команде было невозможно, да и таблица обновлялась не сразу. Форма для заполнения этих заявок, как я понял по названиям полей в HTML-коде, была позаимствована со страницы какой-то школьной олимпиады. Добавлять поле "Название команды" было, наверное, неправильно. Я предлагаю всё-таки использовать номер команды. А так в таблице получилось странное смешение номеров и названий команд и университетов, да ещё и на разных языках.
Видно, что здесь организаторы пошли по пути наименьшего сопротивления. Я допускаю, имела место нехватка времени, но в любом случае web-страница выглядит несерьёзно.
Проживание
Похоже, гостинице "Рось-92" наконец-то пришёл конец. Побочным эффектом этого приятного факта стало то, что все остальные гостиницы оказались переполненными. Отдельная благодарность организаторам и лично тов. Гальперину за предоставленные места в профилактории УрГУ. У некоторых команд были проблем с заселением из-за нехватки мест, но нас поселили сразу же. Единственный существенный недостаток - туалет был на другом этаже и через коридор (зато какой коридор ;) ), а так всё просто замечательно. Хороший и чистый номер с телевизором. Душ буквально за дверью. На первом этаже неплохая столовая. Добираться до УрГУ и обратно относительно удобно.
В общем, предлагаю организаторам бронировать места в этом профилактории и на октябрьский четвертьфинал.
Регистрация и брошюры
Процедура регистрации прошла быстро и без проблем. Зачем-то спросили, была ли наша команда на полуфинале, и после утвердительного ответа выдали сертификаты участников, брошюры ЧУ, значки и наклейки на системный блок. Значки маленькие, но стильные, а наклейку на системник я уже использовал по назначению. Забавно - на брошюрах и указателях, расклеенных по стенам, присутствовала символика ACM ICPC.
Большая часть брошюры посвящена задачам ЧУ 2005 и их решению (ну и как решается "Мизер" за 1 секунду? и кто хочет подарить мне решение "Звезды смерти", чтобы я не парился с перемножением векторов в 3D?). Также имеется пара небольших статей и рейтинг вузов под редакцией тов. Асанова (может быть, придёт день - и однажды название моего университета всё-таки исправят с "Tumen SOGU" на "Tyumen SOGU"?). На месте организаторов я бы добавил ещё и расписание чемпионата.
Также выдавали памятки, но я их особо не разглядывал, поэтому ничего конкретного сказать не могу. Насколько помню, всё то же самое, что и в прошлом году, т.е. это весьма полезная штука для тех, кто на ЧУ первый раз.
Раздевалки, питание и общие сборы
К работе раздевалки претензий нет. Обед в первый день был организован в главной столовой УрГУ. И совершенно напрасно - толпа желающих отобедать участников была дополнена не меньшей толпой студентов УрГУ, в результате чего подносов для еды не хватало даже больше, чем столов. Представляю себе тему курсовой работы: "Моделирование системы массового обслуживания на примере столовой УрГУ". Ситуация повторяется уже третий год, и это не предел, т.к. по словам тов. Клепинина столовая неплохо защищена от административных воздействий. Однако где-то в подвале УрГУ обнаружилась ещё одна столовая, где и был проведён обед второго дня. Нагрузка на эту столовую оказалась существенно меньше, поэтому время ожидания в очереди было вполне приемлемым.
Все запланированные мероприятия прошли более или менее в рамках расписания. Организаторы наконец-то начали использовать микрофоны, поэтому на этот раз, по крайней мере, было всё слышно. Да и актовый зал отремонтировали - теперь сидеть стало удобнее.
Открытие прошло довольно быстро и ничем особенным не запомнилось. Очевидной ошибкой организаторов была выдача задания на турнир программ перед открытием, поскольку потом все читали и обсуждали это задание, не обращая особого внимания на выступления спонсоров и организаторов.
Так называемый "мастер-класс" оказался скучнейшим повествованием о тщете всего сущего. Сдаётся мне, что поднятую в этой лекции тему (о связи промышленного и спортивного программирования) можно было раскрыть более интересно. А лучше было бы вместо этого рассказать, скажем, о методиках подготовки команд УрГУ, сайте Timus Online Judge, прошлых Чемпионатах Урала, кубке CBOSS, ACM ICPC вообще и полуфинале/финале в частности и т.д. В сущности, не более трети присутствовавших команд имели какие-то реальные шансы на участие в более крупных соревнованиях, поэтому было бы неплохо просветить и заинтересовать остальных.
Пробный тур
Тексты задач опять были выданы заранее. Говорю второй раз и готов повторить ещё - это просто глупо. Не вижу ни одной причины для досрочной выдачи текстов. Что мешало положить их под клавиатуру, как на основном туре? Хотя бы из соображений элементарного порядка. Проверяющая система по-прежнему дико тормозила - задачи проверялись по 10 минут (на основном туре ситуация улучшилась, но даже 2-3 минуты - это всё равно долго), монитор загружался через раз, а клиентская оболочка, перерисовываясь, подвешивала на несколько секунд всю систему. И ещё прошу добавить вертикальную полосу прокрутки к полю для ввода вопроса жюри - сейчас длинные вопросы приходится набивать в блокноте.
Турнир программ
В этот раз организаторы по примеру финала и Всесибирской Олимпиады решили устроить своего рода творческий тур - так называемый турнир программ. Для решения была предложена задача моделирования действий муравья по сбору еды на дискретном поле. Но организаторы не учли того факта, что функции dll позволяют использовать глобальные переменные, если библиотека загружается статически. Короче говоря, программа TestRoom, визуализирующая действия муравьёв, допускала использование глобальных переменных, поэтому размер памяти муравья не имел никакого значения (нужен был только 1 байт под идентификатор), а маркировка запахом оказалась просто бесполезной. Но нужно отдать должное организаторам - задача была на самом деле интересной. Может быть, не стоит ждать ЧУ 2007, а взять и провести турнир программ в первый день четвертьфинала?
Информационная безопасность
Специально выделяю под это дело целый параграф, т.к. это предельно важно.
Перед основным туром (в отличие от полуфинала) содержимое рабочих папок ничто не чистил, поэтому на пробном и творческом турах за 4 часа можно было вбить изрядно типовых алгоритмов типа QSort или интервального дерева.
Во время контеста народ прогуливался по аудитории и за её пределами без всяких ограничений. Контроля со стороны организаторов не было вообще - обслуживающий персонал либо не был проинструктирован, либо просто решил на всё забить. Если бы я принёс с собой ноутбук и Кормена с Романовским, ничего бы не произошло. А уж незаметно воткнуть флэшку с несколькими мегабайтами электронной документации и исходников - так это вообще было раз плюнуть. Готов спорить, что некоторые так и поступили.
В свете всего этого было исключительно забавно наблюдать, как перед контестом члены команды УПИ, высунув от напряжения языки, обычной шариковой ручкой перекатывали с тетрадки какой-то алгоритм себе на запястья - прямо как школьники перед экзаменом :lol:
Короче говоря, с информационной безопасностью нужно срочно что-то делать. Иначе скоро кто-нибудь точно сдаст задачу на венгерский алгоритм на пятой минуте контеста.
Контест
Тексты задач опять выдавались из расчёта один комплект на команду. Ну ладно, будем считать это традицией Чемпионатов Урала.
Проблемсет мне очень понравился. Три однозначно халявных задачи позволили проранжировать команды нижней половины таблицы. Я уже сдал все задачи на Timus Online Judge, поэтому могу высказать свои соображения по поводу некоторых из них:
A. Интервальное дерево без всяких оптимизаций порвало таймлимит в 6,5 раз. Странно, что эта задача считалась организаторами самой сложной. То есть идейно-то она элементарная, но вот вбивать это дерево во время контеста... В общем, надо было с собой на флэшке приносить.
C. Идея достраивания имеющегося графа до эйлерова уже где-то использовалась, но всё равно задача классная - довольно сложная, но тем не менее решаемая. У меня с двукратным запасом по времени зашло решение с линейным удалением рёбер из списков смежности при построении эйлерова цикла, хотя, в общем, это можно сделать и за логарифм.
D. Моё решение долго не могло зайти по времени, т.к. нужное приближение достигалось лишь при очень малом dh и соответственно большом времени - обратные тригонометрические функции вычисляются медленно. Я уже думал об интерполяции по Лагранжу, но оказалось, что начальные условия взяты немного неправильно. После этого всё зашло очень быстро. Организаторы были правы - задача на самом деле не сложная, а просто неожиданная - на интернет-контесте в воскресенье её никто не решил. Да, такие задачи тоже полезны.
I. Легко зашло решение, использующее обычную дихотомию, так что более продвинутые методы не понадобились. Всё равно хорошая задача.
Отдельный респект тов. Васильеву за отличные тексты задач. Я сейчас как раз пишу тексты к Timus Top Coders: Second Challenge, но там они выдержаны в несколько иной стилистике :)
Награждение и заключительный ужин
Несмотря на позорное выступление (и что самое обидное, не по моей вине :evil: ), нашу команду наградили дипломом третьей степени. Точнее, "третей" степени. Да, велик и могуч русский язык.
На этот раз призы за первые три места были более чем приличными - сотовые телефоны, КПК, mp3-плееры и т.п. По всему видно, что спонсоры изрядно потратились. Правда, у победителей и сотовые телефоны, и mp3-плееры наверняка уже были. Может, лучше деньгами? ;)
Заключительный ужин - без претензий. Немного пообщался с тов. Клепининым и посмотрел на команду местных первокурсников. Надо же, люди прямо на фуршете подходят к тренеру и просят увеличить количество тренировок. Эх, мне бы таких первокурсников - и можно начинать завоевание галактики. Хоть сейчас собирать вещи и переезжать в Свердловск :)
Итого
Вот так оно и бывает. Вроде бы собирался на пенсию ещё в прошлом году, а теперь сильно подозреваю, что приму участие ещё и в своём пятом ЧУ на следующий год, не говоря уже о четвертьфинале (который станет моим шестым официальным четвертьфиналом - как я понимаю, абсолютный рекорд ;) ). Это к тому, что я крайне заинтересован в том, чтобы последние в моей карьере участника ЧУ и четвертьфинал были проведены на ещё более высоком уровне, чем этот.
P.S. Пользуясь случаем, приглашаю всех желающих принять участие в интернет-контесте Timus Top Coders: Second Challenge. Контест пройдёт на Timus Online Judge ориентировочно 22 апреля.