Всем привет!
Уже в эту субботу, 20 февраля в 16:00 по московскому времени состоится четвертая личная интернет-олимпиада для школьников. На этот раз помощь потребовалась фантастической неповторимой четверке — Атосу, Портосу, Арамису и Д'Артаньяну!
Продолжительность олимпиады — 5 часов. Не забудьте зарегистрироваться на цикл личных интернет-олимпиад в этом сезоне перед началом олимпиады, если вы не сделали этого раньше.
Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client (русская версия).
Олимпиаду для вас подготовили Дмитрий Филиппов (DimaPhil), Илья Пересадин (pva701), Дарья Яковлева (Devushka) и Григорий Шовкопляс (GShark).
Удачи!
Новый год уже близко...
На сайте написано, что олимпиада начнётся в 16:00.
Это ошибка в посте, олимпиада начнется в 16:00
Автокомментарий: текст был обновлен пользователем DimaPhil (предыдущая версия, новая версия, сравнить).
Каналья! Тысяча чертей!
Почему мои посылки по D были на 60 баллов, а теперь WA #1?
Теперь ещё нельзя просмотреть код некоторых посылок по D. Что-то странно.
Все посылки по D были перетестированы. Можете проверить соответствующий комментарий во вкладке Messenger. Также советую, в будущем писать на почту Жюри по всем вопросам, потому что комментарии тут мы читаем не так оперативно, как почту. Пост используется именно для анонса, а не для связей с общественностью:)
OKAY. =]
Где можно порешать задачи этой олимпиады? (сдать их)
Как только закинут в тренировки наверное.
Разбор будет?
В Тренировках: 2015-2016 Цикл интернет-олимпиад. Четвертая личная олимпиада (20 февраля 2016 года).
Может кто подскажет как решать B и С? А то, я так понимаю, разбора не будет
Задача B:
Будем хранить сет неудаленных лестниц, когда приходит запрос найдем lower_bound-ом в сете ближайшие неудаленные и попробуем пройти через них.
Задача C: Положим все строки в бор, каждая вершина в боре задает некоторый префикс, количество строк с этим префиксом — кол-во листов в этом поддереве.
Для каждой вершины в боре посчитаем, сколько максимально символов при подъеме вверх из этой вершины будет равно суффиксу t. Для этого посчитаем двоичные подъемы из каждой вершины и сравнивать на равенство строки будем хэшами, либо зараннее предподсчитав для каждого двоичного подъема его класс эквивалентности, как это делается в суффмассиве.
Теперь для каждой вершины знаем suff[v] — длина максимального суффикса t, lev[v] — глубина этой вершины. В предка на высоте lev[v] — suff[v] положим пару (lev[v], leafs[v]). Теперь просто спускаемся строкой t по бору, в каждой вершине для каждой пары релаксируем ans[first] = max(ans[first], second).
Можно проще. Что мы хотим? Посчитать для каждой вершины бора наибольший общий суффикс с T.
Давайте сделаем следующее, рассмотрим все строки положенные в бор (они заданы во входных данных), мы хотим у каждого префикса каждой из строк найти наибольший общий суффикс с T.
Перевернём задачу. Поревёрсим строку T, а также все интересные нам строки, теперь задача свелась к поиску наибольшего общего префикса с ревёрсом T у каждого суффикса каждой строки. Решается Z-функцией.
deleted
Как решать задачу D?
40 баллов: можно за 27 попыток в худшем случае определить ответ по всем первым 4 тестам. Просто выводим сразу ответ. Если подошел, то оставляем, нет — прибавляем к нему 1 и отсылаем еще. Ограничений по посылкам не было.
50-100 баллов: бинарный поиск нужного элемента, работающий за log(n) или log(n)+1. Вроде бы не подходит ко всем тестам. Но можно предположить, что номер искомого элемента при делении на 10 дает остаток 0, 1, 2, 3, ..., 9, и искать таким образом только среди таких элементов за log(n/10) и 10 посылок. Выбирайте сразу остатки от 30, чтобы наверняка получить результат.
Не реализовывал, должно было зайти.
Авторское решение такое:
Наблюдение: во всех тестах суммарное количество монет — степень тройки. Давайте тогда научимся для количества монет 3n решать задачу за n действий.
Для примера рассмотрим тест с 13 золотыми и 14 серебряными монетами. Разделим эти 27 монет на три группы: (4 золотых, 5 серебряных), (4 золотых, 5 серебряных), (5 золотых, 4 серебряных). Взвесим первые две группы. Теперь рассмотрим три случая:
Во всех трех случаях мы перешли от 27 монет к 9, то есть уменьшили количество рассматриваемых монет в три раза. Значит мы научились решать задачу для 3n монет за n действий, ура!