WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«Практика по алгоритмам HLD, Euler-Tour-Tree 14 марта Собрано 10 мая 2016 г. в 18:15 Содержание 1. Задачи на тему HLD, Euler-Tour-Tree 1 2. Разбор задач практики 3 3. Домашнее задание 6 3.1. ...»

Первый курс, весенний семестр 2015/16

#6

Практика по алгоритмам

HLD, Euler-Tour-Tree

14 марта

Собрано 10 мая 2016 г. в 18:15

Содержание

1. Задачи на тему HLD, Euler-Tour-Tree 1

2. Разбор задач практики 3

3. Домашнее задание 6

3.1. Обязательная часть..................................... 6

3.2. Дополнительная часть................................... 6

4. Разбор домашнего задания 7

4.1. Обязательная часть..................................... 7

4.2. Дополнительная часть................................... 8 Практика #6. HLD, Euler-Tour-Tree .

Алгоритмы, весна 2015/16 Задачи на тему HLD, Euler-Tour-Tree

1. Минимум на пути меняющегося дерева

Дано дерево с весами на ребрах, надо эффективно обрабатывать запросы:

a) min(, ) – минимум на пути из вершины в вершину .

set(, ) – присвоение ребру веса .

b) min(, ) – минимум на пути из вершины в вершину .

add(,, ) – прибавление числа к весам всех ребер на пути из вершины в вершину .

2. Ближайший хороший предок Дано дерево с весами в вершинах. Веса из {0, 1} .

a) Запросы: сделать вес вершины равным 1, найти ближайшого предка с весом 0 .

b) Запросы: сделать вес вершины равным 1, найти ближайшого предка с весом 1 .



c) Запросы: изменить вес вершины, найти ближайшего предка с заданным весом .

d) Веса из N. Запросы: изменить вес вершины, найти ближайшего предка с заданным весом .

e) Веса из N. Запросы: присвоить вес вершины, по найти ближайшего предка с весом .

3. Число тяжелых вершин на пути Дерево с весами в вершинах. Нужно научиться отвечать на запрос count(,, ) – количество вершин на пути из в, у которых вес, если:

a) Веса не меняются. (log ) .

b) Теперь веса меняются. Запрос за (log3 ), изменение веса за (log2 ) .

c) (*) Веса меняются. Эйлеров обход. (log2 ) .

4. Добавление листьев в HLD Придумайте модификацию Heavy-Light-Decomposition, поддерживающую добавлении новых листьев .

a) ( ) на добавление листа, ( + log2 ) на запрос get .

b) Добавление за (log2 ). Подсказка: мы хотим быстро split-ить и merge-ить пути .

5. Link-cut-sum Дан лес с положительными целочисленными весами на ребрах. Используя Euler-Tour-Tree научитесь обабатывать следующие запросы:

a) link(,, ) – подвесить корень одного дерева к вершине другого ребром веса

b) cut(, ) – удалить ребро

c) sum(, ) – сумма весов рёбер на пути Все запросы нужно обрабатывать за (log ) .

–  –  –

6. (*) Дерево namespace-ов Дано дерево вложенности изначально пустых namespace-ов. Чтобы, находясь в вершине дерева, узнать значение переменной, нужно подниматься по дереву, пока не попадём в вершину, где определена. Все переменные в задаче булевы. Запросы:

a) set(,, ) – присвоить в пространстве имён переменной с именем значение .

b) count() – посчитать, во скольких пространствах имен-листьях переменная с именем имеет значение true, false и во скольких не объявлена .

7. (*) Dynamic Connectivity Online Используя за основу Euler-Tour-Trees, придумайте online решение задачи dynamic connectivity за () на запроы cut, link, isConnected. Подсказка : при удаление ребра, если оно лежит в остове, нужно найти ему замену, при этом придётся перебрать рёбра-кандидаты, нужно перебрать поменьше рёбер-кандидатов и всем им уменьшить некий потенциал .



2/8 Практика #6. HLD, Euler-Tour-Tree .

Алгоритмы, весна 2015/16 Разбор задач практики

1. Минимум на пути меняющегося дерева Строим Heavy-Light-Decomposition (HLD), для каждого пути из HLD храним дерево отрезков на минимум. += тоже делаем через ДО. Получили решение за (), (log2 ). При этом изменение в точке за (log ), так как это обращение только к одному ДО .

2. Ближайший хороший предок

a) Сделать вес вершины 1, найти ближайшого предка с весом 0 В СНМ для каждого нуля храним все единицы, которые на него ссылаются .

