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

Автор I_love_Varechka, 10 лет назад, По-русски

Всем доброго времени суток. Столкнулся с задачами на LCA в которых нужно отвечать на запрос за 1, читал e-maxx столкнулся с множеством алгоритмов которые решают данную проблему хотелось бы узнать что вы чаще всего используете для решение таких задач.

UPD Всем спасибо за помощь, я остановился на двоичном подъёме.

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

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

http://e-maxx.ru/algo/lca_linear

Тут описывается, как эту задачу свести к задаче нахождения минимума на отрезке. А эту задачу можно решать(без запросов на модификацию) при помощи sparse table за препроцесс O(NlogN) и запрос за O(1).

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

Если нужно решить за O(1) в онлайне, то лучше свести к задаче минимум на отрезке и там юзать sparce table (Ибо Фарах-колтон из-за большой константы работает столько же). А если запросы даны в оффлайне использую Тарьяна (считает в сумме за O(N)).

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

Двоичный подъем. Алгоритм короткий, простой, и хотя асимптотика O(logN) на запрос, константа у алгоритма совсем маленькая.

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

    Вот только памяти столько же жрёт :(

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

      На контестах это редко является проблемой.

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

      Лично у меня ни разу на контестах не было проблем с тем, что двоичный подъем не заходит по памяти. А так — конечно, можно поизвращаться со сведением к RMQ и даже с алгоритмом RMQ за O(log * N) с препроцессингом за — он еще относительно практичный.

      Кстати, алгоритм таков. Разбиваем массив на отрезки длины , находим на каждом из них RMQ, получаем массив RMQ размера . Строим по полученному массиву Sparse Table (память, очевидно, O(N))). Теперь мы можем находить RMQ за — одним запросом к Sparse Table и проходом оставшихся хвостов тупым алгоритмом. Чтобы не проходить хвосты втупую, можно для каждого из блоков размера рекурсивно построить Sparse Table, и так далее для еще меньших блоков, пока блоки в конце концов не станут единичного размера — у нас получится своеобразное дерево глубиной O(log * N).

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

        зачем что-то рекурсивно строить для блоков размера , то есть на практике меньше 20? Заводим 2 массива с минимумами на префиксах и на суффиксах для каждого блока. Тогда тупым алгоритмом придется обрабатывать лишь небольшую () часть запросов, у которых обе границы лежат внутри одного блока, а все остальные будут работать за константу.

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

          А почему бы не сделать тесты, в которых все запросы будут именно "плохие"?

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

            тогда будет работать за log с очень небольшой константой. А чтобы получить честный O(1), придется применить трюк четырех русских, вернувшись таким образом к фарах-колтону и бендеру :)

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

Алгоритм Тарьяна меньше памяти потребляет, чем двоичный подьем? Так как вот это задача не укладывается по памяти с помощью последнего http://informatics.mccme.ru/mod/statements/view3.php?id=1089&chapterid=2787#1

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

    Да. И название задачи какбэ намекает.

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

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

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

    Так как вот это задача не укладывается по памяти с помощью последнего

    Вы построили дерево явно, да еще и на векторах? Разумеется, у Вас ничего не уложится, т.к. у вектора изначальный размер вроде бы 10 (зависит от реализации, но я где-то такую цифру видел).

    Задачу можно решить двоичным подъемом немного по-другому, идея была описана в комментариях к моему посту. Если написать все аккуратно, то такое решение просто обязано зайти.

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

      Ну строил я на массивах и явно, просто там ограничения 5 *10^5 вершин. А как я понял памяти съест двоичный подъем n * log (n), еще я писал на Java и наверно не оптимально, то думаю не зайдет. Сейчас попробую Тарьяном. Спасибо.

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

        Я подсчитал расход по памяти при аккуратной реализации, получается 42 МБ. Вам не интересно разобраться, почему Вы все-таки получаете MLE? :)