Добрый вечер сообщество Codeforces!

Прошедший неделю назад 1 тур (13.01.2012) Киевской городской олимпиады школьников по информатике вызвал достаточное количество вопросов, и я, не увидев здесь о нем ни слова, решил высказать свои впечатления и поинтересоваться вашим мнением. Больше информации вы можете прочитать на сайте. Там же лежит порядок проведения, информация по программному обеспечению, результаты, архив работ участников и.т.д.

И так несколько слов касательно организации. Олимпиада проходила по адресу Тимошенко 13б, в помещении Института последипломного образования. фото фото фото

По устоявшимся традициям и регламенту начало в 10 утра. Конечно, предусмотрительные участники начали массово подходить уже к 9.30 и к 9.40 в вестибюле, прямо напротив входа, уже не было где яблоку упасть. Сразу у входа участников встречали приветливые представители оргкомитета с предложением помочь в нахождении своего места и указать на расположение гардероба (что, кстати, встретишь не на всех олимпиадах).

В 9.45 – 9.50 участников начали запускать в их кабинеты (нас запустили ровно в 10), где они (согласно условию проведения ) должны ознакомится с правилами сдачи задач, создать файл contest.txt, за отсутствие которого тестирующая система Kgrader отказывалась тестировать решения участника и он автоматически получал 0 балов за олимпиаду. О чем неоднократно говорили, но каждый год находятся участники, которые не считают нужным прочитать правила.

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

Теперь перейдем к самой интересной и важной части любой олимпиады. И начнем с тестирования задач – собственно человеческой системы тестирования и не было... Жюри олимпиады не меняло этот аспект проведения с незапамятных времен, а точнее (может я ошибаюсь) никогда. Не было не только проверки на полном наборе тестов хоть по всем, хоть по части задач, так еще и адекватного способа проверить свои решения на совместимость с системой тестирования (проверка на тестах из условий). Ну вернее был один, но насколько я помню он достаточно длинный, и состоит в поиске указанной выше системы в папках компьютера, и установке его на компьютер. Хотя в последние годы технические условия сделали чуть лояльнее по отношению к участнику. Например, еще в 2010 отсутствие перевода строки после вывода ответа и/или некорректно заявленный компилятор в первой строчке решения по задаче влекло за собой 0 балов за задачу, в то время как сейчас участник получит половину заслуженных им балов.

В 10.20 раздали задания и в течении последующих 5 часов участники решали предложенные 3 задачи. Перед тем как продолжить чтение, советую прочитать условия, дабы вы могли их прокомментировать и результаты.

Начнем по порядку:

• Clinic
  Задача достаточно легкая и заслужено занимает место самой легкой задачи олимпиады. Ее решение придумали многие участники, но только 3 смогли сдать ее на полный бал.Этот факт можно, наверное, считать как и хорошими тестами жюри, так и недостаточным опытом решения подобных задач участниками.
  Тесты и авторский разбор

• Farben
  У многих участников задача вызвала вопросы во время тура, так как даже самое наивное, простое и не оптимальное решение уже само по себе сложно, особенно как для школьной олимпиады, где участники с трудом сдают первую "халявку".Как следствие большинство балов по этой задаче расположилось в интервале 15-20 балов, которые спокойно могли набираться несколькими аккуратно написанными if (ну или 19 балов моим плохим хэшированием графов :)). Но еще больше негатива эта задача навлекла на себя после появления разбора, как только люди узнали что для ее полного решения надо знать теорему Редфилда — Пойя. Подробнее об этой далеко не школьной теореме, а так же и алгоритме вы можете прочитать здесь(на русском) и здесь(на украинском).
  Ах да, а Вы знаете Редфилда — Пойя ???
  Тесты и авторский разбор

• Inverses
  Первое впечатление от этой задачи после ее прочтения — баян. Но впрочем я промолчу,слушая Ваше мнение по поводу того, имеет ли эта задача право на существование (быть на городской олимпиаде)? Обсуждение этой задачи оставим для комментариев.А сейчас минутка статистики: из 187 участников только 7 написали NlogN (2 десятиклассника и 5 одиннадцатиклассников). А точнее 3 — Merge Sort , 2 — Дерево отрезков , 2 — Декартово дерево.
  Авторское решение подразумевает нечто подобное (для числа 0-инверсий).
  Отметим страние авторов зажать по времени все что только возможно, а также немного не адекватную разбаловку.Тупейший квадрат набирал 40 балов,а в прямых руках с минимумом оптимизаций — 50. Все остальное кроме Меrge Sort сдать на 100 было пожалуй невозможно, лишь на 60 (только аккуратно написанное дерево отрезков на 80). Сей факт есть немного возмутительным, так как между квадратом(пусть и с оптимизациями) и NlogN довольно большая разница.
  Тесты и авторский разбор

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

А в заключение хотелось бы все-таки поздравить победителей:
1. Алексей Кузьмин(vagnard)
2. Радомир Першин(Rad0miR)
3. Василий Антонюк(Antoniuk)
4. Евгений Попович(a00920)
5. Леонид Логвинов(Logvinov_Leon)

P.S. С нетерпением ждем 2 тура олимпиады, который состоится в следующее воскресенье.