Архив форума

Вероятно, организаторам 1/4 финала и его участникам (да и всем остальным) будет полезно познакомиться с моими выводами. Это только моё мнение, и оно может не совпадать с мнением остальных (типа дисклеймер :] ).

0. Официальный сайт.

Сайт ЧУ обладает несколько примитивным дизайном, но по крайней мере быстро грузится, удобен в использовании и почти не глючит. Можно было выложить дополнительную информацию, например, бланки договоров, сведения о системе проверки, фотографии и т.д.

1. Проживание.

Гостиница оказалась расположеной у чёрта на куличках напротив какого-то развалившегося завода. Вид из окна просто пострясающий :) На момент нашего прибытия 3-местные номера (которые мы забронировали при регистрации на сайте чемпа) закончились, пришлось брать 4-местные. Один туалет на этаж, душ вообще на первом этаже. Для сравнения, на полуфинале мы жили в 2-местных номерах с телевизором, радио, чайником, туалетом и душем в каждом номере. В довершении всего все 4 дня нашего пребывания в гостинице постоянно кто-то пил - в основном программисты ;)

С другой стороны, нельзя не отметить следующие несомненные достоинства гостиницы:
- дешёвые номера
- простой путь в УрГУ и обратно
- приемлимое качество обслуживания

Таким образом, организацию проживания иногородних участников можно признать удовлетворительной. На будущий год я рекомендую организаторам поступить так, как было в прошлом году в Челябинске - предложить командам на выбор несколько гостиниц различных ценовых категорий, в результате чего каждая команда получит такое жильё, за которое будет в состоянии заплатить.

2. Регистрация

Найти место регистрации в УрГУ оказалось непросто. Мы обнаружили только 2 малозаметные бумажки, почему-то направлявшие нас в разные аудитории - 604 и 640. В результате задача поиска была решена перебором :)

Сама регистрация прошла нормально и без проволочек. Всем участникам выдали книжки в историей ACM в России (на полуфинале давали такие же), а также брошюры 1/4 финала. К этим брошюрам есть серьёзные претензии: авторы почему-то решили, что участникам будет намного интереснее узнать про какой-то турнир в поддавки, чем, например, про расписание мероприятий, работу проверяющей системы, количество разыгрываемых мест в полуфинале и т.п. В результате для всей этой действительно важной информации места не нашлось, поскольку 2/3 брошюры занимали реклама математико-механического факультета УрГУ и подробный рассказ о пресловутом турнире в поддавки. Ещё бы анекдоты на последней странице напечатали - совсем было бы здорово :)

Разочаровало отсутствие памятных значков (как в прошлом году) - в следующий раз было бы неплохо сделать. Зато ручки на этот раз были с символикой чемпионата.

3. Раздевалки, питание и общие сборы

Прекрасная идея - поручить одной из раздевалок обслуживать исключительно участников. К работе раздевалки претензий нет.

Неплохо и то, что в столовой для нас была отдельная очередь. К сожалению, эта очередь (вопреки заверениям организаторов) временами двигалась очень медленно, к тому же нехватало подносов для еды. Наилучшим решением было бы на 40-60 минут закрыть столовую для всех посторонних посетителей - думаю, студенты УрГУ не умерли бы от голода, зато качество организации питания серьёзно бы возросло. Кстати, сами обеды были очень вкусными :)

Плохо то, что во время проведения чемпионата в университете проводились обычные занятия. Я допускаю, что отменить занятия во всём корпусе было нереально, но хотя бы на 6-ом и 5-ом этажах это должно было быть сделано. Когда у нас проводили областную олимпиаду, на день закрыли целый корпус, а здесь мы были вынуждены постоянно пробиваться сквозь толпы студентов и иногда даже дожидаться окончания пары в какой-нибудь аудитории.

4. Досуг