setOne(v): DSU.p[v] = Tree.parent[v] или DSU.join(v, Tree.parent[v]) .

b) Сделать вес вершины 1, найти ближайшого предка с весом 1 Решение #1. Offline. Обрабатываем запросы с конца, получаем предыдущий пункт .

Решение #2. Online. HLD, для каждого пути HLD поддерживаем setint позиций всех единиц. setOne за (log ): в нужный setint добавить позицию вершины в пути. get за (log ): пока верхняя единица лежит ниже нашей вершины, поднимаемся к следующему пути. В последнем пути делаем lower_bound. Вершины в пути нумеруется сверху вниз .

int get(int v) { while (set[pathIndex[v]].empty() || *set[pathIndex[v]].begin() positionInPath[v]) v = parent[topVertex[pathIndex[v]]]; // O(1), O(log n) iterations auto it = set[pathIndex[v]].lower_bound(positionInPath[v]); // O(log n) return path[pathIndex[v]][*it]; // O(1) } Решение #3. Online. ДО на эйлеровом обходе вершин дерева. Если пометилась вершина, то всему поддереву присвоим как ближайшего помеченного предка. Поддерево – отрезок эйлерова обхода между первым и последним вхождением.

Присваивание хитрое:

при проталкивании информации вниз сохраняем в отрезке более глубокую вершину .

c) Изменить вес вершины, найти ближайшего предка с заданным весом .

Так же, как предыдущий пункт, setint нулей и setint единиц, при изменении перемещаем из одного set в другой .

d) Предыдущий пункт. Веса из N .

Для каждого веса храним свой Heavy-Light. Как сделать так, чтобы памяти не стало в раз больше? Все массивы поменять на unordered_map-ы .

e) Веса из N, менять вес вершины, находить ближайшего предка с весом .

HLD, для каждого пути HLD поддерживаем ДО на максимум, с его помощью уже умеем находить ближайший слева. Запрос обновления за (log ), просто изменение одного элемента в нужном ДО. Запрос get за (log2 ): прыгаем вверх по путям, пытаемся найти в каждом за (log ), пока не найдем. Получили решение за (), (log2 ) .

3. Число тяжелых вершин на пути

a) Static Разобьем запрос (, ) как запросы на путях до корня: +1 в, +1 в, -2 в lca(, ) .

Теперь в offline можно решить dfs-ом, обойдя дерево и поддерживая дерево отрезков, делая add() при спуске, del() при подъёме, это +1 и -1 к позиции. Запрос на пути до корня: count( ) (сумма на суффиксе). Время обработки всех запросов (( + ) log ) .





Как обычно, в online это переделывается использованием персистентного ДО .

Получили решение за ( log ), (log ) .

3/8 Практика #6. HLD, Euler-Tour-Tree .

Алгоритмы, весна 2015/16

b) Dynamic, (log3 ) HLD, для каждого пути HLD храним дерево отрезков Treap-ов .

Изменение за (log2 ), удаляем старый вес и добавляем новый в каждый treap, соответсвующий вершине ДО, покрывающего измененную вершину .

Запрос за (log3 ): в (log ) путях HLD выделяем вершины ДО, в каждой вершине делаем Split по весу .

c) Dynamic, (log2 ) Перенесем веса с вершин на ребра, соединяющие их с предком .

Поддерживаем Эйлеров обход на ребрах, для версии ребра вверх храним пару +1,, для версии вниз пару -1,. Для каждой вершины помним время выхода из – pos[] (длину Эйлерового обохода в момент выхода из ) .

На этом массиве строим ДО treap-ов, которое умеет по отрезку массива посчитать за (log2 ) сумму плюс-минус единиц на отрезке весов .

При изменении веса ребра, нам нужно поменять два элемента массива. Двумерное дерево обновляется за (log2 ) .

При запросе count(,, ) находим = lca(, ). count(, ) = sum(pos[], pos[],, +) + sum(pos[], pos[],, +). Почему сумма корректна? Пока мы идём по Эйлеровому обходу от pos[] до pos[], мы пройдём все рёбра пути из в вверх. Остальные рёбра, что мы пройдём, посчитаются два раза с разными знаками и сократятся в 0. Заметим, что, поскольку выше и, то max(pos[], pos[]) pos[] .

4. Добавление листьев в HLD

a) Отложенные операции. Когда добавляем лист, создаём путь из одной вершины. Как только листьев накопилось, за () перестраиваем HLD .

