1632
правки
Изменения
м
# Дана строка $s$. Посчитать матрицу $A: ||a_ij|| = LCP(s[i .. n-1], s[j .. n-1])$; $i,j \ge 0$ за $O(|s|^2)$. (LCP - наибольший общий префикс двух строк)
# То же, что и в предыдущем задании, но для каждого фиксированного $i$ надо научиться получать строку с нуля за $O(|s|)$.
# Тандемный повтор - строка вида $a = bb$. Найти максимальный тандемный повтор за $O(n \log n)$, используя результат предыдущего задания. Указание: используйте алгоритм вида "разделяй и властвуй", разделите строку пополам, ответ либо лежит слева от точки деления, либо справа, либо пересекает ее.
# Обобщить алгоритм поиска наибольшей общей подстроки, если дано $k$ строк. Указание: используйте очередь c операцией минимум. Время работы равно $SA + O(\sum |p_i|)$, где $p_1$, $p_2$, ..., $p_k$ - заданные строки.# Пусть $B(S)$ - множество бордеров $S$. Найти за $SA + O(n)$ сумму $\sum\limits_{i = 1}^{n} \sum\limits_{j = i}^{n} B(S[i..j])$.
rollbackEdits.php mass rollback
# Как найти строку длины $m$ в строке длины $n$ с использованием z-функции и O(m) дополнительной памяти?
# Задана строка. Пусть $p_1[i]$ - максимальная длина палиндрома нечетной длины с центром в позиции $i$. $p_0[i]$ - аналогично для четной длины. Модифицировать алгоритм поиска $z$-функции для построения $p_0$ и $p_1$.
# Дана строка $s$. Посчитать матрицу $A: ||a_{ij}|| = LCP(s[i .. n-1], s[j .. n-1])$; $i,j \ge 0$ за $O(|s|^2)$. (LCP - наибольший общий префикс двух строк)
# Докажите, что в конечном автомате для поиска подстроки в строке длины $n$ лишь $O(n)$ ребер ведут не в начальное состояние. Как это помогает сэкономить память?
# Алгоритм Саймона. Используя результат предыдущего задания, предложите алгоритм построения автомата за $O(n)$ (без множителя, зависящего от размера алфавита).
# Дана строка $s$. Посчитать число строк длины $L$, содержащих $s$ как подстроку. Время работы должно быть полиномом от длины $s$, и $L$.
# Дана строка $s$. Посчитать число строк длины $L$, содержащих $s$ как подстроку (по заданному модулю). Время работы должно быть полиномом от длины $s$, и $\log L$.
# Дана строка $s$. Посчитать число строк длины $l$, содержащих не менее $k$ вхождений $s$.
# Дана строка $s$. Посчитать число строк длины $l$, содержащих не менее $k$ непересекающихся вхождений $s$.
# Это и следующее задание доказывают линейность алгоритма Апостолико-Джанкарло. Будем обозначать закешированные значения наибольшего суффикса образца, который заканчивается в i-й позиции текста как suf[i]. Будем называть отрезок текста [i-suf[i]+1 - i] покрытым. Докажите, что любые два покрытых отрезка в процессе работы алгоритма либо вложены, либо не пересекаются.
# Используя результат предыдещего задания, докажите, что алгоритм Апостолико-Джанкарло работает линейное время.
# Докажите, что если строки s и t таковы, что st=ts, то найдется такая строка p, что $s=p^i$ и $t=p^j$ для некоторых i и j.
# Модифицировать алгоритм Ахо-Корасик так, чтобы не хранить все переходы, а только исходный бор и суффиксные ссылки, и время работы осталось прежним.
# Найти первые вхождения каждого из образцов в тексте за время O(длина текста + постр. автомата).
# Дано 2 бора A и B. Для всех вершин $u$ в $A$ найти самую глубокую вершину $v$ в $B$, соответствующую суффиксу $u$ (префикс-функция бора в боре). $O(|A| + |B|)$
# Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная вправо строка $t$, не содержащая $p_i$ как подстроки.
# Дан набор образцов $\{p_i\}$. Определить, существует ли бесконечная в две стороны строка $t$, не содержащая $p_i$ как подстроки.
# Дан набор образцов $\{p_i\}$. Посчитать число строк длины $l$, содержащих хотя бы одну из $p_i$ как подстроку. $O(\sum |p_i|\cdot l\cdot \sigma)$. ($\sigma$ - размер алфавита)
# Дано взвешенное дерево. Научиться отвечать на запросы "максимальное ребро на пути из $u$ в $v$" Для решения задачи модифицировать метод двоичного подъема ($O(n\log n)$ - предобработка, $O(\log n)$ - ответ на запрос).
# Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$". После предобработки за $O(n)$ ответ на запрос за $O(1)$.
# Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(d)$ памяти для каждой маски.
# Свести задачу RMQ к задаче LCA линейного размера (указание: использовать декартово дерево)
# Можно ли свести задачу RMQ к задаче RMQ$\pm 1$ так, чтобы размер получившегося массива был равен $n+C$, где $n$ - длина исходного массива, а $C$ - константа?
# Докажите, что число различных как строки подстрок $s$ равно $n(n + 1) / 2$ - sum(lcp[i]).
# Найти самую длинную строку $p$, такую, что она входит в строку $t$ дважды и не пересекаясь. Решение должно работать за $SA + O(n)$, где $SA$ - время построения суффиксного массива.
# Использовать суффиксный массив для нахождения такой строки $p$, что $|p| \times $(число вхождений $p$ в $t$) было максимальным за $SA + O(n)$
# Пусть в алфавите есть ровно два символа. Построить такую строку $s$, что её суффиксный массив совпадает с данным, за $O(n)$.
# Найти строку над алфавитом $\{0, 1\}$, в которой $\Omega(n^2)$ различных как строки подстрок.
# Строка $s$ называется ветвящейся вправо в $t$, если существуют символы $c$ и $d$, такие что $c \ne d$ : $sc$ и $sd$ - подстроки $t$. Аналогично, ветвящаяся влево, если $cs$ и $ds$ - подстроки $t$. Найти самую длинную ветвящуюся влево и вправо подстроку $t$ за $SA + O(n)$.
# Докажите теорему об аксиоматизации замыканиями.
# Будем называть предматроидом пару $\langle X, I \rangle$, для которой выполнены аксимомы нетривиальности ($\varnothing \in I$) и наследования независимости ($A \subset B$, $B \in I$, тогда $A \in I$). Пусть в предматроиде для любой весовой функции верно работает жадный алгоритм Радо-Эдмондса. Докажите, что такой предматроид является матроидом.
# Будем называть два элемента $x$ и $y$ матроида \emph{параллельными}, если пара $\{x, y\}$ образует цикл. Докажите, что если $A$ независимо $x \in A$, а $x$ и $y$ параллельны, то $A\setminus x\cup y$ также независимо.
# Рассмотрим носитель некоторого матроида, упорядочим произвольным образом его элементы: $X = \{x_1, x_2, \ldots, x_n\}$. Пусть $Y = \left\{x_k \,|\, rank(\{x_1, \ldots, x_{k-1}, x_k\}) > rank(\{x_1, \ldots, x_{k-1}\})\right\}$. Докажите, что $Y$ независимо.
# Приведите пример матроидаКакие универсальные матроиды являются матричными?# Докажите, который что матроид Вамоса не является бинарнымпредставимым ни над каким полем.# Приведите пример матроидаДокажите, который не что двойственный к матричному матроид является тернарнымматричным.Как устроена его матрица?# Приведите пример матроида, который не Когда двойственный к графовому матроид является изоморфен никакому матричному.графовым?
# Докажите лемму о паросочетании в графе замен (формулировка тут: [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9B%D0%B5%D0%BC%D0%BC%D0%B0_%D0%BE_%D0%BF%D0%B0%D1%80%D0%BE%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B8_%D0%B2_%D0%B3%D1%80%D0%B0%D1%84%D0%B5_%D0%B7%D0%B0%D0%BC%D0%B5%D0%BD], доказательство неправильное - неверный индукционный переход)
# Рассмотрим два матроида $M_1$ и $M_2$. Как связаны максимальное независимое множество пересечения $M_1 \cap M_2$ и база $M_1 \cup M_2^*$? ($M_2^*$ - матроид, двойственный $M_2$)
# Докажите теорему Радо: пусть $M$ - матроид с ранговой функцией $r$, $X = X_1 \cup X_2 \cup ...\cup X_k$, причем все $X_i$ попарно не пересекаются. Будем называть независимой системой представителей независимое множество $A$, такое что $|A \cap X_i| \le 1$. Пусть $A_{max}$ - максимальная по мощности независимая система представителей. Тогда $|A_{max}|=\min_{Z\subset \{1,..,k\}}(r(\cup_{i\in Z} X_i)+k-|Z|)$.
# Предложите алгоритм построения максимальной независимой системы представителей.
# Докажите, что длина кратчайшего пути из $S$ в $T$ в алгоритме построения базы пересечения матроидов не убывает.
# Докажите, что число различных длин кратчайшего пути из $S$ в $T$, которые встречаются в алгоритме построения базы пересечения матроидов, есть $O(\sqrt n)$.
# Докажите, что сумма длин кратчайших пути из $S$ в $T$, которые встречаются в алгоритме построения базы пересечения матроидов, есть $O(n \log n)$.
# Игра Шеннона. Рассмотрим игру на связном графе с множеством ребер $E$. Играют два игрока, cut и link, первым ходит cut. Игроки по очереди добавляют себе ребра, не использованные на предыдущих ходах. В конце игры link выигрывает, если по его ребрам можно дойти от любой вершины до любой. Докажите, что link выигрывает при оптимальной игре, если и только если в графе существует два непересекающихся остовных дерева.
# Игра Шеннона на произвольном матроиде. Рассмотрим игру на матроиде $M$. Играют два игрока, cut и link, первым ходит cut. Игроки по очереди выбирают себе элементы носителя, не использованные на предыдущих ходах. В конце игры link выигрывает, если его множество содержит базу матроида. Докажите, что link выигрывает при оптимальной игре, если и только если в графе существует две непересекающихся базы.
# Пусть $M$ - невырожденная квадратная матрица над вещественными числами. Докажите, что для любого множества строк $R$ найдется множество столбцов той же мощности $C$, что миноры $R\times C$ и $\overline{R}\times \overline{C}$ - ненулевые (как $\overline T$ обозначено множество строк/столбцов, не входящих в $T$).
# Задан двудольный граф, каждая вершина имеет вес. Требуется выбрать паросочетание, чтобы суммарный вес покрытых вершин был максимален. Решите эту задачу, не используя сведение к обычной задаче о назначениях.
</wikitex>
