Всем привет. Лето потихоньку заканчивается и я решил, что сейчас самое время транслировать очередную Зимнюю олимпиаду. Немного поздновато, но сойдет.
Время и место олимпиады
Пробный тур: 10 августа в 19:00. Продолжительность: 24 часа.
Основной тур: 11 августа в 19:00. Продолжительность: 3 часа.
После основного тура будет запущен виртуальный турнир той же длительности.
Оба тура проводятся тут: http://freopen.org/.
Если будут проблемы с DNS, можно напрямую: http://37.139.21.227/. Напишите мне в личку, если будут проблемы с DNS (freopen).
Правила олимпиады
- Языки олимпиады: С/С++ (gcc), Java7 (openjdk), Python (2.7.3, 3.2.3), Pascal (Free Pascal 2.4.4-3.1)
- На олимпиаде будет предложено несколько задач.
- По каждой можно получить максимум 100 баллов.
- В каждой задаче своя система оценки. Система оценки каждой задачи указана в условии.
- Лишние отправки не могут негативно влиять на итоговый балл по задаче.
- Действия других участников могут влиять на балл по задаче. Таким образом, количество баллов участника может меняться в течение контеста даже если участник не предпринимает действий.
- Проверка решения происходит сразу после отправки.
Сложность олимпиады
На Зимнюю олимпиаду приезжают школьники, уровень которых заранее неизвестен. Поэтому я стараюсь сделать олимпиаду так, чтобы даже совсем неопытные участники смогли получить удовольствие, но при этом и более сильным участникам не было скучно.
На этой олимпиаде даже только начавшие программировать школьники, которые знают лишь основы своего языка программирования, смогут набрать какие-то баллы в каждой задаче. В частности, в одной задаче можно набрать баллы не умея программировать ВООБЩЕ (правда, достаточно маленькие). Но при этом лично мне неизвестно полное решение этой задачи.
Итого. Олимпиада рекомендуется для новичков и участников второго дивизиона Codeforces. Более сильные участники найдут, над чем подумать, получить близкие к 100 баллы по каждой задаче довольно непросто даже для фиолетовых и оранжевых участников (как мне кажется).
Краткая инструкция по регистрации
После того, как вы зарегистрируетесь и залогинитесь появится вот такая форма:
В ней надо нажать на кнопку [Edit] и в полученное поле ввести свое имя:
Затем надо нажать save и потом [Confirm registration]
Наконец, надо нажать Participate.
В основной тур можно попасть по тому же пользователю и паролю. В случае трудностей пишите мне: freopen.
Напоследок
Я не знаю, насколько система стабильна. Все может упасть в любой момент, так что я заранее извиняюсь, если все сломается. Пожалуйста, не ломайте мою систему специально.
Комментарии:
В задаче Б пробного тура некорректные тесты. В условии числа в одной строке, а в тестах в разных.
В условии ни слова про то, что числа в одной строке. Сейчас поправлю тесты, чтобы не возникало проблем.
Хорошо, в тестах из условия.
Проблемы с Java:
"javac" -source 1.7 -Xlint:unchecked SimpleSolution.java
Error occurred during initialization of VM
Could not reserve enough space for object heap
Error: Could not create the Java Virtual Machine.
Error: A fatal exception has occurred. Program will exit.
Есть такое. Памяти для компиляции не хватает. Сейчас ненадолго положу сервер, чтобы добавить памяти, потом должно заработать.
Вроде бы работает теперь.
Да, спасибо.
Снимать до 50 из 300 баллов за более поздний посыл на задачу А достойно апплодисментов.
Прошу прощения, олимпиада была расчитана на немного более позднюю первую сдачу. На самом туре до первой сдачи прошло минут 20, поэтому было не так заметно. Пока думаю, надо ли смягчить кривую.
UPD. Было бы любопытно мнение сообщества по этому поводу.
Да, когда сдавший на начале 5й минуты участник получает за задачу 84 балла из 100, то это не круто.
Может, пусть снижается линейно до 50 до конца контеста?
Как раз таки она сейчас линейно снидается до конца контеста до 50.Ха, наврал, извиняюсь.
Oh..
На 16й минуте — 59 баллов — не совсем линейно.
Но менять уже действительно лучше не надо ничего.
Нет, не линейно, а довольно круто. Через час уже 52 балла.
совсем-таки не линейно, а гиперболически
Давайте я сделаю альтернативную табличку просто чтобы посмотеть, что будет.
UPD. http://freopen.org/cgi-bin/table2.py
Ну а сейчас она перестала выполнять свою функцию, у абсолютного большинства участников 96-99 баллов за нее, разве что qwerty пострадал сильно (но в условии описана система оценки, поэтому понятно, что ее надо сдавать быстро). Я согласен с тем, что кривую стоит смягчить, но не настолько.
Возможно я что — то не понял, но в условии третьей задачи написано: вам заранее выданы 10 тестов Куда выданы? Или что тут имеется в виду
Лежат на http://freopen.org/
Извините, вопрос снят, прочитал клар
Спасибо большое за контест, рад, что поучавствовал.
Жаль то, что получилось с задачей A. Уж ОЧЕНЬ много от неё зависело. Да и я, например, сдал правильное решение только чтобы что-то сдать, а потом подумать(В итоге сдал вторым). По поводу "нужно ли менять шкалу?": Не понятно. С одной стороны, ясно, что результаты станут менее рандомными, с другой — это не вполне честно к первому сдавшему.
qwerty787788, Сколько у тебя пройденных тестов в С? Как решал?
Я решил С так. Понятно, как достичь того, чтобы осталось максимум min(n, m) черных клеток — идем по, скажем, рядам с первого и до предпоследнего и делаем так, чтобы в текущем ряду не было черных клеток, переключая клетки следующего ряда. А теперь пройдем точно так же, только начиная с последнего ряда и до второго. А потом опять в обратную сторону, и. т. д. Еще перед каждой итерацией случайно изменим какие-нибудь клетки. Ну и выберем наилучший результат по всем итерациям.
И еще, чтобы ответ не был слишком большим, если какую-то клетку перекрасили два раза, то не будем ее перекрашивать.
На тестах после этого остается 0, 0, 0, 0, 0, 2, 1, 3, 32, 75 черных клеток.
В 6, 7, 8 можно просто перебрать покраску и найти решение с 0 черных клеток. Лично я не умею делать лучше.
Я лично сильно затупил с тем, что не начал решать с задачи А, хотя, когда взялся за нее, написал минут за 5 перебор и получил АС, но все равно контест понравился, спасибо!
Про задачу A: На основном туре я долго сомневался, давать задачу или нет. В конце концов я заранее в правилах отметил отсутствие штрафа за лишние посылки и вывел актуальные результаты на проектор перед всеми участниками. Мне показалось интересным дать задачу на интуицию в таких условиях. На туре задача отыграла себя прекрасно, первая сдача была минут через 20, почти все уложились в 40 минут по этой задаче, в итоге задача слегка развела тех, кто был близко по баллом в других двух задачах и больше ничего не сделала. Еще мы, кажется, вручили спецприз участнику, решившему эту задачу первым, т.к. он из-за глупой ошибки проиграл первое место.
На трансляции я думал о том, что будет сдача через 3 минуты и баллы будут очень быстро сыпаться. После некоторых сомнений я решил провести трансляцию один в один также, как она была проведена в оригинале.
Я согласен с тем, что это целиком и полностью мой косяк, мне следовало переделать кривую так, чтобы на 20 минуте было баллов 75-80, а на 40 — 65-70. Но теперь, как мне кажется, будет неправильным что-то менять. В следующий раз постараюсь быть внимательнее при проведении трансляции. Еще раз прошу прощения у всех пострадавших. Надеюсь, вы все-же смогли получить удовольствие от решения моих задачек.
Несколько слов про задачки и решения.
Задача A: Достаточно очевидное решение замостить слева-направо сверху-вниз расположив прямоугольник вертикально. Тогда ответом будет min(n,m). Этот ответ верен по крайней мере для ограничений, указанных в условии и еще немножко больших (проверено перебором). Предполагалось, что участники воспользуются отсутствием штрафа и проверят найденную гипотезу, а немного отставшие поймут, что задача не очень сложная по таблице результатов. Полного доказательства этого факта у меня нет. Более менее понятно, что если прямоугольник n*m можно решить меньше, чем за min(n,m), то и квадрат min(n,m)*min(n,m) тоже можно решить, для этого надо взять решение прямоугольника, вырезать из него любой квадрат и заменить каждое число на его порядковый номер среди всех чисел квадрата. Что делать дальше -- лично мне непонятно, быть может, кто-то знает.
Задача B: Эта задача была добавлена из соображения большого количества простых частных случаев. Предполагалось, что неопытные участники будут развлекаться пытаясь написать по отдельности несколько очень простых случаев. Первые 7 случаев решаются просто аккуратной реализацией. Кроме того надо не забыть про mod 10 для последовательности из условия. Случай 8 решается с помощью любой структуры, позволяющей исказть сумму на отрезке, либо наблюдении о том, что перейти к следующей сумме можно вычтя из предыдущей число, которое вышло из диапазона и добавив последнее сгенерированное. Случай 9 решается наблюдением, что последовательность циклична и длина цикла не превышает возможное количество наборов из последних n чисел. Требуется найти цикл и пропустить его нужное число раз. Случай 10 решается с помощью перемножения матриц. Строится матрица преобразования на один шаг и возводится в нужную степень, затем применяется к исходному объекту.
Задача C: Достаточно забавная задача. Давно хотел дать что-то подобное и посмотреть, придумает ли кто-нибудь что-то забавное. Из того, что я знаю про эту задачу. Очевидно, что порядок действий не важен и в каждую клетку надо либо сходить один раз, либо 0. Пусть мы ищем полное решение. Пусть мы знаем, в какие клетки первого ряда ходить надо. Тогда во втором ряду надо ходить так, чтобы первый ряд стал пустым, очевидно, это можно сделать единственным образом. И так далее. Итого мы очистим все поле кроме, возможно, последнего ряда. Перебирая положение на первом ряду можно набрать довольно много баллов.
Забавный факт про задачу C: Понятно, что существует 2^(n*m) возможных покрасок прямоугольника и ровно столько же способов его перекрасить (т.к. каждую клетку трогаем, или нет). Логично было бы предположить, что из любой покраски можно сделать любую правильным преобразованием. Однако, это не так и для некоторых размеров существуют нетривиальные перекраски, сохраняющие исходный рисунок.
не зря поучаствовал, хоть две из трех задачи и довольно известные, интересно было порешать С. правда, слишком все зависело от А, в то время как по С баллы выбивались еле-еле, и т.е. затупив вначале, уже сложно было что-то исправить, было бы неплохо, если бы в следующий раз убывание стоимости было как-то более мягкое.
и еще, вначале (почти весь контест, не считая минут 20 последних), выходило из системы. буквально минуты 3 висело и выходило
Весёлый контест, мне понравилось!
Спасибо за контест!
и еще, автор, отличная идея засчитывать группу в задаче В, если она когда-то была пройдена, не надо возиться с рассмотрением групп в программе!
Fun fact: на этом IOI у одного из участников из Латвии так и было, что 2 разных submission брали разные сабтаски, а с учётом отсутствия feedback, объединить их не было шанса. Так что мне эта идея тоже уже с IOI нравится.
Так и было, нет? У меня на эту задачу просто три разных решения — для 1-7, 8, 9-10. Переменную t я вообще не считывал.
Это меня похвалили так :)
Аа, хорошо тогда) Присоединяюсь к похвалам)