Изменения
Нет описания правки
# В массиве есть элемент, который встречается хотя бы $n/2$ раз. Требуется найти его за $O(n)$ с $O(1)$ дополнительной памяти
# Использования памяти без инициализации. Задан массив $a[1..n]$. Требуется поддержать две операции: $set(i, x)$ и $get(i)$. Операция $set$ должна присваивать $i$-му элементу массива значение $x$. Операция $get$ должна возвращать последнее присвоенное $i$-му элементу значение, либо 0, если присвоения не было. При этом исходно массив заполнен произвольными данными. Разрешается завести $O(1)$ дополнительных массивов (также заполненных произвольным мусором) и реализовать все операции за истинное $O(1)$.
# Счетчик Кнута. Рассмотрим массив $a[0..n-1]$. Будем считать, что в каждом элементе может быть число 0, 1 или 2 и массив представляет собой число $a[0]+a[1]\cdot 2+a[2]\cdot 4 + \ldots + a[n-1]\cdot2^{n-1}$. Требуется реализовать операцию добавления $2^k$ к числу, представленному в массиве за истинное $O(1)$ и $O(n)$ дополнительной памяти.
# Реализуйте менеджер памяти, позволяющий выделять и возвращать блоки одинакового размера за $O(1)$ времени и $O(1)$ дополнительной памяти
# Предложите реализацию стека, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в стеке"
# Стек с множественным извлечением. Добавим в стек операцию multipop(k), которая снимает вершины стека k элементов. Докажите, что амортизированная стоимость операции multipop равна $O(1)$. Сформулируйте окончательное доказательство с использованием метода потенциалов.
# Продемонстрируйте, как просимулировать очередь на двух стеках. Амортизированная стоимость операций push и pop должна быть $O(1)$.
# Предложите реализацию очереди, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в очереди". Амортизированная стоимость всех операций должна быть $O(1)$.
# Можно ли реализовать два стека на очереди (ограничений на время выполнения операций нет)?
# Задан односвязный список, каждый элемент знает следующий после себя. При этом возможно, что на самом деле список зацикливается (один из элементов ссылается как на следующий на элемент, который уже встречался в списке перед ним). Требуется проверить, зацикливается ли заданный односвязный список за $O(n)$ с $O(1)$ дополнительной памяти
# $d$-кучей называется структура данных аналогичная двоичной куче, только у каждой вершины по $d$ детей. Двоичная куча является 2-кучей. В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Какое оптимальное асимптотически $d$ следует выбрать?
# В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Время выполнения decreaseKey - $C_1 \log n$, а extractMin - $C_2 d \log n$. Какое $d$ следует выбрать?
# Пусть подряд выполняется $n$ операций insert в пустую биномиальную кучу. Какое среднее время операции?
# Как можно модифицировать биномиальную кучу, чтобы insert выполнялось за истинное $O(1)$, а амортизированная стоимость остальных операций не поменялась?
# Тонкие кучи. Будем называть дерево "тонким", если оно может быть получено из биномиального удалением у некоторых вершин ребенка максимального ранга. Тонкой кучей называется коллекция тонких деревьев. Ограничений на число деревьев одного ранга нет. Разработайте операции merge и extractMin для тонких куч. Амортизированная стоимость операции extractMin должна быть $O(\log n)$. Амортизированная стоимость операции merge должна быть $O(1)$.
# Разработайте операцию decreaseKey для тонкой кучи. Докажите, что амортизированное время выполнения есть $O(1)$ (используйте потенциал $2M + T$, где $M$ - число вершин, у которых удалили ребенка)
# Докажите, что операция decreaseKey в тонкой куче из предыдущего задания выполняется за истинные $O(\log n)$
# Ускорение extractMin. Докажите, что в тонкой куче можно добиться истинного $O(\log n)$ на extractMin, если обрабатывать корневой список, сливая деревья разных рангов, как при extractMin каждый раз, когда в корневом списке становится хотя бы $2\log n$ элементов.
# Докажите оценку $O(\log n)$ для реализации СНМ со сжатием путей, но когда второе дерево всегда подвешивается на первое (а не обязательно меньшее на большее)
# Докажите оценку $O(\log^* n)$ для СНМ, если вместо рангов используется число вершин в поддереве (меньшее дерево подвешивается на большее)
# Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k$ ребер
# Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Приведите пример, где высота дерева в результате серии объединений будет $\Omega(n)$.
# Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Сжатие путей не проводится. Докажите или опровергните, что в среднем время работы get будет $O(\log n)$.
# Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое произвольным образом, но не проводить сжатие путей, то среднее время работы get будет $O(\log n)$.
# Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое случайным образом и проводить сжатие путей, то среднее время работы get будет $O(\log^* n)$.
# Для каких $a$ определен $\log^*_a x$?
# Докажите, что если для $a$ и $b$ определен $\log^*_a x$ и $\log^*_b x$, то $\log^*_a x = O(\log^*_b x)$.
# Постройте массив, в котором сортировка выбором делает максимальное число обменов
# Предложите алгоритм, который вычисляет число обменов, которое делает сортировка выбором, за $O(n \log n)$.
# Найдите минимальное число сравнений для сортировки 4 элементов
# Найдите минимальное число сравнений для сортировки 5 элементов
# Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов
# Укажите способ посчитать число массивов, в которых сортировка слиянием делает максимальное число сравнений элементов, за полиномиальное время.
# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(\sqrt{n})$ дополнительной памяти
# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(1)$ дополнительной памяти
# Докажите, что любой алгоритм, проверяющий, есть ли в массиве два одинаковых элемента с использованием только сравнений элементов, работает за $\Omega(n \log n)$
# Укажите способ для алгоритма QSort с выбором среднего элемента в качестве элемента построить массив, на котором происходит максимальное число сравнений элементов
# Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$
# Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n^2)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве.
# Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n \log n)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве. Указание: зная порядок на подстроках длины $L$ порядок на подстроках длины $2L$ можно восстановить за $O(n)$.
# Пусть известно, что массив длины $n$ из чисел от 1 до $n$ получен с помощью генератора случайных чисел, каждое число независимо получено с помощью равномерного распределения. Предложите модификацию алгоритма сортировки подсчетом, который сортирует данный массив за $O(n)$ используя лишь $O(\sqrt{n})$ дополнительной памяти (обе оценки должны выполняться в среднем).
# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $2^k$. Предложите алгоритм определения за $O(1)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $n$. Предложите алгоритм определения за $O(\log n)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска. h
# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 одного знака.
# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 разных знаков, или одно из них равно 0.
# Предложите алгоритм с временем работы $O(n)$ для следующей задачи: задан массив из неотрицательных чисел и число $k$, определите число отрезков с суммой, не превышающей $k$. Также проанализируйте, работает ли ваш алгоритм, если массив может содержать отрицательные числа: постройте контрпример или докажите, что работает.
# Запросы на статическом массиве: задано число $k$ и запросы {{---}} посчитать ассоциативную необратимую функцию на отрезке длины от $k$ до $2k$. Ответ на запросы за $O(1)$ и препроцессинг за $O(n)$.
# Запросы: 1. set(i, x) {{---}} $a_i := x$ (x {{---}} неотрицательно), 2. get(s) {{---}} найти такое минимальное $y$, что $\sum\limits_{i=1}^y a_i \ge s$, $\sum\limits_{i=1}^{y - 1} a_i < s$ за $O(\log{n})$.
# Обработайте $q$ запросов на прибавление на отрезке, получите конечный массив длины $n$, за $O(n + q)$.
# Обработайте запросы за $O(\log{n})$. Первый {{---}} присвоить значение элементу, второй {{---}} задан отрезок, найти подотрезок с максимальной суммой, содержащийся в этом отрезке.
# Сведите задачу к запросам изменения в точке и функции на отрезке за $O(\log{n})$. Задача {{---}} отвечать на запросы: прибавление на отрезке и минимум на отрезке.
# Решите за $O(\log{n})$ на запрос. Поступают запросы: изменить элемент, найти на заданном отрезке элемент с минимальным индексом, больший или равный заданного значения.
# В дереве отрезков любой отрезок можно разбить на $O(\log n)$ непересекающихся отрезков дерева. Предложите способ выделить $O(n \log n)$ отрезков в массиве индексов 1..$n$, чтобы любой отрезок можно было разбить на $O(1)$ непересекающихся отрезков из выбранного множества
# Дано $n$ точек на плоскости. Требуется найти наибольшую последовательность точек, в которой при переходе к следующей точке обе координаты строго возрастают, за $O(n \log n)$.
# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти точку, покрытую максимальным числом прямоугольников за $O(n \log n)$.
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить произведение на отрезке. Время работы $o(n)$ на запрос (это задача-аукцион, пишите свое среднее время работы на запрос, время предпосчета и памяти на заявке)
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить значение к элементам на отрезке, найти элемент с минимальным индексом, больший или равный заданного значения.
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log n)$.
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить сумму на отрезке. Время на запрос $O(\log n)$.
# Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить минимум на отрезке. Время работы $o(n)$ на запрос (это задача-аукцион, пишите свое среднее время работы на запрос, время предпосчета и памяти на заявке)
# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти площадь объединения прямоугольников за $O(n \log n)$.
# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти периметр объединения прямоугольников за $O(n \log n)$.
# Решите за $O(\sqrt{n}\log{n})$ на запрос амортизированно. Поступают запросы: развернуть отрезок и посчитать количество элементов на отрезке от $x$ до $y$.
# Решите предыдущую задачу за $O(\sqrt{n\log{n}})$ на запрос истинно.
# Решите с помощью персистентного дерева отрезков. Дано $n$ точек. Поступают запросы в online: прямоугольник со сторонами, параллельными осям координат, нужно найти $k$-ю точку по возрастанию $y$-координаты, среди лежащих внутри этого прямоугольника. Время работы: $O(\log{n})$ на запрос.
# Решите предыдущую задачу без персистентного дерева отрезков.
# Решите за $O(\log{n})$ на запрос. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам на отрезке заданное число и вывести сумму сумм всех подотрезков отрезка.
# Решите за $O(\log{n})$ на запрос. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам на отрезке заданное число, умножить все элементы на отрезке на заданное число, вывести $i$-й элемент массива.
# Модифицировать алгоритм Фараха-Колтона-Бендера, чтобы массив precalc занимал только $O(K \log{K})$ бит памяти для каждой маски.
# Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$". После предобработки за $O(n)$ ответ на запрос за $O(1)$.
# Дано взвешенное дерево. Научиться отвечать на запросы "вес пути из $u$ в $v$" и "изменить вес ребра". После предобработки за $O(n)$ ответ на запрос за $O(\log{n})$.
# Дано взвешенное дерево. Научиться отвечать на запросы "вес ребра" и "прибавить ко всем ребрам на пути от $v$ до $u$ число $d$". После предобработки за $O(n)$ ответ на запрос за $O(\log{n})$.
# Алгоритм Хьюи. Дано дерево, вершины которого раскрашены в цвета, то есть задано отображение $col: V \to \{1..k\}$. С помощью LCA найти $dc: V \to \{1..k\}$, где $dc(u)$ - число различных цветов в поддереве с корнем в вершине $u$. Время работы: $O(V)$.
# Задано взвешенное дерево. Посчитать число простых путей в дереве длины от $L$ до $R$ и весом от $x$ до $y$. Время работы $O(n \log^2{n})$.
# Задано невзвешенное дерево. Изначально все вершины белого цвета. Научиться отвечать на запросы: покрасить белую вершину в черную, к заданной вершине найти ближайшую черную вершину. Время работы одного запроса $O(\log{n})$.
# Задано невзвешенное дерево. Изначально все вершины белого цвета. Научиться отвечать на запросы: покрасить белую вершину в черную, покрасить черную вершину в белую, к заданной вершине найти ближайшую черную вершину. Время работы одного запроса $O(\log^2{n})$.
# Покраску дерева в $k$ цветов от 1 до $k$ назовем яркой, если между любыми двумя вершинами одного цвета $c$, существует вершина цвета $d$, что $d < c$. Рассмотрим функцию $f(n) = k$ {{---}} минимальное $k$, что любое дерево из $n$ вершин можно ярко покрасить в $k$ цветов. Докажите, что $f(n) = O(\log{n})$
# Задано дерево из $n$ вершин. В каждой вершине есть число. Нужно отвечать на запросы: медиана в множестве чисел, записанных в вершинах на пути. Время на запрос: $O(\log{n})$.
# Рассмотрим подвешенное дерево. Пусть $s(v)$ {{---}} размер поддерева с корнем в вершине $v$, $C(v)$ {{---}} множество всех непосредственных потомков вершины $v$, $h(v) = \operatorname*{arg\,max}\limits_{u \in C(v)} s(u)$, $f(v) = s(v) - s(h(v))$. Доказать, что $\sum\limits_{v \in V}f(v) = O(n \log{n})$.
# Рассмотрим подвешенное дерево. Пусть $k(v)$ {{---}} высота поддерева с корнем $v$, $C(v)$ {{---}} множество всех непосредственных потомков вершины $v$, $d(v) = \operatorname*{arg\,max}\limits_{u \in C(v)} k(u)$, $g(v) = \sum\limits_{\substack{
u \in C(v) \\
u \ne d(v)}} k(v)$. Доказать, что $\sum\limits_{v \in V}g(v) = O(n)$.
# Задано подвешенное дерево. Нужно отвечать на запросы: подвесить вершину как лист к одной из имеющихся вершин, найти наименьшего общего предка двух уже добавленных вершин. Время работы запросов: $O(n \log{n})$.
# Предложите алгоритм добавления в АВЛ-дерево за $O(h)$, где $h$ {{---}} высота дерева.
# Предложите алгоритм удаления из АВЛ-дерева за $O(h)$, где $h$ {{---}} высота дерева.
# Предложите алгоритм добавления в красно-черное дерево за $O(h)$, где $h$ {{---}} высота дерева.
# Предложите алгоритм удаления из красно-черного дерева за $O(h)$, где $h$ {{---}} высота дерева.
# Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.
# Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(\log n)$
# Предложите алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше или равны заданному $x$, а во втором - больше, за $O(\log n)$
# В АВЛ-дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
# В красно-черном дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
# Предложите реализацию АВЛ-дерева, в которой в каждом узле хранится $O(1)$ бит
# Перекошенное сбалансированное дерево. Дерево называется перекошенным сбалансированным, если у каждой вершины разность высоты левого и правого поддерева 0, 1 или 2. Предолжите реализацию операций вставки и удаления для перекошенного сбалансированного дерева.
# Мальчик Петя считает, что если в дереве поиска можно хранить несколько одинаковых ключей, то на пути от одного такого ключа до другого не может быть ключей с другим значением. Тогда можно легко найти все такие ключи. Прав ли он?
# Докажите, что высота красно-черного дерева $O(\log{n})$.
</wikitex>