Организаторы приняли очень спорное решение – организовать 4-часовое сидение на лекциях. Первая и последние 2 лекции были приличными, зато вторую (про динамику кальция в каких-то клетках), по-моему, никто даже не пытался понять. Кстати, людям высокого роста в актовом зале сидеть очень неудобно – дистанция между рядами кресел маленькая. Идея организовать «Что? Где? Когда?» неплохая – я играю в ЧГК уже несколько лет, мне понравилось – но опять же на любителя.

Короче говоря, желание организаторов пойти по пути наименьшего сопротивления понятно. И всё же мне кажется, что в Челябинске это было сделано лучше – экскурсия по городу и поход в классный кинотеатр тоже имеют свои преимущества. Всё-таки если человек едет за несколько сот километров на 4 дня в самый большой город Урала, он может расчитывать на знакомство с его достопримечательностями. Предлагаю организаторам подумать над этим.

5. Контест

В организации контроля над участниками были обнаружены существенные недостатки. Мальчики и девочки с жёлтыми бейджами тщательно следили за тем, чтобы никто до начала контеста не запускал FAR, зато контестанты могли свободно ходить внутри аудитории, а входить и выходить на произвольное время мог, кажется, кто угодно. Вынести своему человеку тексты заданий или просто посовещаться в коридоре было элементарно. Напомню, что в Челябинске даже в туалет водили под конвоем и по одному, да и на полуфинале был жёсткий контроль.

Также не понравилось, что выдавали по одному комплекту задач на команду, когда следовало бы дать 3. В распечатках задачи были почему-то расположены не по порядку, а с целью минимизации количества листов. Создавалось впечатление, что организаторы пытались сэкономить на бумаге. В следующий раз, вероятно, тексты будут печататься вообще с двух сторон :)

Сами проблемсеты были на уровне, есть только несколько замечаний:
- поскольку я исследователь задач, а не спортивный программист, мне кажется, что 10 задач на 5 часов – это много. Максимум 8. Как говорится, лучше меньше, да лучше. Хотя вопрос, конечно, спорный
- задача D второго тура была сформулирована некорректно. В условии требовалось представить (present) граф в виде множества (set) пар смежных рёбер. Я понял это как требование _представить_ граф в _форме_ множества пар его смежных рёбер. Причём это представление должно определять граф однозначно, т.е. по множеству пар рёбер можно восстановить этот и только этот граф, также как, например, по его матрице смежности. На самом деле требовалось просто _разбить_ граф на пары смежных рёбер, причём каждое ребро должно встречаться только в одной паре (в то время как в условии про это ничего не говорилось – _множество_ пар рёбер подразумевает уникальность пары, а не рёбер). Товарищи составители задач, будьте аккуратнее с английским языком!
- на некоторые задачи проходили читерские (например, переборные) или неэффективные решения при существовании более эффективных алгоритмов
- непонятна ситуация с мемори лимитами

Здорово, что параллельно на тимусе проходил интернет-контест.

6. Результаты

Думаю, не только мне непонятна сокрушительная победа команды УрГУ во главе с Дэном Расковаловым. Видимо, дома не только стены помогают :) Конечно, никаких доказательств нечестной игры у меня нет, поэтому не буду растекаться мыслью по древу о причинах такого успеха. Как мне сказал Илья Немец, «полуфинал расставит всех по местам».

7. Награждение и заключительный ужин

На мой взгляд, награждение прошло излишне скромно и недостаточно официально – пять минут игры на рояле и раздача призов. Причём, сдаётся мне, призы можно было бы сделать подороже и более по теме – например, книжки по программированию с автографами М. Асанова, Л. Волкова и П. Атнашева ;) С другой стороны, впервые вручался кубок чемпионов Урала – это отличная идея.

Заключительный ужин – это было круто :) В десять раз лучше, чем в Челябинске. Никаких претензий.

8. Итого

В общем-то неплохо. Очевидные недостатки поддаются исправлению, а достоинства – приумножению. Хочется верить, что следующий ЧУ я смогу назвать лучшим за всю историю проведения.

P.S. Мне тут А. Мироненко предложил организовать следующий четвертьфинал - а для меня нет ничего невозможного. Как вы на это смотрите?

...просто мимо проходил...

