Множества и функции

1. Очереди с приоритетами

2. Хеш-таблицы

3. Двоичные деревья поиска

4. Системы непересекающихся множеств

Задачи

Задача 1 (Выборы заведующего кафедрой). В связи с реорганизацией встал вопрос о выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером $i$ определили следующие числа: $m_i$ – уровень познаний в математике, $p_i$ – уровень познаний в программировании; $t_i$ – преподавательское мастерство. Чем больше число, тем выше уровень мастерства преподавателя в соответствующей области. Считается, что $i$-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого $j$-того преподавателя, что одновременно $m_j > m_i$, $p_j > p_i$, $t_j > t_i$. Напишите программу, составляющую список кандидатов на должность заведующего кафедрой.

Решение. Вначале упорядочим всех преподавателей по одному из признаков $m_i$. Всё множество точек $\mathbf x_i = (m_i, p_i, t_i)$ разбивается на подмножества $X_j = {\mathbf x_i \colon m_i = a_j}$ с определенными значениями $m_i = a_j$, и пусть $a_1 < a_2 < \ldots < a_s$. Таким образом, каждый преподаватель $\mathbf x_i \in X_j$ окажется кандидатом на должность в том и только том случае, когда для него не найдется такого $k$-го преподавателя, что $\mathbf x_k \in X_l$, $l > j$, причем $p_i < p_j$, $t_i < t_j$.

Нам потребуется структура данных типа “множество”, в которую мы будем последовательно добавлять точки из множеств $X_s, X_{s-1}, \ldots, X_1$, проверяя для каждой новой точки, найдется ли в нашем множестве точка, превосходящая ее по всем параметрам. Множество будет двумерным – будет содержать признаки $p_i$ и $t_i$, а сравнение признаков $m_i$ проводится автоматически (внутри одного и того же множества $X_j$ сравнение не производится).

Итак, определим структуру данных $S$ – множество точек плоскости с операцией модификации $S.{\tt add}(y, z : {\tt Int})$ – добавить точку $(y,z)$ к $S$; и операцией доступа $S.{\tt exists_greater}(y,z) \to {\tt Bool} = (\exists (y’, z’) \in S \colon y’ > y, z’ > z)$ – эта функция возвращает, существует ли в множестве $S$ пара, превосходящая заданную пару $(y,z)$. И еще одна операция доступа: $S.{\tt Pareto}() \to {\tt Set\langle [Int,Int]\rangle}$, которая возвращает множество точек, не превосходимые другими точками множества $S$, то есть множество ${(y,z) \in S \colon {\tt exists_greater}(y,z) = 0}$.

Логически мы работаем со всем множеством $S$, однако для реализации указанных операций над структурой данных достаточно хранить в ней информацию только о точках подмножества $S.{\tt Pareto}()$, поскольку все остальные точки, которые превосходятся точками этого подмножества, на результат выполнения операций никак не влияют.

Алгоритм решения задачи: в цикле по $j$ от $s$ до $1$ с шагом -1 находим множество $A_j = {(y,z) \in X_j \colon S.{\tt exists_greater}(y,z)=0}$; и для всех элементов $(y,z) \in A_j$ вызываем $S.{\tt add}(y,z)$.

Реализация СД $S$

Временная сложность алгоритма $O(n\log n)$.

Задача 2 (Всё успеть). У студента Коли много дел: целых $N$. Каждому делу он назначил приоритет $p_i$ и уровень сложности $d_i$. Коля – очень ответственный студент, поэтому он берется в первую очередь за наиболее важные дела, для которых $p_i$ максимально. Да только он сейчас устал, и поэтому может делать дела, для которых $d_i \leq a$. Требуется найти среди таких дел наиболее важное.

Дано: ${(p_i, d_i)}_1^N \subset \mathbb R^2$, ${a_j}_1^M \subset \mathbb R$. Для каждого $j$ Коля находит $i : d_i \leq a, p_i \to \max$ и удаляет соответствующий элемент множества пар ${(p_i, d_i)}$. Реализовать эффективную структуру данных, позволяющую эффективно производить такие операции над этим множеством.

Решение. Вначале нам понадобится предварительная обработка точек $(p_i, d_i)$. Упорядочим их по координате $p_i$. Представим себе, что Коля не удаляет точки после просмотра. Тогда для реализации всех $M$ запросов при разных $a$ достаточно привести множество точек к виду возрастающих массивов $p_i$ и $d_i$, а остальные точки $(p, d)$, для которых найдется точка $(p’, d’)$ такая, что $p \leq p’$, $d \geq d’$, мы удаляем. В возрастающем массиве выполнить запрос можно за время $O(\log N)$ при помощи двоичного поиска. Но по условию задачи множество надо обновлять после каждого запроса и соответствующего удаления. Как это сделать? В упорядоченном по $p_i$ множестве точек $(p_i, d_i)$ будем ставить стрелки от точки $(p_1, d_1)$ к ближайшей справа точке $(p_2, d_2)$, для которой $p_1 \leq p_2$, $d_1 \geq d_2$. Тогда при обработке запросов достаточно будет просмотреть точки, из которых не выходят стрелки. Для всех точек можно хранить количество входящих стрелок и при удалении очередной точки удалять все входящие в нее стрелки – тогда у некоторых точек исчезнут исходящие стрелки, и их придется внести в возрастающую последовательность точек, которую мы используем для выполнения запросов к СД. А также придется ставить новые стрелки к элементам возрастающей последовательности – точку, к которой надо поставить стрелку, найдем двоичным поиском.

(алгоритм еще нужно уточнить и проверить, задача новая)

Временная сложность алгоритма $O((M+N)\log N)$.