31.03.2020 16:17
DeathCookies 0 3000 Источник

Привет! Меня зовут Александр Курилкин, и я веду курс по алгоритмам в «ШАД Helper». В этом посте я разберу несколько задач из вступительных экзаменов прошлых лет, чтобы вы смогли увидеть, что вас ждет, и понять, чему мы сможем вас научить на нашем курсе. Надеюсь, что вы разделяете мою любовь к интересным задачам по алгоритмам и получите искреннее удовольствие от прочтения этого поста! Итак, приступим...



28.05.2016, №4


Даны $n$ отрезков $[a_i; b_i]$. Назовем индексом вложенности отрезка $[a_i; b_i]$ количество отрезков, которые его содержат. Предложите алгоритм, определяющий, есть ли в наборе отрезок с индексом вложенности, превышающим 1000. Ограничение по времени — $O(n \log n)$, по дополнительной памяти — $O(n)$.


Решение

Воспользуемся методом, который в среде олимпиадников называется "сканлайн". Его суть в том, что мы сводим задачу к набору каких-то событий, которые обрабатываем в отсортированном порядке, что-то при этом делая, таким образом решая задачу. В данном случае для каждого отрезка создадим события "отрезок открылся", которое происходит в момент времени $a_i$, и "отрезок закрылся", которое происходит в момент времени $b_i$. Отсортируем все события по их моменту времени и начнем обрабатывать их в таком порядке. Когда отрезок открывается, нужно увеличить счетчик открытых отрезков на 1. Когда открылся очередной отрезок, а счетчик открытых отрезков уже был больше или равен 1000, казалось бы, мы уже решили задачу — очередной отрезок содержится в 1000 уже открытых ранее. Но все не так просто — какие-то из открытых ранее отрезков могли закрыться раньше, чем закроется наш текущий отрезок, который мы рассматриваем как кандидат на ответ. Чтобы решить эту проблему, давайте поддерживать отсортированное мультимножество (std::multiset в C++), в котором будем хранить координаты концов открытых отрезков. На самом деле, хранить все концы в нем не обязательно — достаточно лишь 1000 максимальных. Теперь, чтобы проверить, что текущий отрезок и правда подходит нам, нужно проверить, что в мультимножестве *set.begin(), то есть минимальный (среди 1000 максимальных) конец не левее конца текущего отрезка. Если это правда, то мы нашли подходящий отрезок и задача решена! Если нет, то увы, придется продолжать обрабатывать события раньше. Если отрезок закрылся, то нужно уменьшить счетчик открытых отрезков и удалить из мультимножества его конец. Если все события обработаны, а подходящий отрезок не обнаружен, то его и нет!


У пытливого читателя при прочтении мог возникнуть вопрос: почему достаточно хранить лишь 1000 концов? Вдруг может быть такое, что удалится какой-то из этих 1000 максимальных концов, а открыто было больше 1000 отрезков, и придется откуда-то взять конец, чтобы заменить им только что удаленный? На самом деле такого быть не может, ведь если мы удалили какой-то из 1000 максимальных концов, значит, мы закрыли отрезок с таким концом, а до этого закрыли и все отрезки с концами левее нашего, а значит, заменять в мультимножестве удаленный конец нечем.


Вот и все, задача решена. Мы потратили $O(n \log n)$ времени на сортировку событий, $O(n \log 1000) = O(n)$ времени на операции с мультимножеством концов отрезков и O(n) на все остальное. Таким образом, время работы: $O(n \log n)$. Памяти мы уж точно потратили не больше $O(n)$.


25.05.2019, №4


Дан массив вещественных чисел $A$. Предложите алгоритм, находящий для каждого элемента $A$ индекс ближайшего справа элемента, большего его хотя бы в два раза. Если такого элемента нет, то должно возвращаться значение $None$. Ограничение по времени $O(n \log n)$, по дополнительной памяти — $O(n)$.


Решение

Будем идти по массиву справа налево и поддерживать стек пар $(значение, индекс)$ пройденных чисел. Начнем с самого правого элемента (для него ответ $None$), добавим в стек $(A[n - 1], n - 1)$, пойдем левее. Пусть мы хотим обработать очередное число с индексом $i$. Тогда какие числа, пройденные ранее, не представляют для нас никакого интереса в плане определения ближайшего справа в два раза больше как для нашего числа, так и для чисел левее? Это те числа, которые находятся между нашим и ближайшим большим справа. И правда, зачем они нам в будущем, если у нас уже есть число левее, большее них? А вот ближайшее большее справа нам еще может пригодиться. Поэтому давайте удалять из стека верхние элементы, пока их значения меньше или равны нашему. Как только у верхушки стека значение стало больше, пора остановиться и добавить на вершину стека $(A[i], i)$. Хорошо, со стеком мы поработали, но как теперь определить индекс ближайшего справа в два раза большего числа? Заметим, что числа в стеке отсортированы (сверху вниз) по значению и по расстоянию до $i$. Тогда достаточно двоичным поиском в стеке (да, для этого потребуется индексация стека, поэтому давайте вместо стека использовать std::vector) найти наименьшее значение, большее или равное $A[i] \cdot 2$. Если такое нашлось, нужно взять его индекс (мы же храним его в паре), а если не нашлось, то ответ $None$.


Хорошо, задачу мы решили, но какова асимптотика алгоритма? Каждый элемент добавится и удалится из стека всего один раз, поэтому на все добавления и удаления в стек мы потратим O(n), а еще придется сделать $n$ двоичных поисков, что займет $O(n \log n)$, что все еще укладывается в ограничения задачи. Памяти мы, потратили, очевидно, не больше $O(n)$.


10.06.12, №5
В множестве из $n$ человек каждый может знать или не знать другого (если $A$ знает $B$, отсюда не следует, что $B$ знает $A$). Все знакомства заданы булевой матрицей $n?n$. В этом множестве может найтись или не найтись знаменитость — человек, который никого не знает, но которого знают все. Предложите алгоритм, который бы находил в множестве знаменитость или говорил, что ее в этом множестве нет. Сложность по времени — $O(n)$, сложность по памяти — $O(1)$.


Решение

Для определенности пусть $K_{ij} = 1$, если $i$-й человек знает $j$-го человека, и 0 иначе.


Тогда заметим, что если $K_{ij} = 1 ~ (i \neq j)$, то $i$-й человек точно не может быть знаменитостью, ведь он кого-то знает, а вот $j$-й может, а если $K_{ij} = 0$, то $j$-й человек точно не может быть знаменитостью, ведь $i$-й его не знает.


Это дает нам следующий алгоритм: пусть изначально первый человек — наш кандидат в знаменитости. Давайте начнем идти по первой строке матрицы вправо, пока не встретим 1, скажем, в столбце $l$. Тогда все люди, соответствующие пройденным столбцам (где был записан 0), точно не могут быть знаменитостями, а человек, соответствующий первой строке, тоже не может быть знаменитостью, поскольку он кого-то знает (а именно, человека, соответствующего строке $l$). Тогда $l$-й человек — наш кандидат в знаменитости, и начнем такой же процесс с клетки матрицы $(l, l + 1)$. Если на пути нам встретится 1, то обновим кандидатата, и так далее, пока мы можем идти вправо. Осталось проверить, действительно ли является ли наш последний кандидат знаменитостью. Для этого проверим, что в столбце, соответствующем ему, все единицы (кроме клетки на главной диагонали), это значит, что его все знают, а в его строке все нули, то есть он никого не знает. Пока мы шли по матрице, мы двигались только вправо, а значит, потратили $O(n)$ времени, а во время финальной проверки пробежались по одной строке и по одному столбцу, что также заняло $O(n)$ времени. Итого: $O(n)$ времени. Также ничего, кроме нескольких переменных, мы не хранили (считаем, что матрица была дана заранее и в расчет памяти не входит), и памяти мы заняли $O(1)$. Полное решение!


Это были задачи, требующие смекалки и совсем небольшого знания алгоритмов, а теперь немного алгоритмической жести!


2019, онлайн-контест, задача D


Минимальное остовное дерево, часть 2
Ограничение времени: 2 секунды
Ограничение памяти: 256Mb


Вам дан неориентированный взвешенный граф с $n$ вершинами и $m$ рёбрами. Требуется выполнить $q$ запросов вида «уменьшить вес ребра номер $i$ на 1». После каждого запроса вам нужно вывести вес минимального остовного дерева в графе.


Остовное дерево графа — это подграф, содержащий все вершины графа и являющийся деревом. Остовное дерево называется минимальным, если сумма весов входящих в него рёбер минимально возможная.


Граф связен и не содержит петель и кратных рёбер. Кроме того, гарантируется, что после каждого запроса веса всех рёбер неотрицательны.


Формат ввода


В первой строке входного файла содержатся два целых числа $n$ и $m$ — количество вершин и рёбер графа соответственно ($1 \le n, m \le 10^5, 2 \le n)$. В следующих $m$ строках содержится по три целых числа $u$, $v$, $w$. Это значит, что в графе есть ребро веса $w$, соединяющее вершины $u$ и $v$ ($1 \le u, v \le n, 1 \le w \le 10$).


В следующей строке содержится целое число $q$ — количество запросов ($1 \le q \le 10^5$). В следующих $q$ строках содержится по одному целому числу $id$ ($1 \le id \le m$). Это значит, что требуется уменьшить на единицу вес ребра $id$. Рёбра нумеруются с единицы в порядке следования во входном файле.


Формат вывода


Выведите $q$ чисел, разделённых пробелами или переводами строки — веса минимального остовного дерева после выполнения каждого запроса.


Решение

Для начала давайте поймем, как решать задачу, если бы ограничения были поменьше или наши руки были посильнее 99% поступающих в ШАД. Для начала построим минимальное остовное дерево.


Пускай приходит запрос "уменьшить ребро между $u$ и $v$", и новый вес ребра стал $k$. Тогда если в дереве на пути между $u$ и $v$ есть ребро весом больше $k$ (для поиска такого достаточно найти максимальное ребро на пути. В силу условия задачи оно может быть только весом $k+1$, иначе бы остов не был минимальным, так как на пути в остове между вершинами ребра $u$ и $v$ было ребро веса $> k + 1$, а наше ребро было веса $k + 1$, а значит, выгодно заменить бо?льшее ребро на наше), то нужно удалить его из остова и добавить вместо него наше, уменьшив тем самым вес минимального остовного дерева на 1. Это называется критерий Тарьяна минимальности остовного дерева. Осталось понять, как находить максимальное ребро на пути, удалять ребро из дерева и соединять два дерева ребром. Это можно делать либо наивно за $O(n)$, что не позволит нам решить задачу, уложившись в ограничения по времени, либо за $O(\log n)$ с помощью структуры данных link-cut tree, написание которой у вас займет больше времени, чем сам контест (и это в лучшем случае). Поэтому будем искать другое оптимальное решение.


Так как веса бывают всего лишь от 1 до 10, давайте поддерживать 10 остовов (они могут быть лесами, не обязательно деревьями). В $k$-м остове будут только ребра весом $\le k$. Каждый остов построим алгоритмом Краскала. Для этого есть две причины: он просто пишется, и СНМы (системы непересекающихся множеств) для каждого остова, оставшиеся после него, нам еще понадобятся в будущем. Кроме того, можно заметить, что при построении таким образом первый остов будет подмножеством второго, второй третьего, и так далее.


Пусть вес ребра $(u, v)$ уменьшился на 1 и стал $k$. Попытаемся добавить его в $k$-й остов. Для начала с помощью СНМ проверим, лежат ли в $k$-м остове $u$ и $v$ в одной компоненте связности. Если это не так, то на пути между ними есть ребро веса $k+1$, а значит, можно его выкинуть и заменить на наше. Но делать все это явно не будем, а просто сделаем слияние компонент $u$ и $v$ в СНМе $k$-го остова, заодно уменьшив вес минимального остовного дерева на 1. Если же $u$ и $v$ лежат в одной компоненте связности в $k$-м остове, то между ними есть путь по ребрам с весом $\le k$, и уменьшение веса нашего ребра не принесет никакой пользы.


Задачу решили, пишется не очень сложно, а что там по времени и памяти? $O(\alpha(n))$ на запрос и даже если писать совсем не заботясь о времени, то $O(10 \cdot m \log n) = O(m \log n)$ на препроцессинг. В ограничения должно уложиться, Accepted :)