Можно сделать так, чтобы get работал за (log2 ), а не ( + log2 ). Для этого при каждом добавлении листа будем перестраивать HLD на кусочке из новых вершин .

b) Пути храним в деревьях по неявному ключу с операциями split и merge .

Когда добавили лист, на пути до корня увеличились размеры. Значит, тяжёлые рёбра остались тяжёлыми, а лёгкие могли стать тяжёлыми. Лёгких рёбер на пути не более (log ), перебираем их и, если нужно, делаем split старого пути и merge нового. Получили асимптотику (log2 ) на добавление листа .

Здесь надо уметь пересчитывать размеры поддеревьев при добавлени листа. Можно использовать решение из последнего ДЗ, а можно просто делать += на пути от листа до корня, используя уже имеющуюся HLD .

Кстати, если использовать splay tree, то и HLD, и добавление листьев работают за (log ) вместо (log2 ) .

5. Link-cut-sum Делать link и cut умеем .

При построении Эйлерового обхода ориентированных рёбер пишем на версии ребра вверх его вес, на версии ребра вниз его вес со знаком минус. Поскольку мы подвешиваем только корни деревьев, направления ребер не меняются .

При запросе sum берем сумму от до, и сумму от до, лишние рёбра посчитаются два раза с разными знаками и сократятся .

Для нахождения нужно искать вершину с минимальной глубиной на отрезке от до. При подвешивании и отрезании нужно делать += или -= соответствующей глубины на отрезке .

4/8 Практика #6. HLD, Euler-Tour-Tree .

Алгоритмы, весна 2015/16 Другое решение. Будем поддерживать для каждой вершины сумму на пути до корня .

При link и cut эти величины пересчитываются операциями += или -= на отрезке, соответствующем поддереву. искать также .

6. (*) Дерево namespace-ов См. разбор прошлого дз .

7. (*) Dynamic Connectivity Online Лекция профессора Эрика Демэйна

–  –  –

Домашнее задание

3.1. Обязательная часть 1. (3) Max отрезок без циклов Дан взвешенный неорграф. Найти максимальный по длине отрезок весов 0 такой, что множество рёбер с весами из [, ] не содержит циклов. (( + ) log ) .

2. (3) Статически оптимальный HLD Дано дерево с фиксированным корнем. Так же даны запросы на произвольных путях,. Нужно построить статически оптимальное покрытие дерева вертикальными путями. Оптимальное – в смысле, минимизируеющее общее число переходов между путями в течение ответов на все запросов .

3. (3) Доказать Expose в Link-Cut Пусть в Link-Cut-Tree для дерева из вершин мы несколько раз вызываем операцию Expose от произвольных вершин. Больше никаких операций не осуществляем. Докажите, что относительно потенциала = «количество тяжёлых рёбер, покрытых путями» амортизированное время работы Expose (log ). Можно предположить, что Split и Merge работают за (1) .

4. (3) MST за ( + ) Посмотрите внимательно на рандомизированный алгоритм построения MST за линейное время и докажите, что в худшем случае он работает за min(2, log ) .

3.2. Дополнительная часть

1. (3) Додоказать Link-Cut У нас уже доказана амортизированная сложность операции Expose. Осталось оценить MakeRoot, Link, Cut .

2. (4) Улучшенный Euler-Tour-Trees Придумайте модификацию Euler-Tour-Trees для хранения леса подвешенных деревьев, поддерживающую операции Link, Cut, MakeRoot, IsAncestor(a, b) .

3. (4) Алгоритм Вишкина и 4 русских Сделать таки (), (1) для LA! Напомним, мы уже увидели запрос на ±1 массиве, но не умеем его обрабатывать быстро .

–  –  –

Разбор домашнего задания

4.1. Обязательная часть

1. Max отрезок без циклов Отсортируем рёбра по весу. Два указателя. Правым добавляем ребро, пока его концы в разных компонентах (не создают цикл). Левым режем ребра, пока концы правого в одинаковых компонентах. Для добавления и удаления ребер и проверки принадлежности одной компоненте используем Euler Tour Trees. ( log ) .

2. Статически оптимальный HLD Для каждого ребра насчитаем, скольки путями оно покрыто. Для этого разобъем пути на пары вертикальных, в вертикальном пути ставим +1 в нижнюю вершину, -1 в верхнюю .

Число путей, покрывающих ребро, – сумма в поддереве .

Растим пути сверху вниз. При продолжении пути вниз выбираем ребро, покрытое max числом путей. () на всё .

