Список заданий по АиСД-year2015-сем2 — различия между версиями
| Строка 17: | Строка 17: | ||
# Предложите алгоритм восстановления наибольшей возрастающей подпоследовательности по функции ДП, вычисление которой было предложено на лекции за $O(n \log{n})$ с $O(n)$ дополнительной памяти. | # Предложите алгоритм восстановления наибольшей возрастающей подпоследовательности по функции ДП, вычисление которой было предложено на лекции за $O(n \log{n})$ с $O(n)$ дополнительной памяти. | ||
# Задана последовательность. Про каждое $i$ определите одно из трех: элемент $a_i$ не может входить ни в одну НВП, элемент $a_i$ входит хотя бы в одну НВП, элемент $a_i$ входит во все НВП за $O(n \log{n})$. | # Задана последовательность. Про каждое $i$ определите одно из трех: элемент $a_i$ не может входить ни в одну НВП, элемент $a_i$ входит хотя бы в одну НВП, элемент $a_i$ входит во все НВП за $O(n \log{n})$. | ||
| − | # Заданы две последовательности $a$ и $b$. Подпоследовательность $c$ называется общей для $a$ и $b$, если $c$ является подпоследовательностью $a$ и подпоследовательностью $b$. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время $O(|a| \cdot |b|)$ и памятью $ | + | # Заданы две последовательности $a$ и $b$. Подпоследовательность $c$ называется общей для $a$ и $b$, если $c$ является подпоследовательностью $a$ и подпоследовательностью $b$. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время $O(|a| \cdot |b|)$ и памятью $O((|a| + |b|) ^ {2 - \epsilon})$, для некоторого $\epsilon > 0$. |
# Задача о рюкзаке. Заданы $n$ предметов, для каждого известен вес $w_i$ и цены $p_i$. Вам нужно выбрать подмножество предметов суммарным весом не более $W$ с максимальной суммарной ценой. Найдите это подмножество за время $O(W \cdot n)$ и память $O(W)$. | # Задача о рюкзаке. Заданы $n$ предметов, для каждого известен вес $w_i$ и цены $p_i$. Вам нужно выбрать подмножество предметов суммарным весом не более $W$ с максимальной суммарной ценой. Найдите это подмножество за время $O(W \cdot n)$ и память $O(W)$. | ||
# Подпалиндромом последовательности будем называть подпоследовательность $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}$). | # Подпалиндромом последовательности будем называть подпоследовательность $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}$). | ||
# Покажите, что если решить задачу о максимальном подпалиндроме, использовав алгоритм поиска наибольшей общей подпоследовательности, как в предыдущем задании, то алгоритм может выдать подпоследовательность, которая не является палиндромом. Предложите алгоритм, который находит максимальный подпалиндром последовательности $a$ за время и память $O(|a|^2)$. | # Покажите, что если решить задачу о максимальном подпалиндроме, использовав алгоритм поиска наибольшей общей подпоследовательности, как в предыдущем задании, то алгоритм может выдать подпоследовательность, которая не является палиндромом. Предложите алгоритм, который находит максимальный подпалиндром последовательности $a$ за время и память $O(|a|^2)$. | ||
# $a$ {{---}} последовательность длины $n$ из различных чисел от 1 до $n$. Докажите, что произведение длин наибольшей возрастающей и наибольшей убывающей подпоследовательностей в $a$ не меньше $n$. | # $a$ {{---}} последовательность длины $n$ из различных чисел от 1 до $n$. Докажите, что произведение длин наибольшей возрастающей и наибольшей убывающей подпоследовательностей в $a$ не меньше $n$. | ||
| − | # Заданы две последовательности $a$ и $b$. Числа в последовательности $a$ различны. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время и память $O(|a| + |b|)$. | + | # Заданы две последовательности $a$ и $b$. Числа в последовательности $a$ различны. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время и память $O((|a| + |b|) \log{(|a| + |b|)})$. |
# Заданы $n$ предметов, каждый весом $w_i$. Известно, что за один раз вы можете унести предметы, суммарным весом не более $S$. Какое минимальное число подходов вам нужно сделать, чтобы унести все предметы? Решать за $O(3^n)$. | # Заданы $n$ предметов, каждый весом $w_i$. Известно, что за один раз вы можете унести предметы, суммарным весом не более $S$. Какое минимальное число подходов вам нужно сделать, чтобы унести все предметы? Решать за $O(3^n)$. | ||
# Заданы $n$ различных натуральных чисел. Посчитать число перестановок этих чисел, что НОД любых двух соседних не меньше $d$ за $O(n^2 2^n)$. | # Заданы $n$ различных натуральных чисел. Посчитать число перестановок этих чисел, что НОД любых двух соседних не меньше $d$ за $O(n^2 2^n)$. | ||
</wikitex> | </wikitex> | ||
Версия 12:50, 9 марта 2016
<wikitex>
Алгоритмы и структуры данных, 2 семестр
- Покажите, что если в сплей дереве при операции splay делать только операцию zig на всем пути до корня, то амортизированное время работы не $O(\log n)$.
- Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось?
- Докажите, что если сделать splay ко всем элементам в порядке возрастания ключа, то суммарное время работы будет $O(n)$.
- Постройте дерево из хотя бы 7 вершин, которое после операции splay к одному из самых глубоких листьев становится бамбуком.
- В пустое сплей-дерево были добавлены элементы в таком порядке: 30, 40, 60, 50, 80, 70. Какой элемент нужно добавить, чтобы дерево имело минимальную глубину? А какой, чтобы максимальную?
- Пусть мы хотим хранить информацию только в листьях дерева, как нам использовать сплей-дерево для этого?
- Предложите реализацию операции splay(v), если у вас нет ссылки на саму вершину $v$ и ссылок на родителя во всех вершинах, а известен только ее ключ, с $O(1)$ дополнительной памяти.
- Задана строка длины $n$ из латинских букв и знаков вопроса. Посчитать число слов длины $n$ из букв латинского алфавита, в которых после согласной всегда идет гласная буква, которые можно получить заменой знаков вопроса во входной строке на буквы, за время $O(n)$.
- Задано дерево, у каждой вершины есть вес. Нужно выбрать $k$ вершин суммарно максимального веса, чтобы никакие две соединенные ребром вершины не были выбраны.
- Задана скобочная последовательность из нескольких видов скобок. Посчитайте минимальное число скобок, которое нужно вставить в эту последовательность, чтобы она стала правильной.
- Задана последовательность чисел длины $n$, каждое число не больше $n$. Посчитайте число различных непустых подпоследовательностей последовательности за $O(n)$. Например, последовательность (1, 1, 2) содержит 5 подпоследовательностей: (1), (2), (1, 2), (1, 1), (1, 1, 2).
- Посчитайте число различных двоичных деревьев из $n$ вершин.
- Посчитайте число различных двоичных деревьев из $n$ вершин без порядка на детях.
- Посчитайте число различных красно-черных деревьев из $n$ вершин.
- Предложите алгоритм восстановления наибольшей возрастающей подпоследовательности по функции ДП, вычисление которой было предложено на лекции за $O(n \log{n})$ с $O(n)$ дополнительной памяти.
- Задана последовательность. Про каждое $i$ определите одно из трех: элемент $a_i$ не может входить ни в одну НВП, элемент $a_i$ входит хотя бы в одну НВП, элемент $a_i$ входит во все НВП за $O(n \log{n})$.
- Заданы две последовательности $a$ и $b$. Подпоследовательность $c$ называется общей для $a$ и $b$, если $c$ является подпоследовательностью $a$ и подпоследовательностью $b$. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время $O(|a| \cdot |b|)$ и памятью $O((|a| + |b|) ^ {2 - \epsilon})$, для некоторого $\epsilon > 0$.
- Задача о рюкзаке. Заданы $n$ предметов, для каждого известен вес $w_i$ и цены $p_i$. Вам нужно выбрать подмножество предметов суммарным весом не более $W$ с максимальной суммарной ценой. Найдите это подмножество за время $O(W \cdot n)$ и память $O(W)$.
- Подпалиндромом последовательности будем называть подпоследовательность $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}$).
- Покажите, что если решить задачу о максимальном подпалиндроме, использовав алгоритм поиска наибольшей общей подпоследовательности, как в предыдущем задании, то алгоритм может выдать подпоследовательность, которая не является палиндромом. Предложите алгоритм, который находит максимальный подпалиндром последовательности $a$ за время и память $O(|a|^2)$.
- $a$ — последовательность длины $n$ из различных чисел от 1 до $n$. Докажите, что произведение длин наибольшей возрастающей и наибольшей убывающей подпоследовательностей в $a$ не меньше $n$.
- Заданы две последовательности $a$ и $b$. Числа в последовательности $a$ различны. Найдите наибольшую общую подпоследовательность $a$ и $b$ за время и память $O((|a| + |b|) \log{(|a| + |b|)})$.
- Заданы $n$ предметов, каждый весом $w_i$. Известно, что за один раз вы можете унести предметы, суммарным весом не более $S$. Какое минимальное число подходов вам нужно сделать, чтобы унести все предметы? Решать за $O(3^n)$.
- Заданы $n$ различных натуральных чисел. Посчитать число перестановок этих чисел, что НОД любых двух соседних не меньше $d$ за $O(n^2 2^n)$.
</wikitex>