-1 (минут один): к вашему приезду обновили компьютерную технику. ты бы видел, что стояло в 514 до олимпиады. надеюсь, оно куплено, а не взято в аренду :))по-моему господа участники достаточно взрослые, чтобы самостоятельно решить задачу поиска гостиницы, если предложенный generic не устраивает...наилучшим решением было бы показать вам секретную столовую, которая находится через дорогу. немножко дороже, поэтому студенты туда почти не ходят, и очередь редко превышает 10 человек. двигается быстро. но, очевидно, патриотизм не позволил...это означало бы "отменить занятия на всем факультете" :wink:#$%@# !!!!!!! :oops: :oops: :oops: :oops: :oops: :oops:согласен. у меня при ее прочтении возник вопрос, который я бы обязательно отправил жюри, если бы учавствовал в очном.:oops: :oops: :oops: :oops: :oops:зачем обязательно четвертьфинал? организуй уж сразу свое собственное соревнование, найди спонсоров, составителей задач, участников... :lol: все будут в майках с твоим именем тусоваца!

Все желающие подошли после рабора первого тура к оргкомитету и выяснили где в городе находятся интерсные ИМ места. Если участник не проявляет активной позиции, значит ему не нужны достопримечательности, тем более что их в городе практически нет.Думали. Ну нет в городе достпримечательностей. Развалившиеся купеческие особняки конца 19 века? Построенная год назад церковь на месте расстрела царской семьи? Краеведческий музей? Картинная галерея? Супермаркеты? Компьютерные клубы? Ночные клубы? Разве это можно назвать достопримечательностями - этого добра в каждом городе хватает.Нас подводит дурацкая привычка доверять участникам. И своим, и чужим.Верстались они (первый день мной лично) по порядку, кроме одной задачи в каждом туре - каждая из них занимала четвертушку страницы. Перемешались они уже при размножении, но не вижу в этом вообще никакой проблемы. Все равно номера задачам были присвоены почти случайно.Мы не исследовательский семинар проводим, а соревнование, цель - не исследовать, а расставить команды по ранжиру. Победители решают по 8 задач за тур, последнее место - 1, комплект адекватен набору участников. Уфа, например, имела 8 за час до конца, и могла (теоретически) продавить девятую. А если бы их всего было 8?При этом все лидеры, не задавая лишних вопросов, сдали ее с первой попытки. Видимо у них словари какие-то другие :)Если это решение быстро писалось и укладывалось в тайм-лимит - оно достаточно эффективно.Что тут непонятного? Обещанные 10 Mb были доступны всем. Все в равных условиях.Тогда лучше молчать. Еще никто не пытался обвинить УрГУ в нечестности. Пермь безуспешно потратила два с лишним часа на задачу "Тарелки" и не увидела простую задачу "Пирамида" - вот вам и разница 8-6. Расковалов просто знал (5 лет уже играет), что в задачах Петрова не бывает простой геометрии и все граничные и вырожденные тесты будут присутствовать.Легко. Генеральный спонсор следующего четвертьфинала - Dmitry Kovalioff. Советую уже начинать собрать деньги, тысяч так 5 у.е.Художественные альбомы - это действительно традиция в УрГУ.В одиночку? Тогда хотелось бы увидеть примерную раскладку по
следующим вопросам:
Где взять и куда поставить на неделю 100 компьютеров, соединенных сетью, да так, чтобы их хозяин не сильно обиделся?
Где поселить 200 человек, чтобы это было относительно рядом и не очень дорого?
Кто напишет 16 крутых задач (из разных областей) с полными тестами и решениями на двух разных языках?
Кто будет выписывать счета-фактуры и отмечать командировки? (нужно юридическое лицо)
Кто оплачивает значки и прочую символику, и где все это будет производиться?

Простите за оффтоп, НОА почему задач на графы не было (4 одинаковые волны не считаются)??? В Питере без 2-3 графовых задач уже давно не обходятся.

справедливости ради, у команд УрГУ действительно было преимущество.

