Добрый вечер сообщество 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 тура олимпиады, который состоится в следующее воскресенье.
Я бы с интересом почитал и подумал бы над задачками, если бы не этот блевотный файлообменник, с которого я с планшетом ничего не могу скачать :-(
зайдите на сайт самой олимпиады. там все есть но надо чуть чуть поискать. но зато он работает с планшета.
Ага, вижу. Линк на архив со всеми данными и заданиями по-украински.
украинский не сложный. я уверен что вы кое как вникнете в условия. будут вопросы обращайтесь переведу.
Да не, во всё спокойно можно вникнуть. У нас на национальных сборах был развлекательный контест, в котором все задачи были на разных языках — английский — халява, польский — легко, латышский — посложнее, а какую-то неведомую дребедень получилось разобрать только по сэмплу :-) Как-то справились.
В этом году я никакого отношения к подготовке задач не имел, но все же выскажу свое мнение.
По поводу второй задачи: на самом деле основной сложностью там является не теорема Пойа (там и лемму Бернсайда достаточно знать), а нахождение всех симметрий многогранника, а также всех поворотов, переводящих его в себя же. Мне кажется, даже на АСМ олимпиаде такое вряд ли бы много команд стало писать. Хотя и сама лемма Бернсайда — не школьный материал.
С третьей задачей не все так однозначно. Я и сам не сторонник зажатых ТЛ-ов, но зато это хоть как-то подготовит участникам к Всеукраинской олимпиаде. Там так сложилось исторически, что ТЛ всегда зажимается достаточно сильно и нужно уметь писать оптимальный код, чтобы набрать 100 баллов. И я не согласен с тем, что разбалловка в третьей задаче плохая. Именно так и надо делать, если уже решили зажимать ТЛ. Чтобы набрать здесь 100 баллов, а не 60 и не 80, нужно понимать несколько вещей.
Во-первых, нужно знать тонкости языка, на котором пишете. Если это Pascal (как в вашем случае), то нужно понимать, например, что на Delphi операции с int64 выполняются долго и лучше сдавать код на FPC, если он активно использует этот тип. Вот здесь можно почитать подробнее. Если язык — C++, то лучше не считывать через cin и не выводить через cout, и уж тем более не выводить перевод строки через endl, когда в задаче такой ТЛ.
Во-вторых, нужно не только знать разные структуры данных и алгоритмы, а и уметь вовремя их применять. Декартово дерево, может и решает более широкий класс задач, но ведь оно имеет достаточно большую скрытую константу и не стоит его совать туда, где достаточно обычного дерева отрезков. Это при том, что в условии написан ТЛ в 0.1 секунды и еще до начала написания ясно, что придется оптимизировать решение. Я думаю, в третьей задаче нормально написанное нерекурсивное дерево отрезков или же дерево Фенвика пройдет на 100 баллов, хотя на 100% не могу быть уверен, т.к. сам ее не писал и не сдавал.
Сколько-сколько там TL? 0.1 секунды? Да они там совсем поехали.
Кстати, фенвик на этой задаче раза в два быстрее работает, чем mergesort. Я это как-то тестил.
0.1 это не хорошо. Особенно если меряется как обычно с точностью до ± 30 мс. 0.2 уже адекватнее.
Вот я например во время тура написал декартово дерево. Я понимал что там большая константа. Засекал время на макс тестах. 109 мс. Я решил что сам процесс замера времени долгий и если на машинах участника 109 мс, то на компьютере жюри должно быть хорошо.(Под хорошо я подразумевал 85-95). И каково же было мое удивление, когда оказалось, что либо компьютеры жюри слабее чем у участников, либо в задаче 40% макс тестов.
Вспоминаются сборы в Швейцарии. Там такие TL были во всех задачах. И ограничения в стиле TC. Зато тестировалось мгновенно.
На Всеукраинских олимпиадах такой ТЛ почти во всех задачах. Я не буду делать никаких заключений по поводу того, насколько это хорошо, но зато, как уже было сказано выше, все тестируется очень быстро.
По поводу знания языка и тонкостей применения алгоритмов я с Вами абсолютно согласен. Например, я, еще не дочитав условие до конца, придумал решение с декарткой. Конечно, сам факт структуры с такой большой константой мне не очень понравился, но, потратив последующие минут 15-20 на то что бы придумать решение с деревом отрезков( а значит и Фенвиком ) я все такие решил написать свою первую идею. Среди причин можно указать то, что это была первая задача которую я писал, а значит хотелось больше времени оставить себе на остальные задачи.Так же Сodeforces, возможно ошибочно, научил меня тому, что решение с оптимальной асимптотикой (почти) всегда проходит по времени. Да, об заморочках с int64 в Delphi я знал, но сей факт напрочь вылетел из головы( несмотря на то что на эти "грабли" я уже однажды наступал ).
Что касается разбаловки, то я не имел ввиду что зажимать решения вообще не надо. Лишь призываю к тому, что бы сделать более существенную разницу между хоть каким-нибудь NlogN и квадратом.
Написал merge sort и решил проверить сколько работает. Максимальное время оказалось 0.024s. Какой-то слабый комп, где проверяли, раз дерево отрезков не зашло.