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

XXIII Открытая Всесибирская олимпиада по программированию им. И.В. Поттосина
Автор ssor96, история, 2 года назад, По-русски

Всем привет. Решил ли кто 10 задачу неявным декартовым деревом или какое предполагалось решение? Еще интересно послушать про 11 задачу.

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

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

Привет. У меня в 10 зашло FFT. 11 решается через банаховы пространства.

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

Мне очень интересно узнать про 04 — заходит ли там $$$\frac{qt \log n}{64}$$$ или нет, и если нет, как вообще такое решать?

10 мы сдавали лет 5 назад в ПТЗ явным декартовым деревом с unite. А как неявным делать?

→ Ответить
  • »
    »
    2 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +32 Проголосовать: не нравится

    Наше решение 4. Реализуем наивно за O(q*t). По асимптотике почти подходит, но это TL. Дольше всего работают прыжки по массиву red и blue, так как идёт обращение к ОЗУ в случайные места. Мы решили предпосчитать для всех позиций красной и синей фишки первые 512 ходов так же втупую за O(n*512). Как это применить для запросов? Если t<512, то идём втупую, как делали раньше. Иначе уменьшим t на 512 и пройдём по предпосчитаным массивам (тоже втупую) и добавим в сумму xor. За счёт такой техники мы используем кеш процессора, что существенно ускоряет программу

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

Задача 10 выглядела несколько баянистой, и в итоге такой и оказалась.

Однако здесь предполагалось гораздо более простое решение. Заметим, что $$$N$$$ небольшое, так что $$$O(N^2)$$$ должно проходить — надо только избавиться от $$$O(Q N)$$$ в асимптотике.

Можно заметить, что т.к. направление сортировки всегда одинаковое, то и количество инверсий никогда не увеличивается, а лишь уменьшается. А всего их $$$O(N^2)$$$, так что если мы будем просто swap-ать неправильно стоящих соседей, то времени на это хватит — главное их быстро находить.

Сортировка вставками работает за $$$O(L + I)$$$, где $$$L$$$ — длина отрезка, а $$$I$$$ — количество инверсий. Поскольку $$$O(I)$$$ в сумме даёт $$$O(N^2)$$$, то надо лишь сделать так, чтобы сумма $$$O(L)$$$ не была слишком большой.

Для этого можно хранить в дереве поиска набор позиций $$$k$$$, таких что $$$A[k-1] > A[k]$$$. Имея такое дерево, мы можем быстро ответить на вопрос, отсортирован ли отрезок. Если нет, то мы делим заданный отрезок этими позициями на возрастающие куски.

Перебираем куски слева направо, для каждого запускаем сортировку вставками, двигая элементы влево насколько нужно. Важный момент: если мы взяли очередной элемент куска и его не надо двигать влево, тогда оставшуюся часть данного куска нужно пропустить, и сразу перейти к следующему куску. За счёт этого мы тратим на запрос $$$O(R + I)$$$ вместо $$$O(L + I)$$$, где $$$R$$$ — количество кусков, а $$$L$$$ — длина запроса. Остаётся заметить, что сумма $$$O(R)$$$ не превышает $$$O(N + Q)$$$, потому что каждый запрос удаляет из дерева поиска все позиции, и добавляет максимум две новых на концах.

Получается решение за $$$O(N^2 + Q log N)$$$.

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

Как решалась 11 задача?

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

    Посмотрев на определитель матрицы системы можно получить, что верно одно из трёх:

    1. d1=d2=d3
    2. d1+d2+d3 = 0
    3. Матрица системы невырождена

    В первом случае ходы неразличимы, решение очевидно

    В случае (2 но не 1) все ходы сразу бесполезно, переберём какой ход не используем, задача сведётся к двумерной с невырожденной матрицей.

    Когда у нас есть невырожденная матрица, находим методом гаусса единственное решение и проверяем его допустимость.

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

      Немного не очевидно, что определитель равен 0 только в этих двух случаях. Почему нет других вариантов, когда определитель равен 0?

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

        Определитель имеет вид $$$d_1^3 + d_2^3 + d_3^3 - 3 d_1 d_2 d_3$$$

        Приравняем к нулю и решим относительно $$$d_1$$$

        Получим одно вещественное решение $$$d_1 = -d_2 - d_3$$$.

        Остальные два решения комплексных и они будут вещественными только в случае $$$d_1=d_2=d_3$$$.

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

Добрый день. А где можно на задачи посмотреть или дорешать ?

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

Как решалась 6 задача?

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

    Вызываем package.zaic =)

    Придумать какой-то способ строить лабиринт логарифмического размера несложно, но упихать его в ограничения задачи очень непросто.

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

    Взглянем на конструкцию вида:

    ..#######..
#.........#
###########
#.........#
.....#.....

    Количество кратчайших путей при старте из левого нижнего угла будет:

    ..#######..
#.........#
###########
#123444444#
11111#48**16

    В этой конструкции для получения от 0 до 15 количества кратчайших путей в правом верхнем углу достаточно убирать отдельные стены в средней линии: чтоб добавить от 1 до 3 путей надо убрать одну из стен, помеченных собачкой. И независимо от этого чтоб добавить 4, 8 или 12 путей надо убрать соответственно 1, 2 или 3 стен, помеченных вопросиком:

    ..#######..
#.........#
#@@@#?#?#?#
#123444444#
11111#48**16

    Весьма удачным, но всё-таки не совпадением, оказывается тот факт, что количество путей дойти правой нижней клетки равно 16. И подставив такую же конструкцию ещё раз справа мы аналогичным образом сможем добавить ещё x*16 различных кратчайших путей (где х от 0 до 15) дойти до правой верхней клетки:

    ..#######...#######..
#.........#.........#
#####################
#.........#.........#
.....#.........#.....

    Дополнительный ряд сверху с хреновиной посередине нужен, чтоб удлинить верхние пути: иначе б пути из второй конструкции справа уже бы не были кратчайшими до правой верхней клетки.

    Обобщая, имея в левом нижнем углу 2^k путей мы научились строить конструкцию, с помощью которой можно до 15 раз добавить 2^k кратчайших путей и которая при этом получает в нужном месте 2^(k+4) путей и тем самым позволяет продолжить себя такой же конструкцией. Её размер 5*10 клеток и для получения до 2 миллиардов путей понадобится до 7 с половиной таких вот штук. В оптимальных конструкциях жюри получаются поля размера до 75*5 — площади 375.

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

Как решалась задача 2?

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

    Динамика по изломанному профилю. Заполняем матрицу комнат построчно и для каждой комнаты выбираем в переходах в динамике ее ориентацию, при этом профиль динамики хранит, есть ли дверь в комнаты профиля снизу, а также есть ли дверь в последнюю комнату справа. Соответственно, когда мы выбираем ориентацию очередной комнаты, мы можем сразу проверить, подходит ли она под профиль.

    → Ответить