1) натасканность на задачи конкретных авторов
2) к задачам spy и archiver ургу-шные команды были подготовлены задачей с ДММнаверное, опытные команды уже умеют читать между строк, иначе где еще они прочтли, чего от них хотят на самом деле? :wink:

Хотел бы поблагодарить Дмитрия Ковалева за разбор полетов (крайне полезное мероприятие, между прочим, особенно для нас - ведь нам и в следующем году проводить ЧУ) и высказать свою (свою личную, конечно!) точку зрения по затронутым вопросам.Почти полностью согласен. "Примитивный" дизайн или нет - дело вкуса, у нас ведь спортивное меропритиятие, а сайт имеет чисто информационную функцию, а по остальным пунктам трудно поспорить. Думаю, в следующий раз будет лучше.А здесь ситуация такая - каждому видно со своей колокольни. Здесь я могу авторитетом задавить :-) Дело в том, что моя работа связана с командировками, и почти во всех уральских (и не только уральских) городах я за последние два года побывал, и не по разу. Так вот, такой проблемной ситуации с гостиницами, как в Екатеринбурге, нет нигде. Я жил в Кургане в отличной гостинице за 450 р., в Тюмени в очень приличной - за 250 р., в Волгограде за 350, а в Кемерово за 500... И что теперь? Эти примеры ничего не доказывают... Когда мы проводили партнерский семинар для своих региональных партнеров и дилеров, мы в итоге ничего лучшего не нашли, как их всех увезти на турбазе (был бы идеальный вариант и для ЧУ, если бы нашлась турбаза на 70 компьютеров :-) ). Почему? Потому что самый дешевый вариант размещения в черте города был у черта на куличках от 1500р. за двухместный номер. Ну вот так вот у нас! В Екатеринбурге гостиницы дороже питерских и сравнимы с московскими. Поэтому тот факт, что нашлась эта сама Рось - просто манна небесная. И предоставить участникам на выбор список гостиниц было невозможно - выбирать было не из чего... Ну а желающие, конечно, могли с помощью Интернета и телефона сами порешать задачу расселения, в этом нет ничего сложного. Ижевцы, например, жили в "Большом Урале" - мягко говоря, подороже, зато через дорогу от УрГУ. Но заказать 150 мест за умеренную цену в Екатеринбурге просто нельзя. Поверьте на слово.Полностью разделяю критику по брошюрам. Мне самому нравится моя прошлогодняя статья про поддавки, но я тоже совершенно не понял, с какого хрена ей отвелось основное место в брошюрке ЧУ :-) Естественнее было бы, по примеру Питера, дать таблицы прошлих чемпионатов, немного истории и т.д. В конце концов, для юных команд, напечатать легендарные архивные методические материалы УрГУ. Надеюсь, мы к следующему разу исправимся.Здесь тоже есть некое непонимание местных условий. Увы, 5-й и 6-й этажи это и есть ВЕСЬ мат-мех УрГУ. Вопросы :-) ?Вот здесь я не просто не понял сути вопроса. Лекции ведь не были обязательными! Организаторы придумали такую опциональную фишку. Участник точно также был волен никуда не ходить! Например, в Перми народ между турами возили на очень интересные экскурсии в Белогорье и т.д., но я лично никогда на них не ездил - считал, что это помешает правильно настроиться на второй тур. Университет в самом центре - не хочешь сидеть на лекциях - вперед, на знакомство с достопримечательностями (которых, как было замечено, действительно почти что и нет). Мы бы всегда с радостью рассказали, что где есть интересненького.Есть точка зрения, что это неправильно. Может, эта какая-то разница в жизненных взглядах и настроениях... Может, у нас какой-то особенно демократический ВУЗ? Но ходить под конвоем в туалет... увольте! Приехали сильнейшие команды Урала соревноваться, оскорблять их недоверием? Кто им что может подсказать - они и так сильнейшие! Насколько помню, на финале не было никакого контроля вообще (правда, в этом году в Праге, говорят, было построже).
Объясните, почему же контестантам нельзя свободно ходить внутри аудитории, да и где угодно?Конечно, собирались исходно печатать три. Ксерокс сломался. Бывает. Уж простите.И правда. Поскольку в каждом туре 8 задач решалось задолго до конца, вопрос не спорный, а очень спорный :-)Есть такой мощный механизм, как вопросы. Если задача обрастает плюсиками с первой попытки, а вы не можете понять условие - спросите. Говорят, помогает.Несогласен принципиально! Почему это - читерские? Задача решена, если решение команды проходит все тесты жюри в отведенное время... Гарантировать единственность решения, как правило, невозможно... А многие задачи и не были рассчитаны на единственность. Пример - "Classmates" или "Логарифм". В первом случае нам хотелось получить от участников какой-нибудь перебор, во втором - какое-нибудь силовое пробивание. И мы получили.Вот здесь, молодой человек, имеет место ситуация, когда лучше сначала подумать, а потом сказать. Или воспользоваться кнопочкой "Предварительный просмотр", перед тем как отправлять сообщение. Полуфинал даст представление о том, что лучше окажется физически и психологически готов играть на питерских задачах в ноябре 2004 года. ЧУ показал, что оказался лучше готов играть на свердловских задачах в апреле 2004 года. Ссылка на авторитет ПГУ кажется тем более неуместной (и вообще, попытка сослаться: раз они так хорошо сыграли в финале, то здесь должны всех выносить одной левой? почему, собственно? мы не отрицаем, что у нас несколько иной стиль задач, да и несколько иной турнир - два тура, все-таки), потому что не только команда УрГУ-2, но и команда УГАТУ-1 смотрелась явно лучше, чем команда ПГУ-1! Уфимцы с треском выиграли второй тур, когда только усталость на финише, видимо, помешала им хоть ненадолго за последние полтора часа (!) отвлечься от столь увлекательного занятия, как пробивание Логарифма и толком прочитать и сдать "Табло в лифте". Команда ПГУ же сыграв в одну силу с УрГУ-2 на втором туре (но обе эти команды явно далеко позади УГАТУ), с треском провалила первый, причем за счет неправильной стратегии: какого черта при шести сданных задачах надо было до конца контеста упиратьсярогом в заведомый гроб - "Тарелки"?.

