Алгоритмы и структуры данных

Модуль 1

1) Циклический буфер

• В круг выстроено N человек, пронумерованных числами от 1 до N. Будем исключать каждого k-ого до тех пор, пока не уцелеет только один человек. (Например, если N=10, k=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.) Необходимо определить номер уцелевшего. N, k ≤ 10000.
• Требования: Решить перебором.

2) Бинарный поиск

• Дан отсортированный массив различных целых чисел A[0..n-1] и массив целых чисел B[0..m-1]. Для каждого элемента массива B[i] найдите минимальный индекс элемента массива A[k], ближайшего по значению к B[i].
• Требования: Время работы поиска для каждого элемента B[i]: O(log(k)).
• Внимание! В этой задаче для каждого B[i] сначала нужно определить диапазон для бинарного поиска размером порядка k, а потом уже в нем делать бинарный поиск. n ≤ 110000, m ≤ 1000.

3) Очередь с помощью двух стеков.

• Использовать стек, реализованный с помощью динамического буфера.
• Требования: Очередь должна быть реализована в виде класса.
• Стек тоже должен быть реализован в виде класса.

4) Двоичная куча

• Скользящий максимум
• Дан массив натуральных чисел A[0..n), n не превосходит 10^8. Так же задан размер некоторого окна (последовательно расположенных элементов массива) в этом массиве k, k<=n. Требуется для каждого положения окна (от 0 и до n-k) вывести значение максимума в окне.
• Требования: Скорость работы O(n log n), память O(n).
• Формат входных данных. Вначале вводится n - количество элементов массива. Затем вводится n строк со значением каждого элемента. Затем вводится k - размер окна.
• Формат выходных данных. Разделенные пробелом значения максимумов для каждого положения окна.

5) Merge sort

• В супермаркете решили оптимизировать показ рекламы. Известно расписание прихода и ухода покупателей (два целых числа). Каждому покупателю необходимо показать минимум 2 рекламы. Рекламу можно транслировать только в целочисленные моменты времени. Покупатель может видеть рекламу от момента прихода до момента ухода из магазина. В каждый момент времени может показываться только одна реклама. Считается, что реклама показывается мгновенно. Если реклама показывается в момент ухода или прихода, то считается, что посетитель успел её посмотреть. Требуется определить минимальное число показов рекламы.

6) Порядковая статистика

• Даны неотрицательные целые числа n,k и массив целых чисел из [0..10^9] размера n. Требуется найти k-ю порядковую статистику, т.е. напечатать число, которое бы стояло на позиции с индексом k (0..n-1) в отсортированном массиве.
• Требования: к дополнительной памяти: O(n). Среднее время работы: O(n). Должна быть отдельно выделенная функция partition. Рекурсия запрещена. Решение должно поддерживать передачу функции сравнения снаружи.
• Реализуйте стратегию выбора опорного элемента “медиана трёх”.
• Функцию Partition реализуйте методом прохода двумя итераторами от начала массива к концу.

7) Binary MSD для long long.

• Дан массив неотрицательных целых 64-разрядных чисел. Количество чисел не больше 106.
• Отсортировать массив методом MSD по битам (бинарный QuickSort).

Модуль 2

1) Хеш таблица

• Реализуйте структуру данных типа “множество строк” на основе динамической хеш-таблицы с открытой адресацией. Хранимые строки непустые и состоят из строчных латинских букв. Хеш-функция строки должна быть реализована с помощью вычисления значения многочлена методом Горнера. Начальный размер таблицы должен быть равным 8-ми. Перехеширование выполняйте при добавлении элементов в случае, когда коэффициент заполнения таблицы достигает 3/4. Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству. Для разрешения коллизий используйте двойное хеширование.

2) Бинарное дерево

• Дано число N < 106 и последовательность целых чисел из [-231..231] длиной N. Требуется построить бинарное дерево, заданное наивным порядком вставки. Т.е., при добавлении очередного числа K в дерево с корнем root, если root→Key ≤ K, то узел K добавляется в правое поддерево root; иначе в левое поддерево root.
• Требования: Рекурсия запрещена. Решение должно поддерживать передачу функции сравнения снаружи.
• Выведите элементы в порядке level-order (по слоям, “в ширину”).

3) AVL дерево

• Порядковые статистики.
• Дано число N и N строк. Каждая строка содержит команду добавления или удаления натуральных чисел, а также запрос на получение k-ой порядковой статистики. Команда добавления числа A задается положительным числом A, команда удаления числа A задается отрицательным числом “-A”. Запрос на получение k-ой порядковой статистики задается числом k.
• Требования: скорость выполнения запроса - O(log n).

Модуль 3

1) Графы

• Реализовать 4 представления графа, удовлетворяющие заданному интерфейсу.

2) Алгоритм Дейкстра

• Дан невзвешенный неориентированный граф. В графе может быть несколько кратчайших путей между какими-то вершинами.
• Найдите количество различных кратчайших путей между зад анными вершинами.
• Требования: сложность O(V+E).
• Формат ввода. v: кол-во вершин (макс. 50000), n: кол-во ребер (макс. 200000), n пар реберных вершин, пара вершин u, w для запроса.
• Формат вывода. Количество кратчайших путей от u к w.

3) Алгоритм Дейкстра для взмешенного графа

• Требуется отыскать самый выгодный маршрут между городами.
• Требования: время работы O((N+M)logN), где N-количество городов, M-известных дорог между ними.
• Формат входных данных: Первая строка содержит число N – количество городов. Вторая строка содержит число M - количество дорог. Каждая следующая строка содержит описание дороги (откуда, куда, время в пути). Последняя строка содержит маршрут (откуда и куда нужно доехать).
• Формат выходных данных: Вывести длину самого выгодного маршрута.