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

Подскажите задачи на применение дерамиды
Автор Hohol, 13 лет назад, По-русски

Прочитал отличный цикл статей  от Skiminok о дерамиде.

Хотелось бы применить полученные знания на практике.
Сам могу указать две задачи с тимуса: War Games 2 и Battle with You-Know-Who. Но в них используются лишь относительно простые операции, хотелось бы чего-нибудь повеселее.
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

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

http://acm.timus.ru/problem.aspx?space=1&num=1469

http://acm.timus.ru/problem.aspx?space=1&num=1839

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Как решать первую?
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      В Кормене есть разбор. В кратце так:

      Сортируем все точки концов и начал отрезков по x. Потом сканлайном по этим точкам строится множество отрезков, сравнение - у кого точка пересечения со сканлайном ниже. Если точка открывает наш отрезок - то смотрятся непосредственно следующий и предыдущий отрезки в множестве, если наш пересекается с одним из них, то ответ найден. Ну и добавить отрезок надо. Если точка закрывает наш отрезок, то проверяется пересечение следующего и предыдущего во множестве, и отрезок удаляется. Собственно тут всплывает много операций: add, delete, prev, next, так что подходит сбаллансированое деревое, например treap.

      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Спасибо, не догадался в Кормена заглянуть.

        И из-за кодефорсеса забыл о существовании дискасса на тимусе. Там все уже давно рассказали.
        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Возможно, Вам понравится эта задача, в ней любопытная задумка. Вообще, можно все прорешать из раздела.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Очень приятная задача. Из раздела единственная, над которой пришлось думать.

    Решил сначала SQRT-декомпозицией - так мне почему-то проще рассуждать было, затем переписал на дерамиду. С дерамидой получилось намного короче и красивее. Прямо проникся мощью дерамиды по неявному ключу.

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Поделись, пожалуйста,  идеей с SQRT-декомпозицией. В общем, я  представляю, что нужно будет хранить сумму в блоке на чётных/нечётных позициях, но сталкиваюсь определёнными проблемами при пересчёте.
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Насколько я понял, ты еще не дошел до верной идеи решения. Лучше подумай еще немного, она классная, и не слишком сложная.
        "нужно будет хранить сумму в блоке на чётных/нечётных позициях" - не совсем верно.
        В любом случае, ответ в первой правке.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Педагогично, но буду благодарен, если дашь хоть небольшую подсказку.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Не вижу подсказок кроме подсказки размером с решение. Смотри первую правку.
            → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

http://www.spoj.pl/problems/ORDERSET/
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вот эта задача красиво решается дерамидой.
http://acm.timus.ru/problem.aspx?space=1&num=1521
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Да. А я в свое время приспособил фенвика для нахождения "k-ой статистики"...
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Там есть ваще простое и красивое решение с treap =) По неявному ключу правда.
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Декартово дерево,  cartesian tree,  дерамида,  treap  - это все одно и тоже. Среди тех с кем я общаюсь наиболее распространено первое название, на втором месте второе (в общем в порядке употребления перечислил).
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Да, спасибо. Но к чему это? Или я где-то не так выразился?

          UPD: Насколько вспомнил, есть ещё дуча и курево.
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          А еще бывает калька с английского (treap): дуча и курево
          → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А как это нормально фенвиком делать?

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

      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Фенвиком можно за O(1) находить сумму ненулевых элементов на отрезке от [1..R]. А двоичным поиском искать это R - и того O(LogN) на запрос.
        Ошибся.
        Вот как раз сейчас нашел в своих "закромах" код фенвика, который вроде должен давать logN
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Фенвик вроде всю жизнь за логарифм работал.
          → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

          дабл пост
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Никогда не слышал, что фенвик работает за О(1) ...
          → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Не за O(1) работает фенвик.
          Я ещё понимаю, как приспособить сюда что-то похожее на двоичные подъёмы, чтобы в сумме за O(log) работало.
          → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Фенвик умеет искать место с нужной суммой за O(log N)
        → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    И тут Фенвик::)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну ведь просили же задачи, которые решаются в том числе декартовым деревом, а не только декартовым деревом. Какие претензии то?)
      → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Я извиняюсь. Upit - действительно хорошая задача, чтобы понять как без багов писать групповые операции на дерамиде. Я очень долго тупил с ее написанием и все-таки сдал(на своем ноутбуке, на своем ejudge). 

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

http://acm.timus.ru/problem.aspx?space=1&num=1839
как решить задачу с помощью дерамиды? Ничего лучше как пересечение двух дермид не знаю ...
→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Если у кого есть построение на Паскале дерамиды по явному ключу можно попросить код посмотреть. Сам написал, но не во всех случаях верно строит. Хочу попробовать понять правильное решение.

→ Ответить