Список заданий по АиСД-year2015-сем2

<wikitex>

Алгоритмы и структуры данных, 2 семестр

1. Покажите, что если в сплей дереве при операции splay делать только операцию zig на всем пути до корня, то амортизированное время работы не $O(\log n)$.
2. Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось?
3. Докажите, что если сделать splay ко всем элементам в порядке возрастания ключа, то суммарное время работы будет $O(n)$.
4. Постройте дерево из хотя бы 7 вершин, которое после операции splay к одному из самых глубоких листьев становится бамбуком.
5. В пустое сплей-дерево были добавлены элементы в таком порядке: 30, 40, 60, 50, 80, 70. Какой элемент нужно добавить, чтобы дерево имело минимальную глубину? А какой, чтобы максимальную?
6. Пусть мы хотим хранить информацию только в листьях дерева, как нам использовать сплей-дерево для этого?
7. Предложите реализацию операции splay(v), если у вас нет ссылки на саму вершину $v$ и ссылок на родителя во всех вершинах, а известен только ее ключ, с $O(1)$ дополнительной памяти.
8. Задана строка длины $n$ из латинских букв и знаков вопроса. Посчитать число слов длины $n$ из букв латинского алфавита, в которых после согласной всегда идет гласная буква, которые можно получить заменой знаков вопроса во входной строке на буквы, за время $O(n)$.
9. Задано дерево, у каждой вершины есть вес. Нужно выбрать $k$ вершин суммарно максимального веса, чтобы никакие две соединенные ребром вершины не были выбраны.
10. Задана скобочная последовательность из нескольких видов скобок. Посчитайте минимальное число скобок, которое нужно вставить в эту последовательность, чтобы она стала правильной.
11. Задана последовательность чисел длины $n$, каждое число не больше $n$. Посчитайте число различных непустых подпоследовательностей последовательности за $O(n)$. Например, последовательность (1, 1, 2) содержит 5 подпоследовательностей: (1), (2), (1, 2), (1, 1), (1, 1, 2).
12. Посчитайте число различных двоичных деревьев из $n$ вершин.
13. Посчитайте число различных двоичных деревьев из $n$ вершин без порядка на детях.
14. Посчитайте число различных красно-черных деревьев из $n$ вершин.
15. Предложите алгоритм восстановления наибольшей возрастающей подпоследовательности по функции ДП, вычисление которой было предложено на лекции за $O(n \log{n})$ с $O(n)$ дополнительной памяти.
16. Задана последовательность. Про каждое $i$ определите одно из трех: элемент $a_i$ не может входить ни в одну НВП, элемент $a_i$ входит хотя бы в одну НВП, элемент $a_i$ входит во все НВП за $O(n \log{n})$.
17. Заданы две последовательности $a$ и $b$. Подпоследовательность $c$ называется общей для $a$ и $b$, если $c$ является подпоследовательностью $a$ и подпоследовательностью $b$. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время $O(|a| \cdot |b|)$ и памятью $O((|a| + |b|) ^ {2 - \epsilon})$, для некоторого $\epsilon > 0$.
18. Задача о рюкзаке. Заданы $n$ предметов, для каждого известен вес $w_i$ и цены $p_i$. Вам нужно выбрать подмножество предметов суммарным весом не более $W$ с максимальной суммарной ценой. Найдите это подмножество за время $O(W \cdot n)$ и память $O(W)$.
19. Подпалиндромом последовательности будем называть подпоследовательность $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$, в которой для любого $j$ выполняется $a_{i_j} = a_{i_{k-j+1}}$. Докажите, что длина максимального подпалиндрома последовательности $a$ равна длине наибольшей общей подпоследовательности $a$ и $a^r$, где $a^r$ — это развернутая последовательность $a$ ($a^r_i = a_{|a| - i + 1}$).
20. Покажите, что если решить задачу о максимальном подпалиндроме, использовав алгоритм поиска наибольшей общей подпоследовательности, как в предыдущем задании, то алгоритм может выдать подпоследовательность, которая не является палиндромом. Предложите алгоритм, который находит максимальный подпалиндром последовательности $a$ за время и память $O(|a|^2)$.
21. $a$ — последовательность длины $n$ из различных чисел от 1 до $n$. Докажите, что произведение длин наибольшей возрастающей и наибольшей убывающей подпоследовательностей в $a$ не меньше $n$.
22. Заданы две последовательности $a$ и $b$. Числа в последовательности $a$ различны. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время и память $O((|a| + |b|) \log{(|a| + |b|)})$.
23. Заданы $n$ предметов, каждый весом $w_i$. Известно, что за один раз вы можете унести предметы, суммарным весом не более $S$. Какое минимальное число подходов вам нужно сделать, чтобы унести все предметы? Решать за $O(3^n)$.
24. Заданы $n$ различных натуральных чисел. Посчитать число перестановок этих чисел, что НОД любых двух соседних не меньше $d$ за $O(n^2 2^n)$.
25. Заданы $n$ предметов, каждый весом $w_i$. Известно, что за один раз вы можете унести предметы, суммарным весом не более $S$. Какое минимальное число подходов вам нужно сделать, чтобы унести все предметы? Решать за $O(2^n \cdot n)$.
26. Заданы натуральные $S$, $L$ и $R$. Сколько есть чисел $x$ ($L \le x \le R$) таких, что сумма цифр $x$ равна $S$ за $O(\log^2 R)$.
27. Заданы три строки из цифр и знаков вопроса $a$, $b$ и $c$. Сколько существует троек чисел $x$, $y$ и $z$, таких, что $x$ получается из $a$ заменой знаков вопроса на цифры, $y$ из $b$ и $z$ из $c$ аналогичным способом, и $x+y=z$ за время $O(\log(\max(|a|, |b|, |c|))$.
28. Петя проводит $n$ независимых экспериментов, известны вероятности $p_i$ успешности $i$-го эксперимента. Посчитайте матожидание квадрата числа успешных событий за время $O(n^2)$.
29. Заданы $n$ строк из цифр. Петя в случайном порядке эти строки склеивает, выбирая, каждую из перестановок равновероятно. Задано число $k$. С какой вероятностью Петино число делится на $k$, посчитать за время $O(2^n \cdot n \cdot k + \sum{|s_i|})$.
30. Есть $n$ монеток на прямой, координата $i$-й $x_i$ (все $x_i$ различны). У каждой монетки есть вес $w_i$. Монетки можно двигать в сторону уменьшения координаты по прямой, несколько монеток может быть в одной точке. Подвинуть монетку $i$ на единицу влево стоит $w_i$ денег. Задано число $k$ ($k < n$), нужно за минимальное количество денег подвигать монетки так, чтобы осталось ровно $k$ точек, в которых есть хотя бы одна монетка. Найдите это минимальное число денег за $O(nk \log{n})$.
31. $f_0 = 1$, $f_1 = 2$, $f_i = f_{i-1} + f_{i-2} + i$. Вычислите $f_n$ за $O(\log{n})$ арифметических операций.
32. $f_0 = 1$, $f_1 = 2$, $f_i = f_{i-1} + f_{i-2} + i^2$. Вычислите $f_n$ за $O(\log{n})$ арифметических операций.
33. Модифицируйте алгоритм возведения в степень, чтобы посчитать $\sum\limits_{i=1}^n A^i$, где $A$ матрица, не изменяя размер матрицы.
34. Кузнечик прыгает по прямой в положительном направлении и всегда находится только в целых точках. Изначально он стоит в точке с координатой 1. Если кузнечик стоит в точке $x$, то он может прыгнуть в точки $x+1, x+2, \ldots, x+k$, где $k$ — максимальное число такое, что $x$ делится на $2^{k-1}$. Вам задано число $n$. Найдите число способов кузнечику добраться до точки $n$ за $O(\log^\alpha{n})$ для некоторого $\alpha$.
35. Рассмотрим последовательность отрезков с целыми концами: $[l_1, r_2]$, $[l_2, r_2]$, $\ldots$, $[l_m, r_m]$ ($1 \le l_i \le r_i \le n$). Вам задан $x$ ($1 \le x \le n$), найдите число различных последовательностей отрезков, что никакой не вкладывается в другой и существует $i$, что $l_i=x$, за время $O((nm)^\frac{3}{2})$.
36. Задано дерево из $n$ вершин. На каждом ребре записан один бит. Нам известно про каждое ребро, нужно ли оставить тот же бит или изменить на противоположный. На каждом шаге разрешается выбирать путь в дереве и изменять все биты на этом пути на противоположные. Какое минимальное число путей нужно выбрать, чтобы получить из начальной конфигурации битов конечную за $O(n^2)$.
37. Докажите парадокс дней рождений: было выбрано $n$ случайных целых чисел от 1 до $m$, для того, чтобы вероятность, что хотя бы два из $n$ чисел совпадут, была больше $\frac{1}{2}$, требуется $n > C \sqrt{m}$, для некоторого $C$.
38. Предложите алгоритм удаления элемента из хеш-таблицы с открытой адресацией, все операции все еще должны работать за $O(1)$.
39. Предложите алгоритм удаления элемента из хеш-таблицы с открытой адресацией такой, что число занятых ячеек всегда равно числу элементов в хеш-таблице, все операции все еще должны работать за $O(1)$.
40. Пусть при хешировании используется разрешение конфликтов с открытой адресацией линейным проходом, размер хеш-пространства равен $cn$, где $n$ — число элементов. Оцените среднюю длину кластера (участка из подряд идущих занятых ячеек)
41. Докажите, что конструкция семейства $H = \{ (ax + b) \bmod p \bmod m \}$, где случайно выбираются $a$ и $b$, $0 < a, b < p$, является универсальным семейством хеш-функций.
42. Универсальное семейство $H$ хеш функций обладает свойством попарной независимости, если для любых двух злементов $x$ и $y$ и любых двух хеш-значений $a$ и $b$ вероятность того, что $h(x) = a$ и $h(x) = b$ есть $1/m^2 + o(1 / m^2)$ (вероятность берется по случайному выбору хеш-функции из множества $H$). Докажите, что семейство из предыдущего задания обладает этим свойством.
43. Докажите, что если в ориентированном графе существует цикл, то в алгоритме dfs мы попытаемся пойти в серую вершину.
44. Решите задачу: есть $n$ гирек разного веса. Сделали $m$ взвешиваний на чашечных весах: по одной гирьке на каждой чаше. Известны результаты этих взвешиваний. Определите какой-нибудь порядок гирек, который не противоречит результатам взвешивания за $O(n + m)$.
45. Решите задачу: есть $n$ гирек разного веса. Сделали $m$ взвешиваний по порядку на чашечных весах: по одной гирьке на каждой чаше. Известны возможные результаты этих взвешиваний, возможно, некоторые из них некорректные. Определите, после какого из взвешиваний, полученная информация стала противоречивой за $O((n + m) \log n)$.
46. У вас есть $n$ дел, а также некоторые дела зависят от других: их нельзя сделать раньше тех, от которых зависят. Граф зависимостей дел не имеет циклов. Каждое дело занимает у вас один час. Известно дело под номером $x$, которое является очень важным. Определите порядок выполнения всех дел, чтобы то, которое под номером $x$, было выполнено как можно раньше, за линейное от размера входных данных время.
47. Предложите алгоритм, который находит лексикографически минимальную топологическую сортировку за $O((V + E) \log V)$.
48. Предложите алгоритм, который находит топологическую сортировку, у которой обратная перестановка минимальна лексикографически за $O((E + V) \log V)$.
49. Предложите алгоритм, который добавляет в граф не более $k$ ребер, чтобы лексикографически минимальная топологическая сортировка была максимальна за $O((E + V) \log V)$.
50. Предложите алгоритм, который находит в ацикличном ориентированном графе какой-нибудь путь, который проходит по каждой вершине ровно один раз за $O(E + V)$.
51. Предложите алгоритм, который проверяет, что в ориентированном графе для любой пары вершин $(v, u)$ существует как путь из $v$ в $u$, так и путь из $u$ в $v$, за $O(E + V)$.
52. Задан ориентированный граф, у каждой вершины исходящая степень равна 1. У каждого ребра есть вес. Вы забыли про ориентацию ребер, найдите паросочетание максимального веса за $O(E + V)$.
53. Предложите алгоритм, который добавляет в ацикличный ориентированный граф ровно одно ребро, чтобы он остался ацикличным, так, чтобы максимальный по длине путь был как можно длиннее за $O(V^2 + E)$.
54. Задан ориентированный граф. В вершинах записаны числа от 1 до $|V|$, все различные. Профилем вершины назовем следующую последовательность: возьмем все вершины достижимые из нее, все числа записанные на этих вершинах и упорядочим. Отсортируйте вершины по профилю лексикографически за $O(E + V)$.
55. Задан ацикличный ориентированный граф. Удалите в нем одно ребро, чтобы число простых путей в графе стало как можно меньше за $O(E + V)$.
56. Задан ориентированный граф, в каждой вершине записано число. Для каждой вершины $v$ найдите $f(v)$ — вершину с максимальным числом, которая достижима из $v$, за $O(E + V)$.
57. Задан неориентированный граф. Покрасьте граф в два цвета, чтобы число вершин первого цвета было равно числу вершин второго цвета за $O(V^2+E)$.
58. Задан неориентированный граф. На каждом ребре записан бит 0 или 1. В каждой вершине расположена кнопка, нажав на которую, меняют значения все биты на ребрах, инцидентных данной вершине. Вычислите, за какое минимальное число нажатий на кнопку биты на всех ребрах окажутся равны нулю, за $O(E + V)$.
59. Задан ориентированный граф улиц в городе. Нужно поставить полицейские станции в вершинах. Всего нужно поставить ровно $k$ станций так, чтобы из каждой вершины была достижима хотя бы одна станция и каждая вершина была достижима из хотя бы одной станции. Выведите число способов поставить $k$ станций в $k$ различных вершин за $O(E + V)$.
60. Задан неориентированный граф, степень каждой вершины не больше двух. Найдите минимальное вершинное покрытие в графе за $O(E + V)$.
61. Задан несильносвязный турнир. Турнир — ориентированный граф, в котором между любыми двумя вершинами есть ровно одно ребро, либо в одну сторону, либо в другую. Найдите число способов развернуть одно ребро так, чтобы все вершины стали сильносвязными за $O(V^2)$.
62. Приведите пример графа с отрицательными рёбрами, но без отрицательных циклов, на котором алгоритм Дейкстры работает неверно.
63. Есть взвешенный граф, где веса ребер, исходящих из одной вершины, одинаковы. Докажите, что алгоритм Дейкстры, реализованный с помощью двоичной кучи, будет работать за $O(V\log{V} + E)$
64. Модифицируем алгоритм Дейкстры следующим образом: будем вместо приоритетной очереди использовать FIFO-очередь. Если при релаксации до вершины, которая уже была в очереди, расстояние улучшается, добавим ее снова в очередь. Докажите, что полученный алгоритм ищет кратчайшие пути в графе за $O(VE)$.
65. Укажите способ построить для некоторых $c_1, c_2 >0$ и любых V, E, где $c_1 V \le E \le c_2 V^2$ граф, на котором алгоритм из предыдущего задания работает за $\Omega(VE)$.
66. Предложите граф, в котором алгоритм Дейкстры делает $\Omega(E)$ успешных релаксаций
67. Предложите алгоритм поиска цикла "почти" минимального среднего веса (отношение суммы весов ребер и числа ребер) за $O(VE \log{\frac{1}{\epsilon}})$, средний вес цикла должен отличаться от оптимального не более чем на $\epsilon$.
68. Доказать, что дерево $T$ является MST (здесь и далее MST - минимальное остовное дерево) тогда и только тогда, когда для любого ребра $uv \not\in T$ это ребро максимальное по весу на единственном цикле в графе $T \cup uv$. (Критерий Тарьяна)
69. Рассмотрим все остовные деревья графа, отсортируем их по весу. Предложите алгоритм, который выдаст вес второго MST в этом списке за $O(E \log{V})$.
70. Рассмотрим граф, вершины которого — остовные деревья $G$, а ребро между деревьями $T_1$ и $T_2$ существует, если $T_1$ получается из $T_2$ добавлением одного ребра и удалением другого. В нём рассмотрим подграф, состоящий только из $MST$. Доказать, что он связен.
71. Предложите алгоритм поиска всех ребер, которые лежат хотя бы в одном MST за $O(E \log{V})$.
72. Предложите алгоритм поиска всех ребер, которые лежат во всех MST за $O(E \log{V})$.

</wikitex>