Впрочем, родные стены, конечно, помогают. Так, тот факт, что задача "Архиватор" была дана и на олимпиаду ДММ, помог командам УрГУ (которые в среду до поздней ночи писали архиватор для этой олимпиады, что само по себе не способствует хорошей игре во втором туре!) быстрее сдать задачу на преобразование Барроуза-Уиллера. Но ее все лидеры быстро сдали. А в остальном просто, может быть, сказался настрой - надоело проигрывать, а тут еще и на родном факультете.Церемония награжения выглядела многократ церемоннее, нежели на все ЧУ, на которых я присутствовал как участник. Правда, в Челябинске не был, сравнить не могу. "Сделать призы подороже" - сделай :-). Это, и правда, разговор в пользу бедных. Уж какие есть. Большая часть призового фонда - это не просто спонсорская помощь "СКБ Контур". а именно деньги лаборатории Интернет-технологий "СКБ Контур", которую возглавляет ваш покорный слуга. Сами призы были невелики, но достаточно большую часть бремени орграсходов мы на себя взяли. Ну а главный приз здесь - путевка в Питер.В общем и целом - спасибо, вполне конструктивно (кроме п.6, за который, по моему скромному разумению, надлежало бы извиниться). Думаю, в следующий раз окажется не хуже. И в чем-то лучше. Хотелось бы выслушать еще мнения участников, разных и побольше!

