Блог пользователя DimaPhil

Автор DimaPhil, история, 8 лет назад, По-русски

Всем привет!

ВКОШП уже совсем скоро, но еще есть шанс успеть потренироваться! В качестве этого шанса на сайте интернет-олимпиад будет проведена последняя тренировочная олимпиада, которая состоится уже сегодня — в субботу (26 ноября) в 14:00 по московскому времени.

Множество проблем возникло у Ньюта Саламандера, который пытается вернуть всех своих магических существ обратно в волшебный чемодан, и вам предстоит помочь ему с этим.

Продолжительность этой олимпиады будет составлять 5 часов в усложненной номинации и 3 часа в базовой. Подробнее о номинациях и правилах можно прочитать здесь. По возникшим вопросам во время олимпиады просьба писать на почту жюри.

Если вы еще не регистрировали команду на интернет-олимпиады в этом сезоне, то сделать это можно тут. Все команды будут подтверждены перед началом олимпиады.

Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client.

Олимпиаду для вас подготовили Михаил Путилин (SpyCheese), Илья Збань (izban), Николай Будин (budalnik), Станислав Наумов (josdas), Дмитрий Филиппов (DimaPhil), Илья Пересадин, (pva701), Григорий Шовкопляс (GShark), Виктория Ерохина (viktoria) и Наталья Слепкова (filyera).

Удачи!

  • Проголосовать: нравится
  • +20
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Что с проверяющей системой?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

del

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Надеюсь на скорую помощь системе тестирования)

UPD. Спасибо за своевременное исправление проблемы.

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Объявление на официальном сайте нирка.

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

К сожалению, были проблемы с веб-сервером, все починилось, каждая из номинаций продлена на 50 минут.

Раунд будет нерейтинговым для всех участников.

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Лайк, если тоже понравилось впихивать каждую вторую задачу по ТЛ...

»
8 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

Какое такое решение подразумевалось в В, что его не надо пихать в 64Mb/1.5sec?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Авторское решение: Откажемся от всех сложных структур. Заметим, что в массиве после всех операций будет O(k) подстрок исходного массива. То есть мы можем представить конечный массив как конкатенацию подстрок из начального массива ai1 + ai2 + ... + aik, где i1, i2, ..., ik — перестановка, k — количество подстрок.

    После каждой операции будем в явном виде поддерживать массив перестановок i и блоков a. Введем вспомогательную операцию: разделить исходный массив в точке x, если x не является границей какого-либо блока, выполняем операцию за O(k). Рассмотрим как происходит операция первого типа. В начале и в конце каждого отрезка проведем операцию деления на блока, так мы суммарно добавили 4 отрезка или меньше. Теперь мы можем поменять местами блоки на этих отрезках за O(k) потому, что начала и концы отрезков точно находятся на границах блоков. Для запроса второго типа просто проведем операцию разреза.

    Для выполнения операции второго типа выполним проход по всем операциям первого, что бы получить массив блоков, в котором после применения любого запроса блоки не будут создаваться, а будут только меняться местами. Вторым проходом по всем операциям будем отвечать на запросы. Теперь отсортируем числа внутри каждого блока и линейным проходом с бинарным поиском ответим на запрос за O(k·logn). Числа k не превышает m, так как каждая операция добавляет не более 4-ех новых блоков.

    Такое решение работает за O(m2·logn) времени и O(n + m) памяти

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Спасибо.

      Кажется, я написал(и сдал с +13) нечто похожее, но, если честно, мне не понятно, что авторы хотели отсечь такими ограничениями.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Отсечь O(n·m) (со всякими оптимайзами на более маленьких ограничениях легко сдать), отсечь всякие сканлайны со сложными структурами, отсечь решение не с линейной памятью.

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Когда будет доступ к олимпиаде в тренировках КФ?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Всё как всегда — как только жюри опубликует архив, тут же сделаем тренировку.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Так что там с архивом? :)