Список заданий по АСД 2к 2016 весна

<wikitex>

1. Докажите лемму Галлаи: если при удалении любой вершины графа размер его максимального паросочетания не изменяется, то граф фактор-критический.
2. Докажите, что единственное множество Татта фактор-критического графа - пустое множество
3. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $D(G\setminus a)=D(G)$.
4. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $A(G\setminus a)=A(G)\setminus a$.
5. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $C(G\setminus a)=C(G)$.
6. Пусть вершина $a$ принадлежит множеству $A(G)$. Докажите, что $\alpha'(G\setminus a)=\alpha'(G)-1$ ($\alpha'(G)$ - размер максимального паросочетания в $G$).
7. Докажите теорему Галлаи-Эдмондса о структурной декомпозиции.
8. Рассмотрим двудольный граф, в качестве одной доли возьмем компоненты связности $D(G)$, а в качестве другой - вершины множества $A$. Соединим вершины ребром, если из соответствующей компоненты в соответствующую вершину есть хотя бы одно ребро. Докажите, что для любого множества $S$ вершин из $A(G)$ множество $N(S)$ содержит больше вершин, чем $S$.
9. Докажите, что любое ребро, соединяющее вершины из $D(G)$ и $A(G)$, лежит в некотором максимальном паросочетании в $G$.
10. Докажите, что любое ребро, соединяющее вершины из $C(G)$ и $A(G)$, не лежит ни в одном максимальном паросочетании в $G$.
11. Будем говорить, что доля $X$ двудольного графа имеет запас, если для любого непустого $S \subset X$ выполнено $|N(S)| > |S|$. Могут ли обе доли двудольного графа иметь запас?
12. Как устроена декомпозиции Галлаи-Эдмондса для двудольного графа, в котором одна из долей имеет запас?
13. Пусть $v \in C(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
14. Пусть $v \in D(G)$. Что можно сказать про декомпозицию Галлаи-Эдмондса графа $G \setminus v$?
15. Бордером строки называется строка, которая является одновременно ее префиксом и суффиксом. Периодом строки $s$ называется число $p$, такое что для всех допустимых $i$ выполнено $s[i+p]=s[i]$. Докажите, что если у строки длины $n$ есть border длины $k$, то у нее есть период $n - k$.
16. Докажите, что если у строки есть периоды $p$ и $q$, причем $p + q \le n$, то $gcd(p, q)$ также является периодом этой строки.
17. Что будет, если в предыдущем задании убрать условие $p + q \le n$?
18. Строки Фибоначчи. Определим $F_0 = \varepsilon$, $F_1 = b$, $F_2 = a$, $F_n = F_{n-1} F_{n-2}$. Докажите, что существует $k$ такое, что для $n \ge k$ выполнено $F_n^2$ - префикс $F_{n+2}$.
19. Докажите, что существует $k$ такое, что если $n \ge k$, то строка $F_n[1...|F_n|-2]$ - палиндром.
20. Определим строку Туе-Морса: $T_n = t_0t_1t_2...t_{2^n - 1}$, где $t_i = 0$, если двоичная запись числа $i$ содержит четное число единиц, и $t_i = 1$ в противном случае. Доказать, что не существует двух равных как строки подстрок строки $T_n$, имеющих пересекающиеся вхождения в $T_n$
21. Докажите, что для любого $u \ne \varepsilon$ и любого $n$ строка $u^3$ - не подстрока $T_n$
22. Разработать алгоритм восстановления строки по префикс-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен)
23. Разработать алгоритм восстановления строки по z-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен)
24. Разработать алгоритм восстановления строки по z-функции. ($O(n)$ или $O(n \log n)$, алфавит двоичный)
25. Вычислить $z$-функцию по префикс функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен, не прибегать к промежуточному представлению в виде строки)
26. Вычислить префикс функцию по $z$-функции. ($O(n)$ или $O(n \log n)$, алфавит неограничен, не прибегать к промежуточному представлению в виде строки)
27. Задана строка. Пусть $p_1[i]$ - максимальная длина палиндрома нечетной длины с центром в позиции $i$. $p_0[i]$ - аналогично для четной длины. Модифицировать алгоритм поиска $z$-функции для построения $p_0$ и $p_1$.
28. Разработайте алгоритм удаления строки из бора. После удаления бор не должен иметь "мертвых" поддеревьев, в которых нет помеченных вершин.
29. Модифицировать алгоритм Ахо-Корасик так, чтобы не хранить все переходы, а только исходный бор и суффиксные ссылки, и время работы осталось прежним.
30. Найти первые вхождения каждого из образцов в тексте за время O(длина текста + постр. автомата).
31. Найти число вхождений каждого из образцов в тексте за время O(длина текста + постр. автомата).
32. Найти последние вхождения каждого из образцов в тексте за время O(длина текста + постр. автомата). Текст подается по одному символу слева направо и у вас нет памяти, чтобы его сохранить.
33. Дано 2 бора A и B. Для всех вершин $u$ в $A$ найти самую глубокую вершину $v$ в $B$, соответствующую суффиксу $u$ (префикс-функция бора в боре). $O(|A| + |B|)$
34. Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная вправо строка $t$, не содержащая $p_i$ как подстроки.
35. Дан набор образцов $\{p_i\}$. Посчитать число строк длины $l$, содержащих хотя бы одну из $p_i$ как подстроку. $O(\sum |p_i|\cdot l\cdot \sigma)$. ($\sigma$ - размер алфавита)
36. Дана строка $s$. Посчитать матрицу $A: ||a_ij|| = LCP(s[i .. n-1], s[j .. n-1])$; $i,j \ge 0$ за $O(|s|^2)$. (LCP - наибольший общий префикс двух строк)
37. То же, что и в предыдущем задании, но для каждого фиксированного $i$ надо научиться получать строку с нуля за $O(|s|)$.
38. Тандемный повтор - строка вида $a = bb$. Найти максимальный тандемный повтор за $O(n \log n)$, используя результат предыдущего задания. Указание: используйте алгоритм вида "разделяй и властвуй", разделите строку пополам, ответ либо лежит слева от точки деления, либо справа, либо пересекает ее.
39. Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная в две стороны строка $t$, не содержащая $p_i$ как подстроки.
40. Докажите, что если строки s и t таковы, что st=ts, то найдется такая строка p, что $s=p^i$ и $t=p^j$ для некоторых i и j.
41. Дано взвешенное дерево. Научиться отвечать на запросы "максимальное ребро на пути из $u$ в $v$" Для решения задачи модифицировать метод двоичного подъема ($O(n\log n)$ - предобработка, $O(\log n)$ - ответ на запрос).
42. Дано взвешенное дерево. Научиться отвечать на запросы "максимальное ребро на пути из $u$ в $v$" $O(n)$ - предобработка, $O(1)$ - ответ на запрос).
43. Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$". После предобработки за $O(n)$ ответ на запрос за $O(1)$.
44. Дано дерево. Разбить вершины его на множество путей (каждая вершина принадлежит ровно одному пути), чтобы путь от любой вершины до любой переходил с одного пути на другой не более $O(\log n)$ раз.
45. Дано дерево. Рассмотрим покрытие его вершин путями по следующему алгоритму: из каждой нелистовой вершины включаем в множество ребро в наиболее глубокое поддерево. Решает ли этот алгоритм предыдущую задачу? Если нет, то какую точную оценку можно дать на число смены текущего пути?
46. Дано взвешенное дерево. Уметь отвечать на запросы "минимальное ребро на пути из $u$ в $v$" и "изменить весь ребра $uv$" за полином от логарифма.
47. Дано взвешенное дерево. Уметь отвечать на запросы "сумма ребер на пути из $u$ в $v$" и "изменить весь ребра $uv$" за $O(\log n)$.
48. Дан массив $a$. Посчитать массив $RMQ[i][j] = min(a[i] ... a[j])$ за $O(n^2)$.
49. Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(d)$ памяти для каждой маски.
50. Дано дерево. Научиться обрабатывать запросы "наименьший общий предок" и "добавить новый лист с родителем u", предподготовка $O(n \log n)$, запрос $O(\log n)$.
51. Дано дерево. Научиться обрабатывать запросы "наименьший общий предок" и "перевесить вершину u от ее текущего родителя к вершине v", предподготовка $O(n \log n)$, запрос $O(\log n)$.
52. Докажите, что число различных как строки подстрок $s$ равно $n(n + 1) / 2$ - sum(lcp[i]).
53. Найти самую длинную строку $p$, такую, что она входит в строку $t$ дважды и не пересекаясь. Решение должно работать за $SA + O(n)$, где $SA$ - время построения суффиксного массива.
54. Использовать суффиксный массив для нахождения такой строки $p$, что $|p| \times $(число вхождений $p$ в $t$) было максимальным за $SA + O(n)$
55. Пусть в алфавите есть ровно два символа. Построить такую строку $s$, что её суффиксный массив совпадает с данным, за $O(n)$.
56. Дано две строки $s$ и $t$. Найти их наибольшую общую подстроку за $SA + O(|s| + |t|)$.
57. Обобщить алгоритм поиска наибольшей общей подстроки, если дано $k$ строк. Указание: используйте очередь c операцией минимум. Время работы равно $SA + O(\sum |p_i|)$, где $p_1$, $p_2$, ..., $p_k$ - заданные строки.
58. Пусть $B(S)$ - множество бордеров $S$. Найти за $SA + O(n)$ сумму $\sum\limits_{i = 1}^{n} \sum\limits_{j = i}^{n} B(S[i..j])$.
59. Найти строку над алфавитом $\{0, 1\}$, в которой $\Omega(n^2)$ различных как строки подстрок.
60. Строка $s$ называется ветвящейся вправо в $t$, если существуют символы $c$ и $d$, такие что $c \ne d$ : $sc$ и $sd$ - подстроки $t$. Аналогично, ветвящаяся влево, если $cs$ и $ds$ - подстроки $t$. Найти самую длинную ветвящуюся влево и вправо подстроку $t$ за $SA + O(n)$.
61. Найти количество ветвящихся влево и вправо строк для строки $t$. Считать только разные строки.
62. Строка $s$ называется максимальным повтором в $t$, если 1) $s$ входит в $t$ не менее двух раз; 2) если $r$ входит в $t$ не менее двух раз, то $s$ - не является собственной подстрокой $r$. Доказать или опровергнуть, что все максимальные повторы равны по длине.
63. Найти все максимальные повторы за $O(SA + n + ans)$.
64. Петя забыл про спуск по счетчику в алгоритме Укконена. Привести пример строки, на которой полученный алгоритм будет работать дольше чем за $O(n)$.
65. Привести пример, когда в алгоритме Укконена в одной итерации спуск происходит по $\Omega(n)$ реберам.
66. Построить суффиксный массив по суффиксному дереву за $O(n)$.
67. Построить суффиксное дерево по суффиксному массиву за $O(n)$.
68. Определить число различных подстрок в строке с помощью суффиксного дерева за $ST + O(n)$. ($ST$ - время построения суффиксного дерева, суффиксный массив не использовать)
69. Использовать суффиксный массив для нахождения такой строки $p$, что $|p| \times $(число вхождений $p$ в $t$) было максимальным за $ST + O(n)$
70. Найти максимальную подстроку в строке, имеющую два непересекающихся вхождения за $ST + O(n)$.
71. Найти строку максимальной длины, ветвящаяся влево и вправо за $ST + O(n)$.
72. Найти подпалиндром максимальной длины за ST + O(n).
73. Алгоритм Хьюи. Дано дерево, вершины которого раскрашенны в цвета, то есть задано отображение $col: V \to \{1..k\}$. С помощью LCA найти $dc: V \to \{1..k\}$, где $dc(u)$ - число различных цветов в поддереве с корнем в вершине $u$. Время работы - $O(DCU)$.
74. Используя результат предыдущей задачи, найти наибольшую общую подстроку $k$ строк за $O(n + DSU)$.
75. Найти наибольший общий подпалиндром за $ST + O(DSU)$.
76. Найти наибольший максимальный повтор за $ST + O(n)$.
77. $1 | p_i = 1, d_i | \sum U_i$. Время $O(n)$.
78. $1 | p_i = 1, d_i | \sum w_iU_i$. Время $O(n\log n)$.
79. $1 | p_i = 1, d_i, r_i | \sum U_i$. Время - полином от $n$.
80. $1 | p_i = 1, d_i, r_i | \sum w_iU_i$. Время - полином от $n$.
81. Обозначение prec означает, что есть ациклический граф зависимостей между работами. Пусть $f(x)$ - произвольная неубывающая функция. Обозначим как $f_{max}$ величину $\max(C_i)$. $1 | prec, p_i = 1, r_i | f_{max}$
82. Обозначение pmtn означает, что работу можно прервать, а затем продолжить ее выполнение. $1 | pmtn, prec, r_i | f_{max}$
83. $1 | p_i = p, pmtn, r_i | \sum w_iU_i$ за $O(n^{10})$.
84. $1 | r_i, pmtn | \sum C_i$
85. $1 | r_i, p_i = p | \sum w_iC_i$ за $O(n^7)$
86. $1 | r_i, p_i = 1 | \sum f_i$
87. Обозначение outtree означает, что граф зависимостей представляет собой исходящее дерево: каджая работа зависит не более чем от одной другой. $1 | outtree | \sum w_iC_i$
88. Обозначение intree означает, что граф зависимостей представляет собой входящее дерево: от каждой работы зависит не более одной другой. $1 | intree | \sum w_iC_i$
89. $R || Sum(C_i)$
90. $P | pmtn, r_i | C_{max}$
91. $Q | pmtn, r_i | C_{max}$
92. $P | p_i = p, r_i, d_i | \sum C_i$ за $O(n^3 \log\log n)$
93. $P | p_i = 1 | \sum w_iU_i$
94. $P | p_i = 1 | \sum w_iC_i$
95. $Q | pmtn | \sum C_i$
96. $P2 | p_i = 1, prec, r_i | \sum C_i$ за $O(n^9)$
97. $F | p_{ij} = 1 | \sum C_i$
98. $F2 | pmtn | C_{max}$
99. $F | p_{ij} = 1 | \sum U_i$
100. $F | p_{ij} = 1 | \sum w_iU_i$
101. $O | p_{ij} = 1 | C_{max}$
102. $O | p_{ij} = 1 | \sum C_i$
103. $O | p_{ij} = 1 | \sum w_iC_i$
104. $O | p_{ij} = 1, d_i | -$
105. $O | p_{ij} = 1 | \sum u_i$
106. $O | p_{ij} = 1 | \sum w_iU_i$
107. $O | p_{ij} = 1, r_i | C_{max}$
108. $O2 | p_{ij} = 1, prec | \sum C_i$

</wikitex>