Список заданий по АиСД-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. Задан ориентированный граф, в каждой вершине записано число. Для каждой вершины $v$ найдите $f(v)$ — вершину с максимальным числом, которая достижима из $v$, за $O(E + V)$.

</wikitex>