Добрый день, дорогие пользователи Codeforces!
2 ноября начался заочный этап X Открытой олимпиады школьников по программированию. В контест добавлен первый пакет из пяти задач, остальные задачи будут добавлены позднее. Те из вас, кто знает что такое Открытая олимпиада (она же "заочка") и её правила, могут не читать дальше и сразу переходить на сайт олимпиады :) Первый пакет задач подготовили для вас: Zlobober, romanandreev, snarknews и GlebsHP.
Те, кто раньше в данной олимпиаде не участвовал, могут так же пойти на сайт и прочитать полную информацию там, а в этом посте будут обозначены лишь основные моменты. Олимпиада состоит из двух этапов: заочного и очного. Заочный этап проходит со 2 ноября по 18 января, и традиционно состоит из 10-15 задач различной сложности, тематики и формата. Мы подбираем задачи таким образом, чтобы они были интересны как совсем новичкам, так и "зубрам" олимпиадной информатики. Лучшие n участников (n приблизительно равно 400) будут приглашены на очный этап олимпиады.
Очный этап пройдёт в Москве, ориентировочные даты проведения — 7-8 марта. Площадка проведения — учебный центр нашего генерального спонсора 1С на м. Тимирязевская. Также, благодаря нашему спонсору, участникам оплачивается проживание в гостинице на время проведения олимпиады. Очный этап состоит из двух туров, уровень участников немного превосходит уровень Всероссийской олимпиады по информатике за счёт приезда сильных школьников из ближнего зарубежья. Возможно это прозвучит слишком пафосно, но на наш вкус качество задач олимпиады в последние годы превосходит Всероссийскую олимпиаду и сравнимо с IOI. Олимпиада имеет первый уровень и даёт соответствующие льготы при поступлении.
Призеры заочного этапа олимпиады никаких льгот не имеют — поступить, не выходя из дома, всё-таки не получится.
Для тех, кто не является школьником и хочет просто порешать задачи, доступно внеконкурсное участие.
Жюри олимпиады призывает всех участников действовать честно, не обсуждать друг с другом решения задач и не делиться написанным кодом. Особенно хотим отметить, что любое обсуждение задач запрещено, в частности, и в комментариях на Codeforces (в том числе, и к этому посту). Все интересующие вас вопросы по задачам вы можете и должны задавать через тестирующую систему. К сожалению, каждый год некоторые участники заочного этапа не допускаются к участию в очном этапе из-за выявления случаев списывания с их участием.
Любые оставшиеся вопросы смело задавайте в комментариях.
UPD: в контест добавлены четыре новые задачи: F, G, H и I. Для вас их подготовили: thefacetakt, Sender, haku и ipavlov.
UPD2: в контест добавлены последние три задачи: J, K и L. За подготовку задач мы благодарим: romanandreev, Vaness и mingaleg.
UPD3: на сайте олимпиады доступны предварительные результаты и архив олимпиады. Рады сообщить, что Zlobober подготовил для вас разбор задач заочного этапа.
Как сдавать решения?
Ссылка на ejudge
Качество задач... Это вы про задачи, в которых заходил рандом на две строчки?
Фраза "заходил" подразумевает, что там были слабые тесты и решение случайно их проходило. В задаче, о которой вы говорите, это решение можно доказать, что и было сказано на разборе.
А будет подключаться еще несколько машин для тестирования?
Просто когда добавится еще задач + останется эта "времяпожирающая" D, ждать результатов тестирования станет совсем невозможно.
Иногда наблюдается рост очереди посылок, но конкретно сейчас всё нормально. Задача D в принципе долго тестируется, одна посылка проверяется по 3-4 минуты.
В целом, я считаю, что на заочном (и только на заочном) туре время ожидания вердикта меньше 5 минут вообще не является некомфортным, а ниже 10 минут не является раздражающим.
Также могу предложить вам тестировать локально перед отправкой :)
Почему бы не ввести в D ограничение на проверку тестов последней группы? К примеру, осуществлять проверку только при полном прохождении первых четырёх групп. Или хотя бы просто 4 группы, в этом случае всё более явно.
Особо сильно системе это, вероятно, и не поможет, но всё чуть легче будет.
На это есть причина, но она будет озвучена только в разборе.
clock() убивает ejudge?
Работаем над этим.
На ЧФ, кстати, так же было.
Не, на чф вроде все check failed были из-за плохой сетки.
там security violation был
С clock() что-то порешали? Сейчас отправляю с clock() и пишет
Превышено реальное время работы >2.000. Реальное время — это же астрономическое? Причем если отправить без clock(), то часть из этих тестов будет успешно пройдена.Run id: 6102
Методом тыка выяснил, что сейчас clock() всегда возвращает -1.
Как перестать посылать D и начать жить, когда впереди тебя множество посылок ОПТИМИЗИРОВАНЕЕЕ?
Авторское решение укладывается в ТЛ с двукратным запасом и содержит только широко известные и используемые оптимизации. Возможно, в вашем решении просто не хватает каких-нибудь идей.
Почему система так долго оценивает решение участников ??
Сам использую das keyboard (правда, не ultimate), поэтому от истории в D я поржал — спасибо. А вот с шенгеном немного прогадали — в реальности всё немножко по-другому устроено.
Почините ссылки на информацию об участниках :)
Какие именно ссылки вы имеете в виду?
Из таблички результатов. На страницу с полной информацией об участниках. Вроде этой
P.S.: Изначально она пересылает на другую страницу, а сюда можно попасть только ручками вбив свой id.
Исправлено. Спасибо за помощь)
Было бы замечательно иметь возможность смотреть табличку только среди школьников, а то внеконкурсные дядечки совсем уж самооценку понижают:(
Не так уж их там и много. На момент написания комментария, всего 33 из 540 участников — вне конкурса.
Не обращайте внимания на этот комментарий, сейчас всё работает как надо :)
Вот интересно, почему большинство сдает задачу D примерно с 50 попитки?
Хотелось бы ответить, но это может стать подсказкой... Но могу сказать одно: на это есть серьезные причины, учитывая ограничения в группах (Особенно в последней)
http://www.olympiads.ru/zaoch/ — ссылка недоступна(
Я зарегистрировался, но нигде не вижу кнопочку "Сдать задачу" или тому подобное.... Кто может объяснить подробно как все таки сдавать задачи?
Ну, там две ссылки — одна на персональную страницу, другая на ejudge. подозреваю, что вы находитесь на своей персональной странице. Зайдите на http://www.olympiads.ru/zaoch/, там "регистрация на олимпиаду". Вводите свой логин и пароль и заходите в ejudge. Там жмете инфо, выбираете задачу (A, B, C, D, или E) выбираете компилятор, файл и тыкаете "отправить". Все
Напишите, пожалуйста, приблизительные даты выхода новых пакетов задач. Спасибо.
Конец ноября и середина декабря.
скоро уже 2/3 декабря
По каким критериям сортируется таблица результатов при равном количестве баллов?
Это не имеет значения, для участия в очном туре будут приглашены все набравшие >= x баллов.
Можно ли быть уверенным, что на Java рекурсия в 3,000,000 возможных вызовов (не скажу в какой задаче) не кинет Stack Overflow, а работа с двумерным массивом такого же размера не кинет за пределы Time Limit?
Другими словами, есть ли авторские решения задач как на Java, как и на С++? Иначе придется пересылать кое-что :)
Согласно правилам олимпиады, жюри не гарантирует возможность решить все задачи с использованием языков отличных от C и C++. Тем не менее вы говорите про задачу, для которой решение на Java у жюри есть. Вопрос про размер стека я сейчас уточню.
А будут дисквалифицировать за использование кода с открытых источников, как e-maxx.ru?
Где же ответ?
Будут ли авторские разборы задач? Я не нашел разборов задач прошлых лет...
Мы постараемся подготовить разбор задач заочного этапа после его окончания.
Будут ли еще задачи? Если да, то когда?
Будут, в самое ближайшее время.
есть вопрос по интерактивной задаче: вердикт на один из тестов Превышено максимальное время работы. Это может означать что я просто превысил количество запросов? или именно задача не прошла по времени?
Почему посылка по задаче D проверяется >10 мин или это нормально
Это нормально, у всех так
UPD. В контест добавлены задачи J, K, L.
Получил такую картинку:
Как я вижу себя: 
Почему у многих участников по последней задаче 100 баллов, хотя задача — полностью оффлайн?
Исправлено.
А есть способ скачать ранее отправленное решение?
Нету, тоже искал) Жаль что нету этой функции
Нельзя. Вероятно, во избежание возможного взлома аккаунта и кражи решений. Теперь злоумышленник может разве что отослать по всем задачам код "int main() { return 0; }" за полчаса до дедлайна :)))
В FAQ примерно это и написано.
Ouch. И еще берется last-submit. У меня по D было 81, написал новое решение — 30. Старый код потерян, как и мой 51 балл. :D
Я во избежание такой оплошности настроил гит и коммичу туда каждое улучшение.
Чего и советую сделать остальным ^^
Почему в задаче L тесты проходят вердикт (OK) а баллы 0 ? Заранее спасибо за ваш ответ.
Читайте систему оценки в условии задачи
Технический вопрос по интерактивной задаче J(просто первый раз решаю такую задачу)... В условии сказано, что после вывода ответа на задачу программа должна завершиться... а что надо сделать чтобы она завершилась, а не ждала нажатия на какую нибудь клавишу?
Достаточно вывести ответ и вернуть ноль.
не понимаю опять ТЛ
Попробуйте отослать без ввода / вывода в файлы
В интерактивных задачах так и надо. Всё через stdin/stdout
В условии сказано, что надо писать определённую команду после каждого вывода. Например на паскале flush(output).
По 18 включительно? Или до 18? (Т.е закрывается в 00:00 18 или в 00:00 19)?
До 18 включительно, то есть 18 числа последний день.
Заочный этап закончился... Когда будут показаны результаты оффлайн-тестов?
Теперь уже можно обсуждать задачи?
Думаю, да
Как нормально решить D? И почему ответ не максимальное пересечение элементов 2-х разных языков?
Разве нет? У меня на 100 зашло максимальное пересечение элементов 2-х разных языков. Не знаю как нормальное решение. Но... Кол-во различных элементов встречающихся менее const раз тривиально пересчитываем и удаляем. Оставшиеся пихаем в битсет. И пробегаемся! (Битсет свой писал. Встроенным не умею пользоваться.)
Ну я и сразу понял,что ответ всегда <=m, ибо столько символов в каждом языке... И собственно я написал решение за O(n*n*m+nmlog(m)) который должен был получить 50... но не прошел(получил только 35 баллов) Вот код (http://pastebin.com/bPqCXPvG)
при n = 1 ответ 0
Да, нежданчик тест был
Очень даже нежданчик... Теперь во всех задачах отдельно буду обрабатывать if(n==1)...
Плохая идея. Так тоже регулярно решения падают, потому что самое важное — не "разбирать случаи руками", а "головой думать". Несколько раз видел, что зачем-то в решении отдельно разбирают минимальный тест и разбирают неправильно.
самый тривиальный случай и ...WTF!!!
Асимптотика
?
Не понял, что имеется в виду под "пробегаемся"
Пуcть const1 = 200(можно чуть больше). Ну вначале сжимаем все значения. И смотрим, если определённое значение встречается менее const1 раз, то за const1^2 увеличиваем все пары одинаковых элементов в отдельный двумерный массив и удаляем его(кроме группы, где n = 10000). Так мы сделаем не более n*m / const1 * const1^2 действий. Т.е n * m * const1. Оставшиеся значения оставим и сожмём. Пусть размер битов у нас = 20 (т.к нам надо подсчитать заранее за 2^20 кол-во бит в числе). Пусть const2 = кол-во различных элементов, встречающихся более const1 раз. Таких будет не более n * m / const1. Сократим их битсетом. Теперь их n * m / const1 / 20 в худшем случае. Отметим двумерный массив для i-го массива битсет из const2 / 20 блоков. Идём по этим блоком, делая побитовое и и проверяя по массиву преподсчёта, кол-во одинаковых элементов. + Добавим тот массив, который мы преподсчитали заранее. (Т.е все элементы встречающиеся менее const1 раз). И так для каждой пары. Среди всех таких вариантов выбрать максимум. И того асимптотика O(const1 * n * m + n^2 * const2 / 20). Ну для случая, где n <= 10000 можно не сжимать координаты и определить заранее кол-во блоков. Это ускорит процесс. (Т.к. там c =200).
решения можно
Как решать B,F на полный бал?...
F — http://codeforces.com/blog/entry/15296
Если правильно понял то, для проверки, что компания яв-ся обделенной надо удалить из графа все ею обслуживаемые дороги и проверить, если граф связный то, обделенная, если нет то-не обделенная ?
Ну да.. Ну не совсем связанный. А находятся ли столицы в одной компоненте связанности.
B — имитацией сортировки подсчётом + проход. http://pastebin.com/hsjj7p7L (Мой код.)
Т.е мы увеличиваем значения границ подсчётом. А потом пройдёмся один раз.
не можете объяснить поподробнее...
Вначале подсчётом увеличиваем левую и правую границу нашего путешествия в каком-нибудь массиве(имитация сортировки подсчёта). У меня это массив ar. Также храним сумму на префиксе для пересчёта дней, что мы прошли. Т.е последних b дней. Т.е смотрим, если кол-во поездок > с хотя бы в какой-то момент времени, то ответ нет. Вообще массив ar хранит то значение на которое нужно изменить это кол-во на данный момент. А переменная s хранит точное значение. Она меняется в процессе , благодаря массиву ar. Следовательно если есть хоть один день , то увеличиваем значение. И каждый раз проверяем, сколько у нас дней в зоне за последние b дней. Если что-то непонятно написал, спрашивай!
Как решать I,K?
Если не обращать внимания на ограничения по памяти, то K баян на дп по подотрезкам с квадратом памяти заходящий на 50. Если мы будем идти не ленивой динамикой, а сохраним последние три диагонали, то кол-во способов найти просто. Чтобы сократить откаты заметим, что если крайние символы равны, то нам всегда выгодно их удалять. Осталось два случая. Удалить первый символ или последний. (т.е дописать в конец или в начало). Теперь массив откатов нам можно хранить в виде 0 и 1. Можно сделать это битсетом. Тогда получится массив 5000*127. И это зайдёт на 70. И что осталось? Мы знаем как найти ответ(кол-во символов, что нужно добавить). И как сделать откаты. Но на них не хватает памяти. Однако можно сделать последнии 5000 откатов. Т.е первый раз пересчитываем за n^2. И запоминаем последниии 5000 значений на которые надо откатиться. И того у нас длина n — 5000. Ещё раз повторяем тоже самое за квадрат(n — 5000)^2, сохранив 5000 откатов. Нам осталось n — 10000. И находим последнии 10000 значений за (n — 10000)^2.
продолжая эту идею с делением нахождения ответа пополам (рекурсивно), можно добиться O(n) памяти, сохраняя тот же O(n2) времени
А я задачу к НОП свел. (Если мы зафиксировали центр палиндрома, то нужно за минимальное количество операций вставки в произвольное место строки сделать части до центра и после центра равными. Для строк s и t количество операций |s| + |t| - 2 * |lcs(s, t)|). А дальше уже искал в вики алгоритм: https://en.wikipedia.org/wiki/Hirschberg%27s_algorithm
Тоже свёл задачу к НОП.Но смог написать только на 50 :(
Объясните суть алгоритма, а то с английским туго.Спасибо!
P.S.Тоже пришёл к решению с lcs, но не знал как из ML выйти(
Нашел статью на русском: http://habrahabr.ru/post/117063/
И ещё статью на английском, из которой позаимствовал код: http://wordaligned.org/articles/longest-common-subsequence#tochirschbergs-linear-space-algorithm
Вкратце: пусть мы ищем НОП для строк s и t. Разобьём s на две примерно равные по длине части s1 и s2. Тогда НОП(s, t) = НОП(s1, t1) + НОП(s2, t2). Найти оптимальное разбиение строки t на t1 и t2 мы можем, посчитав последний слой динамики для s1, t и reversed(s2), reversed(t). После этого ищем ответ рекурсивно для пар строк s1, t1 и s2, t2.
I — http://e-maxx.ru/algo/suffix_automata . Пихаем конкатенацию всех строк, разделённых одним символом-разделителем в один суффиксный автомат. И по очереди строим для каждой строки второй. Для каждого состояния найдя кол-во различных подстрок. Теперь если кол-во различных подстрок для одного автомата равно другому, то такой подстроки больше нигде нет, кроме как в этой строке. Найдём такой массив. Для i-той позициии будем хранить ближайший индекс справа, такое что подстрока [i;ar[i]] встречается как подстрока только для данной. Чтобы его найти, пройдёмся двумя указателями по строке. Правую границу двигаем, меняя состояния суф. автомата, пока такая подстрока встречается, как подстрока другой. Затем левую двигаем, пока такая подстрока больше нигде не встречается. И обновляем значения для нашего массива позиций. Теперь зная этот массив, за один пробег по нему находим минимальную длину. Теперь среди всех подстрок минимальной длины нужно найти лексикографически минимальную. Для этого просто будем хранить хеши. Находя ближайший символ для двух строк, не равный друг другу. И обновляя ответ нужных позиций. А..и у меня c++ строки не заходили(TL). Пришлось на c — строки переписывать.
если перевернуть все строки, то хеши не понадобятся, вершина, которая раньше встречается в обходе дфсом графа суфф. ссылок, та и меньше лексикографически (спс adamant)
да и изначально достаточно одного общего автомата.
Задачу I можно довольно несложно решить суфмасом. Добавим в конец каждой строки свой особый символ и произведем конкатенацию всех строк из набора. Получим большую строку. Построим по этой большой строке суфмас, найдем для него массив LCP (longest common prefix) например, алгоритмом Касаи. Теперь о самой идее решения. Пройдемся по нашему суффиксному массиву указателем i, в то же время поддерживая указатели l и r. Пусть i-й суффикс принадлежит k-й строке из входных данных. Тогда пусть l указывает на последний перед i суффикс, не принадлежащей k-й строке, а r — на первый после i суффикс, не принадлежащий k-й строке. Тогда так как мы уже построили массив LCP, нам не составит труда улучшить ответ. А именно, зная максимум из LCP(l, i) и LCP(i, r), мы попытаемся жадно улучшить ответ для k-й строки (если, конечно, можем). Будут вопросы — обращайтесь :)
Ну я понял.Спасибо:)
Как решать задачу D и K на 100 баллов ?
Заранее спасибо.
D:(http://codeforces.com/blog/entry/21396?locale=ru#comment-273500)
K:(http://codeforces.com/blog/entry/21396?locale=ru#comment-273538)
Думаю, буду прав, если скажу, что вопрос затягивания объявления окончательных результатов становится всё более актуальным :)
Окончательные результаты появятся ближе к концу января, после завершения проверки на списывание. Предварительные результаты будут доступны достаточно скоро.
А в последний день января данный вопрос еще более актуальный
регион завтра, куда спешить?
Планируется ли добавить задачи на CF или открыть дорешку?
Тадам-тадам...! ПОЯВИЛИСЬ РЕЗУЛЬТАТЫ!!!
На сайте олимпиады написанно что очный этап будет проходить 6-8 марта, то есть 6 надо уже обязательно быть там или это день заезда?
А как быстро орг.комитет отвечает если написал на e-mail [email protected]. Нужно анкету подправить(ту, что до 23 февраля обязательна к заполнению).