Дмитрий, большое спасибо за подробный ответ! Это как раз то, что нам очень нужно, но стеснялись спросить. Кстати, почему остальные участникки не комментируют? На то и форум!Странно, бумажки со стрелочками, словом регистрация, номером 640 и логотипом ЧУ, были на КАЖДОЙ развилке и ВСЕХ поворотах лестницы (пять штук). Через два дня после контеста лично я снял таких бумажек восемь, почему участники их не видели?Не подумали, т.к. не были в Челябинске :oops: Исправимся.На разборе пробного тура всем желающим выдавался лист с описанием достопримечательностей Екатеринбурга. У нас интересных мест очень много, слишком много для трех дней, но вот что может заинтересовать программистов? Мы не знаем, написали что-то, кто хотел - тот ходил по городу, кто не захотел - пошли на лекции. Спорить тут не о чем.да мы и в этот раз хотели с двух сторон :) Потом подумали, ладно уж, потратимся.Пять лет назад это было много. Сейчас это норма (см. финал и полуфинал). А еще мы очень боялись, что ПГУ и ИжГТУ все решат и уйдут раньше срока. И первые три часа каждого тура мы все еще этого боялись. А во втором туре поняли, что надо было еще и УГАТУ бояться.

По поводу задачи Архиватор - на олимпиаду к ДММ эта задача была оглашена в тот же момент, что и выдан комплект участникам ЧУ. Так что претензии неуместны. Стратегическая ошибка команды ПГУ в первый день, повлекшая отставание на две задачи, очевидна. Конечно, хотелось бы услышать комментарии от пермяков. Может, пермским студентам воспитание не позволяет высказывать свое мнение? Пусть хоть тренеры скажут.
А вот с преобразованием burrows-wheeler это и правда прокол, причем неожиданный и для нас (про олимпиаду ДММ и использование при архивировании вспомнили слишком поздно). Хотя помогло ли это кому-то? Вряд ли.

А что, какой-то из первых семи был лучше? Какой и почему?

Ну уж извините, "воспомнили"... Сэмпл к задаче - и тот был позаимствован из статьи про BTW.читая отзыв Дена о первом туре, можно догадаться, что помогло. впрочем, лично я не возражаю против их победы :lol:

Мы поняли условие точно так же как и Dmitry Kovalioff. Придумали эвристику, Sumbit - WA6. Лишь в конце тура до нас дошло, что нужно просто разбить граф на пары ребер.
И что спрашивать, если условие понято однозначно? Это явная ошибка составителей.Тоже несогласен. Задачу нужно решить, и неважно какими алгоритмами, лишь бы проходили. Если подходящих алгоритмов решения несколько, то логичнее выбрать самый легко реализуемый.
Не вижу тут недостатков задач. Наоборот они, помогают анализировать алгоритмы.

Подозреваю, что Dmitry Kovalioff имел ввиду несколько иные "алгоритмы", которые проходили у жюри. Например, что-нибудь такое:

if (номер_теста==1) write("YES");

 else if (номер_теста==2) write("NO"); 

 else итд

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

Есть предложение свои мысли выражать яснее и подписываться под ними.

Рассмотрим версию Ковалева про задачу "Graph decomposition" подробнее. По его мнению надо просто перечислить все пары смежных ребер в графе, и проверить, будет ли это описывать граф. Если к вершине подходят два и более ребра, то набор всех пар "её" ребер опишет все смежные ей вершины. Если одно ребро, то надо смотреть на смежную с ней вершину - есть ли к ней другое ребро или нет. Если есть, то есть пара, в которую входит первая вершина, значит, смежность первой вершины тоже описывается. Когад у единственной соседки нет других соседок, пар нет. Значит, если в графе нет изолированных вершин и одиноких ребер (ребро, соединяющее две вершины, которые больше ни с кем не связаны), то граф можно представить в виде списка всех пар смежных ребер, иначе - нельзя.

Входные данные таковы, что узнать наличие изолированных вершин невозможно (описываются только ребра). Значит, требуется просто проверить наличие одиноких ребер, если есть - ответ "NO", нет одиноких ребер - ответ "YES". Смешная задача, но, предположим, что именно такую решали Ковалев и Мелентьев (как будто это они не посмотрели на название - graph decomposition). Тогда на тесте 3 (два несвязанных треугольника) был бы ответ "YES", то есть WA. Следовательно, либо одно из утверждений "мы поняли также как Ковалев" и "мы получили wa6", неверно, либо неправильно понятая задача на самом деле не была решена даже с точки зрения их понимания.

