Изменения
Нет описания правки
# Вероятностный алгоритм проверки некоторого предиката от входных данных размера $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)$.
# Обозначим как $up[v]$ число, в котором $i$-й бит равен $1$, если в $A(v)$ есть путь, заканчивающийся на расстоянии $i$ от корня. Считайте, что вы можете решить задачу о $m$ запросах $LCA$ в дереве с $n$ вершинами за $O(n+m)$ (например, используя алгоритм Фарах-Колтона и Бендера, см https://www.ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf). Объясните, как посчитать $up[v]$ за время $O(n+m)$.
