НОВОСТИ Алгоритмы на экзамене в ШАД

[BDFpromo]

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

28.05.2016, №4


Даны

отрезков

. Назовем индексом вложенности отрезка

количество отрезков, которые его содержат. Предложите алгоритм, определяющий, есть ли в наборе отрезок с индексом вложенности, превышающим 1000. Ограничение по времени —

, по дополнительной памяти —

.

Решение

Воспользуемся методом, который в среде олимпиадников называется "сканлайн". Его суть в том, что мы сводим задачу к набору каких-то событий, которые обрабатываем в отсортированном порядке, что-то при этом делая, таким образом решая задачу. В данном случае для каждого отрезка создадим события "отрезок открылся", которое происходит в момент времени

, и "отрезок закрылся", которое происходит в момент времени

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


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


Вот и все, задача решена. Мы потратили

времени на сортировку событий,

времени на операции с мультимножеством концов отрезков и O(n) на все остальное. Таким образом, время работы:

. Памяти мы уж точно потратили не больше

.



25.05.2019, №4


Дан массив вещественных чисел

. Предложите алгоритм, находящий для каждого элемента

индекс ближайшего справа элемента, большего его хотя бы в два раза. Если такого элемента нет, то должно возвращаться значение

. Ограничение по времени

, по дополнительной памяти —

.

Решение

Будем идти по массиву справа налево и поддерживать стек пар

пройденных чисел. Начнем с самого правого элемента (для него ответ

), добавим в стек

, пойдем левее. Пусть мы хотим обработать очередное число с индексом

. Тогда какие числа, пройденные ранее, не представляют для нас никакого интереса в плане определения ближайшего справа в два раза больше как для нашего числа, так и для чисел левее? Это те числа, которые находятся между нашим и ближайшим большим справа. И правда, зачем они нам в будущем, если у нас уже есть число левее, большее них? А вот ближайшее большее справа нам еще может пригодиться. Поэтому давайте удалять из стека верхние элементы, пока их значения меньше или равны нашему. Как только у верхушки стека значение стало больше, пора остановиться и добавить на вершину стека

. Хорошо, со стеком мы поработали, но как теперь определить индекс ближайшего справа в два раза большего числа? Заметим, что числа в стеке отсортированы (сверху вниз) по значению и по расстоянию до

. Тогда достаточно двоичным поиском в стеке (да, для этого потребуется индексация стека, поэтому давайте вместо стека использовать std::vector) найти наименьшее значение, большее или равное

. Если такое нашлось, нужно взять его индекс (мы же храним его в паре), а если не нашлось, то ответ

.


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

двоичных поисков, что займет

, что все еще укладывается в ограничения задачи. Памяти мы, потратили, очевидно, не больше

.



10.06.12, №5
В множестве из

человек каждый может знать или не знать другого (если

знает

, отсюда не следует, что

знает

). Все знакомства заданы булевой матрицей

. В этом множестве может найтись или не найтись знаменитость — человек, который никого не знает, но которого знают все. Предложите алгоритм, который бы находил в множестве знаменитость или говорил, что ее в этом множестве нет. Сложность по времени —

, сложность по памяти —

.

Решение

Для определенности пусть

, если

-й человек знает

-го человека, и 0 иначе.


Тогда заметим, что если

, то

-й человек точно не может быть знаменитостью, ведь он кого-то знает, а вот

-й может, а если

, то

-й человек точно не может быть знаменитостью, ведь

-й его не знает.


Это дает нам следующий алгоритм: пусть изначально первый человек — наш кандидат в знаменитости. Давайте начнем идти по первой строке матрицы вправо, пока не встретим 1, скажем, в столбце

. Тогда все люди, соответствующие пройденным столбцам (где был записан 0), точно не могут быть знаменитостями, а человек, соответствующий первой строке, тоже не может быть знаменитостью, поскольку он кого-то знает (а именно, человека, соответствующего строке

). Тогда

-й человек — наш кандидат в знаменитости, и начнем такой же процесс с клетки матрицы

. Если на пути нам встретится 1, то обновим кандидатата, и так далее, пока мы можем идти вправо. Осталось проверить, действительно ли является ли наш последний кандидат знаменитостью. Для этого проверим, что в столбце, соответствующем ему, все единицы (кроме клетки на главной диагонали), это значит, что его все знают, а в его строке все нули, то есть он никого не знает. Пока мы шли по матрице, мы двигались только вправо, а значит, потратили

времени, а во время финальной проверки пробежались по одной строке и по одному столбцу, что также заняло

времени. Итого:

времени. Также ничего, кроме нескольких переменных, мы не хранили (считаем, что матрица была дана заранее и в расчет памяти не входит), и памяти мы заняли

. Полное решение!



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


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


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


Вам дан неориентированный взвешенный граф с

вершинами и

рёбрами. Требуется выполнить

запросов вида «уменьшить вес ребра номер

на 1». После каждого запроса вам нужно вывести вес минимального остовного дерева в графе.


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


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


Формат ввода


В первой строке входного файла содержатся два целых числа

и

— количество вершин и рёбер графа соответственно (

. В следующих

строках содержится по три целых числа

,

,

. Это значит, что в графе есть ребро веса

, соединяющее вершины

и

(

).


В следующей строке содержится целое число

— количество запросов (

). В следующих

строках содержится по одному целому числу

(

). Это значит, что требуется уменьшить на единицу вес ребра

. Рёбра нумеруются с единицы в порядке следования во входном файле.


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


Выведите

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

Решение

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


Пускай приходит запрос "уменьшить ребро между

и

", и новый вес ребра стал

. Тогда если в дереве на пути между

и

есть ребро весом больше

(для поиска такого достаточно найти максимальное ребро на пути. В силу условия задачи оно может быть только весом

, иначе бы остов не был минимальным, так как на пути в остове между вершинами ребра

и

было ребро веса

, а наше ребро было веса

, а значит, выгодно заменить бо́льшее ребро на наше), то нужно удалить его из остова и добавить вместо него наше, уменьшив тем самым вес минимального остовного дерева на 1. Это называется

You must be registered for see links

. Осталось понять, как находить максимальное ребро на пути, удалять ребро из дерева и соединять два дерева ребром. Это можно делать либо наивно за

, что не позволит нам решить задачу, уложившись в ограничения по времени, либо за

с помощью структуры данных

You must be registered for see links

, написание которой у вас займет больше времени, чем сам контест (и это в лучшем случае). Поэтому будем искать другое оптимальное решение.


Так как веса бывают всего лишь от 1 до 10, давайте поддерживать 10 остовов (они могут быть лесами, не обязательно деревьями). В

-м остове будут только ребра весом

. Каждый остов построим

You must be registered for see links

. Для этого есть две причины: он просто пишется, и СНМы (

You must be registered for see links

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


Пусть вес ребра

уменьшился на 1 и стал

. Попытаемся добавить его в

-й остов. Для начала с помощью СНМ проверим, лежат ли в

-м остове

и

в одной компоненте связности. Если это не так, то на пути между ними есть ребро веса

, а значит, можно его выкинуть и заменить на наше. Но делать все это явно не будем, а просто сделаем слияние компонент

и

в СНМе

-го остова, заодно уменьшив вес минимального остовного дерева на 1. Если же

и

лежат в одной компоненте связности в

-м остове, то между ними есть путь по ребрам с весом

, и уменьшение веса нашего ребра не принесет никакой пользы.


Задачу решили, пишется не очень сложно, а что там по времени и памяти?

на запрос и даже если писать совсем не заботясь о времени, то

на препроцессинг. В ограничения должно уложиться, Accepted