Всем привет!
ВКОШП уже совсем скоро, но еще есть шанс успеть потренироваться! В качестве этого шанса на сайте интернет-олимпиад будет проведена последняя тренировочная олимпиада, которая состоится уже сегодня — в субботу (26 ноября) в 14:00 по московскому времени.
Множество проблем возникло у Ньюта Саламандера, который пытается вернуть всех своих магических существ обратно в волшебный чемодан, и вам предстоит помочь ему с этим.
Продолжительность этой олимпиады будет составлять 5 часов в усложненной номинации и 3 часа в базовой. Подробнее о номинациях и правилах можно прочитать здесь. По возникшим вопросам во время олимпиады просьба писать на почту жюри.
Если вы еще не регистрировали команду на интернет-олимпиады в этом сезоне, то сделать это можно тут. Все команды будут подтверждены перед началом олимпиады.
Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client.
Олимпиаду для вас подготовили Михаил Путилин (SpyCheese), Илья Збань (izban), Николай Будин (budalnik), Станислав Наумов (josdas), Дмитрий Филиппов (DimaPhil), Илья Пересадин, (pva701), Григорий Шовкопляс (GShark), Виктория Ерохина (viktoria) и Наталья Слепкова (filyera).
Удачи!
Что с проверяющей системой?
del
Надеюсь на скорую помощь системе тестирования)
UPD. Спасибо за своевременное исправление проблемы.
Объявление на официальном сайте нирка.
К сожалению, были проблемы с веб-сервером, все починилось, каждая из номинаций продлена на 50 минут.
Раунд будет нерейтинговым для всех участников.
Что значит раунд будет нерейтинговым?
Лайк, если тоже понравилось впихивать каждую вторую задачу по ТЛ...
лайк, если тоже просто криворукий
Какое такое решение подразумевалось в В, что его не надо пихать в 64Mb/1.5sec?
Авторское решение: Откажемся от всех сложных структур. Заметим, что в массиве после всех операций будет O(k) подстрок исходного массива. То есть мы можем представить конечный массив как конкатенацию подстрок из начального массива ai1 + ai2 + ... + aik, где i1, i2, ..., ik — перестановка, k — количество подстрок.
После каждой операции будем в явном виде поддерживать массив перестановок i и блоков a. Введем вспомогательную операцию: разделить исходный массив в точке x, если x не является границей какого-либо блока, выполняем операцию за O(k). Рассмотрим как происходит операция первого типа. В начале и в конце каждого отрезка проведем операцию деления на блока, так мы суммарно добавили 4 отрезка или меньше. Теперь мы можем поменять местами блоки на этих отрезках за O(k) потому, что начала и концы отрезков точно находятся на границах блоков. Для запроса второго типа просто проведем операцию разреза.
Для выполнения операции второго типа выполним проход по всем операциям первого, что бы получить массив блоков, в котором после применения любого запроса блоки не будут создаваться, а будут только меняться местами. Вторым проходом по всем операциям будем отвечать на запросы. Теперь отсортируем числа внутри каждого блока и линейным проходом с бинарным поиском ответим на запрос за O(k·log n). Числа k не превышает 4·m, так как каждая операция добавляет не более 4-ех новых блоков.
Такое решение работает за O(m2·log n) времени и O(n + m) памяти
Спасибо.
Кажется, я написал(и сдал с +13) нечто похожее, но, если честно, мне не понятно, что авторы хотели отсечь такими ограничениями.
Отсечь O(n·m) (со всякими оптимайзами на более маленьких ограничениях легко сдать), отсечь всякие сканлайны со сложными структурами, отсечь решение не с линейной памятью.
Когда будет доступ к олимпиаде в тренировках КФ?
Всё как всегда — как только жюри опубликует архив, тут же сделаем тренировку.
Так что там с архивом? :)
Контест добавлен в тренировки: