Изменения
Нет описания правки
# Вероятностный алгоритм проверки некоторого предиката от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $1/2$. Можно ли найти верный ответ с вероятностью $99/100$ за полином от $n$?
# Вероятностный алгоритм проверки некоторого предиката от входных данных размера $n$ работает за полином $p(n)$ и дает верный ответ с вероятностью $2/3$. Как найти верный ответ с вероятностью $99/100$ за полином от $n$?
# В алгоритме Кинг с лекции обозначим как $f(u)$ лист, которая получается в ветвящемся дереве $T'$ из вершины $u$ в исходном дереве $T$. Докажите, что если вес максимального ребра на пути из $u$ в $v$ в $T$ равен $x$, а вес максимального ребра на пути из $f(u)$ в $f(v)$ в $T'$ равен $x'$, то $x \ge x'$.
# В условиях предыдущей задачи докажите, что то $x \le x'$.
# Рассмотрим ветвящееся дерево, пусть в нем $n$ вершин. Пусть есть $m$ запросов на пары листьев, для которых необходимо найти максимальное ребро на пути. Разобьем каждый запрос на два запроса на вертикальном пути до $LCA$ этих листьев, таким образом имеем $2m$ вертикальных путей. Для вершины $v$ обозначим как $A(v)$ множество вертикальных путей, проходящих через $v$. Обозначим как $D_i$ множество вершин на расстоянии $i$ от корня, как $d_i$ число вершин на расстоянии $i$ от корня ($d_i=|D_i|$). Докажите, что $\sum\limits_{u\in D_i}\lceil\log(1+|A(u)|)\rceil<\sum\limits_{u\in D_i}\left(1+\log(1+|A(u)|)\right)\le d_i+d_i \log\frac{d_i+2m}{d_i}$.
# В условиях предыдущей задачи докажите, что $\sum\limits_{i\ge 0}\left(d_i + d_i\log\frac{d_i+2m}{d_i}\right)\le n+n\log\frac{n+2m}{n}+2n$.
# Докажите, что $\sum\limits_{м}\lceil\log(1+|A(u)|)\rceil = O(n + m)$.
# Обозначим как $A[v]$ число, в котором $i$-й бит равен $1$, если в $A(v)$ есть путь, заканчивающийся на расстоянии $i$ от корня. Считайте, что вы можете решить задачу о $m$ запросах $LCA$ в дереве с $n$ вершинами за $O(n+m)$ (например, используя алгоритм Фарах-Колтона и Бендера, см https://www.ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf). Объясните, как посчитать $A[v]$ за время $O(n+m)$.
# Назовем вершину $v$ большой, если $|A(v)| > \log n/\log\log n$ и маленькой в противном случае. Докажите, что число больших вершин не превышает $m \log\log n/\log n$. Указание: оцените число больших вершин на каждом уровне дерева. Отдельно рассмотрите большие вершины на нижних $\log\log n$ и на остальных уровнях.
# Для вершины $v$, для которой $|A(v) = k$ будем хранить $B(v) = [l_1, l_2, \ldots, l_k]$ - список глубин самых тяжелых ребер на путях, проходящих через $v$, в порядке от самого длинного пути к самому короткому. Иначе говоря, пронумеруем пути из $A(v)$ в порядке возрастания глубины их верхней вершины. Тогда $l_i$ - расстояние от корня до ребра, которое является самым тяжелым на пути до некоторой вершины $u_i$, которая является верхним концом $i$-го пути. Числа $l_i$ называются тагами, длина тага $O(\log\log n)$. Докажите, что массив $B(v)$ отсортирован по неубыванию.
# Пусть $p$ - родитель вершины $v$, как связаны массивы $B(p)$ и $B(v)$? Дайте подробное описание, используя, при необходимости, $A(p)$ и $A(v)$.
# Для больших вершин $B(v)$ помещается в $O(\log\log n)$ машинных слово. Пусть родитель вершины также большой. Предложите алгоритм пересчета $B(v)$ через $B(p)$, $A[p]$ и $A[v]$ за $O(\log\log n)$, перед этим можно выполнить общий для всех вершин предподсчет за $O(n+m)$.
# Обозначим как $bigp[v]$ максимальную глубину, на котором находится большой предок вершины $v$. Предложите алгоритм, как за построить массив $bigp$ за $O(n)$.
# Для маленьких вершин $B(v)$ помещается в машинное слово, однако вместо списка $B(v)$ будем хранить вспомогательный список $C(v)$, устроенный так. Если самое тяжелое ребро на $i$-м по глубине пути из $A(v)$ находится ниже, чем $bigp[v]$, то будем хранить просто $l_i$. Иначе будем хранить $z_i$ - номер $l_i$ в $B(bigp[v])$. Обозначим упакованный в машинное слово список $C(v)$ за $C[v]$. Предложите алгоритм пересчета $С[v]$ за $O(1)$, перед этим можно выполнить общий для всех вершин предподсчет за $O(n+m)$. Вы можете использовать посчитанные для родителей и предков $C[u]$, $B(u)$, $A[u]$, $bigp[u]$.
# Объедините результаты всех предыдущих заданий, чтобы получить алгоритм обработки $m$ запросов поиска максимального ребра на пути между двумя вершинами на дереве за $O(n+m)$.