Да. У нас было именно такое решение. И на 2х несвязных треуголькихах мы проверяли - 1. Откуда информация о 3ем тесте?
Потом мы придумали контрпример: берем треугольник
1-2 2-3 3-1. Обозначим ребра e1,e2,e3.
Записываем его множеством всех смежных ребер:
e1 e2, e1 e3, e2 e1, e2 e3, e3 e1, e3 e2.
Это множество задает не только этот треугольник, но и такой граф:
1-2 1-3 1-4. ребра e1, e2, e3. Так что это представление неоднозначно.
Вообще в таком понимании задачи много противоречий. Надо было нам задать вопрос.
Да, и зачем нам смотреть на название задачи? В тексте должно быть ясное и однозначное условие, понятное и без названия задачи.

Откуда взялась вершина 4? Не вижу ее во входе "1-2 2-3 3-1" :)
Да и контрпример странный, нужно четное число ребер :)Вот ключевой момент. Если всплывает слово "неоднозначно"- тут же надо писать вопрос.
Кстати, как вы перевели строку из условия

я решал именно так. и получил WA #6 (на тимусе).

з.ы. на двух изолированных треугольниках мой алгоритм отвечает "1".

Нет никаких треугольников в третьем тесте, а есть именно в шестом.

Общие комментарии по теме я дам через пару дней, когда выскажутся все желающие, сейчас же просто хочу внести разъяснения по задаче "D" 2-ого тура в моём понимании её условия.

Задача получается не такая смешная, как думает Станислав Васильев - его решение неправильное.

Итак, как решал я:

Если в графе есть компонента связности, которую невозможно описать однозначно списком всех смежных пар её рёбер - выводим 0, иначе выводим 1. Под это дело в процессе контеста была собственноручно разработана теория обратных графов (у которых вершины с рёбрами поменялись местами).

Примеры компонент связности, которые не задаются списком пар своих смежных рёбер однозначно (задаю их списком рёбер):
1. (1-2) - изолированное ребро
2. (1-2),(2,3),(3-1) и (1-2),(1-3),(1-4) - взаимно симметричные представления звезды и треугольника
3. Кажется, больше ничего такого нет, хотя я и не проверял.А почему нет? Если у тебя на входе граф задан парами смежных рёбер (e1-e2),(e2-e3),(e3-e1), то четвёртая вершина вполне может появиться - откуда тебе знать, была она или нет?

Написав всё это, я получил WA на 18 (восемнадцатом) тесте! Можно ли было предположить, что программа, решающая принципиально не ту задачу, пробила 17 тестов? В итоге я справедливо решил, что моё понимание условия является правильным - и вопросов жюри, конечно задавать не стал.

Короче говоря, получилась интересная задача - намного интереснее оригинальной. Как исследователю задач, мне было бы интересно узнать её решение.

Судя по практике нашей команды, WA на тесте с большим номером означает, что у нас принципиально неправильный алгоритм! Подтверждалось много раз, самый яркий пример был, когда играли NEERC-2003, одна из утешительных задачек у нас валилась на 44-м тесте. Уже после контеста мы поняли, что наш алгоритм был принципиально неправильным - задачу надо было с нуля переделывать. Здесь, получив именно WA (а не TLE и PE) на 18 тесте, мы бы сразу поняли, что что-то принципиально не так делаем.

Хотя, конечно, я согласен с Дмитрием, что условия должны быть яснее, и такого недопонимания, как случилось здесь, не должно было случаться.

Ещё в качестве претензий к организации:
1) на сайте у всех страниц одинаковый заголовок - неудобно; в выложенных правилах оставалось слово "защитывается", несмотря на замечание в гостевухе. Смотрел 10 числа, может за 2 недели уже и исправили, но всё равно неудобно перед теми, кто заметил.
2) на бэджах не было названия мероприятия - только бегущий человечек. Вот посмотрит на него участник через год, и уже не вспомнит, с какого тот соревнования. (в скобках: бэджи печатал я, но Ответственное Лицо у меня их приняло, не заметив отсутствия названия!)
3) ну и хаотическая, несогласованная деятельность "лиц в жёлтых бэджах" - по-моему, не хватало управления (т.е. одного Ответственного Лица на человек тридцать поддержки оказалось мало). Вполне может быть, что в одних аудиториях не давали открывать Фар, а в других позволяли участникам гулять взад-вперёд - указаний "что допустимо, а что нет" вроде бы вовсе не было, и каждый сам решал, что позволять участникам, а что нет.

