Алгоритмы на экзамене в ШАД

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

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

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

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

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

Для определенности пусть , если -й человек знает -го человека, и 0 иначе.

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

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

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

Пускай приходит запрос "уменьшить ребро между и ", и новый вес ребра стал . Тогда если в дереве на пути между и есть ребро весом больше (для поиска такого достаточно найти максимальное ребро на пути. В силу условия задачи оно может быть только весом , иначе бы остов не был минимальным, так как на пути в остове между вершинами ребра и было ребро веса , а наше ребро было веса , а значит, выгодно заменить бо́льшее ребро на наше), то нужно удалить его из остова и добавить вместо него наше, уменьшив тем самым вес минимального остовного дерева на 1. Это называется критерий Тарьяна минимальности остовного дерева ^[1]. Осталось понять, как находить максимальное ребро на пути, удалять ребро из дерева и соединять два дерева ребром. Это можно делать либо наивно за , что не позволит нам решить задачу, уложившись в ограничения по времени, либо за с помощью структуры данных link-cut tree ^[2], написание которой у вас займет больше времени, чем сам контест (и это в лучшем случае). Поэтому будем искать другое оптимальное решение.

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

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

Задачу решили, пишется не очень сложно, а что там по времени и памяти? на запрос и даже если писать совсем не заботясь о времени, то на препроцессинг. В ограничения должно уложиться, Accepted :)