3. Доказать Expose в Link-Cut Сделали Expose, на пути оказалось легких и тяжелых ребер. Тяжелое перестало покрываться, только если оно брат легкого из пути. Все тяжелых стали покрываться. .

= = + 2 2 log .

0 = 0,, | 0 | .

4. MST за ( + ) () = ( + ) + 2 ( ) = (2 ) + 2 ( ) = (2 ) .

Рекурсивные вызовы в худшем случае: (, ), (, + ) ( ребер уже после Борувки). За счет Борувки уйдет ребер, так что на каждом уровне рекурсии ребер будет обработано (изначального), уровней log8, итого ( log ) .

–  –  –

4.2. Дополнительная часть

1. Додоказать Link-Cut Проследим за изменением потенциала «число тяжелых ребер, покрытых путями». Про Expose уже доказано. Потенциал портится на столько, на сколько уменьшается число покрытых тяжелых ребер .

MakeRoot = Expose + Reverse. При Reverse какие-то покрытые тяжелые станут легкими, но на любом пути log легких. Для ребер вне развернутого пути ничего не меняется .

При Link к могут полегчать только какие-то ответвления из пути от корня до, но они все не покрыты за счет expose() .

При Cut могут полегчать только ребра на пути от корня до вершины, от которой оторвали ребенка, но на любом пути log легких .

2. Улучшенный Euler-Tour-Trees Кроме самого ETT храним для каждой вершины в дереве по неявному ключу – массив, в котором лежат ребра, смежные с, в том же порядке, что в ETT, но, возможно, циклически сдвинутые. Также помним для каждого ребра в его позицию в ETT. Понятно, как это всё пересчитывать при Link и Cut .

Для isAncestor(a, b) нужно определить, верно ли, что первое и последнее вхождение a между первым и последним вхождением b. Для этого надо правильно повернуть и .

Как правильно повернуть ? Для каждого ребра из можно узнать за (log ) его номер в ETT. Эти номера образуют циклический сдвиг отсортированного массива. Теперь бинпоиском по ищем позицию сдвига. Итого isAncestor(a, b) за (log2 ) .

3. Алгоритм Вишкина и 4 русских ?

8/8






Похожие работы:

«МУНИЦИПАЛЬНОЕ КАЗЕННОЕ ОБЩЕОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ "СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 17" ИМЕНИ ГЕРОЯ РОССИИ ШЕНДРИКА В.Г. Челябинская обл. г. Миасс, Проспект Автозаводцев 37 А, 456300 тел./факс 55-46-93 ОКПО 14...»

«Коррекция интернет-аддикций подростков посредством тренинга социальных навыков / Е.В. Жихарева, Е.В. Маликова // Образовательная среда сегодня: теория и практика: материалы VI Международной научно-практической конференции (Чебоксары, 2 ноября 2018г.). – Чебоксары: ЦНС "Интерактив плюс...»

«Современный взгляд на использование наглядности как опоры при обучении говорению на уроке французского языка в начальной школе Бочарова Анастасия Владимировна, учитель французского языка ГБОУ гимназии 171 Центрального районаСанкт-Петербурга В совре...»

«"Наука и образование: новое время" № 2, 2016 Почтарева Елена Андреевна, студентка, филологический факультет, кафедра иностранных языков, 3 курс, Лесосибирский педагогический институт – филиал ФГАОУ ВПО "Сибирский феде...»

«Муниципальное бюджетное общеобразовательное учреждение "Центр образования села Канчалан"Рассмотрено и принято: УТВЕРЖДЕНО: Педагогическим советом МБОУ Директор МБОУ "Центр образования с.Канчалан" "Центр образования с.Канчалан" Протокол № 9 от 29.08.2017 г. Ляховская С.Г. 29.08. 2017 г. Введено в действие приказом № 84-О от 29.08.2017 РАБО...»

«Сообщение о существенном факте “Об отдельных решениях, принятых советом директоров (наблюдательным советом) эмитента” 1. Общие сведения 1.1. Полное фирменное наименование эмитента Публичное акционерное общество "Аэрофлот – (для некоммерческой органи...»

«Сергей Воздвиженский Скаутский метод в развитии международного молодёжного сотрудничества Проект ТАСИС "Электронная сеть Карельской молодёжи" CBC-SPF, Karelian Youth Network, 0302/0020, 031-900 Отдел по делам молодёжи города Йоенсуу, Финляндия Отдел по делам молодёжи администрации...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.