1 Тема от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Тема: timus 1553

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

Здравствуйте!
Собственно сабж. На первый взгляд я подумал что все просто - такая же задача как и LCA при помощи RMQ, только ищем максимум по уровню радиации. Но если разобрать пару примеров - становиться понятно что эта идея неверна. Кстате говоря если бы нужно было искать сумму значений радиации - то она бы так и решалась, на этом сайте есть описание этой задачи.
Собственно в обсуждениях этой задачи на тимусе - кто то, что то писал, но честно говоря я толком ничего не понял. Точнее там пишут, что можно применить sqrt-декомпозицию, понятно что при поиске максимум некоторые группы целиком пропускаем - это собственно принцип декомпозиции, но вот толком как это дело обновлять чего то непонятно....
В общем кто нибудь может рассказать внятный алгоритм или как то чего то намекнуть?

2 Ответ от KADR Отредактировано KADR (2010-05-29 18:19:39)

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: timus 1553

Можно использовать Heavy-light декомпозицию. Сложность будет O(N*logN*logN). Почитать о ней можно здесь.

3 Ответ от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Re: timus 1553

Спасибо за прикольную штуку:) Реализовал, но по тайм лимиту на 17 тесте не проходит. Зашел потом в обсуждение - там оказывается тоже какой то человек пытался решить с такой оценкой - у него также ТЛ 17. Все таки видимо константа большая получается.... Хотя может я реализовал коряво. Но вообще я разобрал алгоритм, взял там код программы и оптимизировал его - так как он выдавал ТЛ 4...
Так что пока вопрос открыт....

4 Ответ от KADR Отредактировано KADR (2010-06-02 16:57:34)

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: timus 1553

Можно решать за O(NlogN). Достаточно для каждого пути хранить максимальный уровень радиации на нем. Тогда делать запрос на не полном пути придется делать не более четырех раз, а на остальных путях максимум брать можно за О(1).

Учитывая, что тут радиация только увеличивается, можно вместо деревьев отрезков использовать деревья Фенвика. Правда тогда по 2 для каждого пути (снизу вверх и сверху вниз). Но все равно, думаю, это уменьшит константу.

5 Ответ от Oleg

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: timus 1553

heavy-light декомпозиция не гарантирует что у нас будет не больше 4х нецелых путей для всех вершин.

Попробуй оптимизировать чтение  / хранение дерева

6 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: timus 1553

Почему это не гарантирует? Для каждого запроса у нас есть набор путей в которых лежат все вершины на кратчайшем пути из A в B. Неполными могут быть лишь пути в которых лежат A и B, а так же путь в котором лежит LCA(A,B). Выходит даже не 4, а 3 неполных.

7 Ответ от Oleg

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: timus 1553

Чего-то ты выдумываешь smile
Нарисуй на бумаге небольшое бинарное дерево и сделай его композицию  - когда мы спускаемся с пути на котором лежит A вниз, мы же не попадаем на полный промежуточный путь - а лишь на его часть.

8 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: timus 1553

Да, тут я ошибся smile Все-таки пути не обязательно будут полными.

9 Ответ от Oleg

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: timus 1553

2MSDN: Композиция + segment tree сдается без проблем. Оптимизируй.

10 Ответ от shash

  • shash
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-15
  • Сообщений: 4

Re: timus 1553

KADR пишет:

Можно использовать Heavy-light декомпозицию. Сложность будет O(N*logN*logN). Почитать о ней можно здесь.

можно ссылку на русском, или скажите что мне гуглить
ЗЫ гугление в сторону "Heavy-light декомпозиция" нифига не дала

11 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: timus 1553

К сожалению, я не встречал описания этого метода на русском.

12 Ответ от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Re: timus 1553

Сдал! smile
Спасибо огромное всем. Баг тупой был у меня написал вместо N<<1 - 1<<N. Как оно до 17 теста доходила вообще непонятно.... smile