Дизайн бэджей сам по себе нормальный. Плохо, что на них не написано название соревнования, но их главная функция - опознавательная, а не памятная. (И вообще хорошо было бы значки сделать) Тогда важно было отличать участников, студентов, тренеров, оргкомитет и жюри. Представляю, что было бы, если бэджей не было бы. :lol: Скорее даже важнее был цвет бумажки.

Второе: принципиально что ли, разрешали открывать Фар или нет? Это, я думаю, не спасло тех, кому разрешали. В пятичасовом соревновании 2 минуты использования Фара, если задач все равно не знаешь, мало на что влияют. Это по тому же поводу, что и ходить под конвоем в туалет. Такое недоверие не повышает уровень соревнования, а понижает. Слава богу, такого не было.

Третье: работа оргкомитета была сносной, если учесть, что основную массу техподдержки составляли люди, которые про такие соревнования никогда не слышали. И ответственное лицо - из их числа. Надзирателям приходилось 3 раза повторять ничего не значащую для них фразу "в списке сабмита нет задачи такой-то. Сообщите жюри.", после чего они звали кого-нибудь с красной бумажкой, чтоб ты повторял ему это в четвертый раз. Лучше бы техподдержу составили те, кто участвовал(-ует, но на Урал не прошел). Во всяком случае, когда я за школьниками приглядываю на контестах, это лучше, чем левый бы человек приглядывал.

:oops: :oops: :oops:

1.    Почти все люди которые учавствуют в олимпиадах на матмехе или были участниками или были в жюри. Поэтому за нами следили те кого смог привлечь 1(!) человек.

2.    Человек, который делал сайт(acm.usu.ru) изначально о дизайне и не думал, он сделал хорошую рабочую его версию в серых тонах. Подчеркиваю: хорошую и рабочую. Посмотрев на него(поучавствовав в тестировании) я решил, что дизайн надо подправить, причём не перегрузить сайт флэшками, графикой и остальной не особо важной ерундой(да и времени на это не было), и использовать то, что уже есть. Нарисовал, вроде симпатично. Послал вроде как пре-релиз. Он был реализован почти как есть(правда некоторых задуманых вкусностей так и не появилось). Времени не хватило вылизать, хотя изменилось бы не так уж и много.
(Потом делали аналогичный дизайн для HTML монитора, придумали игру...) Не так уж и плохо, будет лучше...

3.    Во время подготовки у жюри было ещё несколько интересных задумок(каких не скажу), всё могло быть просто супер, но на их реализацию потребовались бы немалые суммы. Опять же хочется думать, что ещё получится.

          P.S. Соберусь с мыслями напишу ещё кое-что.
                 И сделайте пожалуйста рекламу форума, Обратная связь очень важна(где вы, 42 команды????)

По моим прикидкам, знали об АСМ и были в оргкомитете 4-6 человек, остальные либо участвовали, либо сидели дома. В основном, конечно, в оргкомитете были совершенно левые люди. Дело даже не в том, позволяли они открывать Фар или нет, выпускали они в туалет под конвоем или без - в том, что никто из них никакогоинструктажа "а что, собственно, делать" не получал. Отсюда и несогласованность, о которой я заметил. Фар лишь пример.Что за игра?

Мы поняли условие точно так же как и Dmitry Kovalioff. Придумали эвристику, Sumbit - WA6.Наша команда решала это задачу также (у двух участников 10 лет обучения в специализированной аглийской гимназии), так как условие _некорретное_, по нему получается, что надо именно искать изолированные ребра.