Привет всем!
556A - Дело о нулях и единицах
Если в последовательности остались хотя бы одни единица и ноль, тогда существует подстрока 01 или 10, которую можно удалить. При этом порядок удаления не важен: в любом случае мы сделаем min(#единиц, #нулей) операций, так как за раз удаляется один ноль и одна единица. Поэтому ответ: #единиц + #нулей - 2min(#единиц, #нулей) = |#единиц - #нулей|.
Время: O(n).
556B - Дело о поддельных шестеренках
Заметим, что через n нажатий кнопки система приходит в исходное положение. Поэтому самое простое решение — это промоделировать процесс из n шагов и, если на одном из них встретится последовательность 0, 1, ... , n - 1, выдать "Yes", иначе "No". Но можно это решение ускорить. Например, сразу по значению первого элемента определить нужное количество нажатий, перейти в это положение и один раз проверить.
Время: O(n) или O(n2); решения: O(n) и O(n^2)
Предположим нам не нужно разбирать некоторую последовательность. Тогда ни в одну из матрешек этой последовательности не нужно вставить другую. Поэтому нам не нужно разбирать последовательность матрешек лишь в случае, если они идут подряд, начиная с 1. Пусть длина этой последовательности равна l. Тогда вытащить одну из другой нам нужно будет n - k - l + 1 раз, при этом останется одна цепочка из l матрешек 1 → 2 → ... → l и остальные цепочки по одной матрешке. Всего n - k + 1 цепочка, поэтому вложить одну в другую нужно n - k раз. Всего будет сделано 2n - l - 2k + 1 операций.
Время: O(n); решение.
Между островами i и i + 1 мы можем положить мост, длина которого попадает в отрезок [li + 1 - ri;ri + 1 - li]. Получаем задачу: есть n - 1 отрезков и m точек на прямой, необходимо каждому отрезку сопоставить какую-то точку, лежащую в нем, причем каждую точку можно сопоставить только одному отрезку. Будем идти по точкам слева направо, и хранить в сете отрезки, которые еще ничему не сопоставлены и которые содержат рассматриваемую точку. Пусть мы обрабатываем очередную точку. Сначала добавим в сет все отрезки, которые начинаются в этой точке. Далее выберем из них тот, чей правый конец имеет наименьшую координату. Утверждается, что этот алгоритм находит ответ, если он есть. Предположим это не так. Пусть мы на каком-то шаге выбрали для точки A другой отрезок (пропускать точку не имеет смысла). Тогда посмотрим, какая точка B сопоставлена отрезку, который был бы выбран нашим решением. Точка B лежит заведомо правее A. Поэтому мы можем поменять точки для этих отрезков и снова получить ответ.
Время: O((n + m)log(n + m)); решение.
Решим задачу с помощью двух деревьев отрезков: для столбцов и для строк. Будем хранить для каждого столбца самую нижнюю съеденную дольку, а для каждой строки — самую левую. Пусть приходит запрос x y L. Находим значение в дереве отрезков для строк на месте y. Пусть это значение равно ans. Теперь нужно вывести x - ans и в дереве для столбцов обновить значения на отрезке [ans + 1, x] до y, а в горизонтальном обновить значение в элементе y дo x. Аналогично с запросами типа U. Чтобы разобраться с большими ограничениями на n нужно писать либо неявное дерево отрезков, либо сжатие координат.
Время: O(qlogq) или O(qlogn); решения: 1 and 2.
555D - Дело повышенной секретности
Назовем активной длиной La длину части веревки от груза до последнего встреченного колышка. После каждого встреченного колышка активная длина уменьшается. Будем моделировать процесс для каждой длины веревки независимо. На каждом шаге будем бинарным поиском находить, за какой колышек зацепится груз сейчас. При этом если активная длина при этом уменьшается хотя бы вдвое или мы делаем первый шаг, то просто переходим к следующему шагу. А иначе пусть текущий колышек имеет номер i, следующий — j (без ограничения общности i < j). Тогда заметим, что после колышка j мы снова зацепимся именно за колышек i. Действительно, 2(xj - xi) ≤ La, поэтому веревка зацепится не правее чем за i-й колышек. И либо i = 1, либо La ≤ xi - xi - 1, поэтому левее, чем за i-й колышек она тоже зацепиться не может. И вообще, пока активная длина будет не меньше, чем xj - xi, груз будет наматываться на эту пару колышков, следовательно, можно сделать сразу несколько ходов. При этом после этих ходов длина веревки уменьшится хотя бы вдвое. Поэтому всего таких будет сделано не больше log(L), где L — изначальная длина веревки.
Решение: O(mlogLlogn); решение.
555E - Дело о компьютерной сети
Для начала, сведем задачу к задаче на дереве. В каждой компоненте двусвязности ориентируем ребра в порядке обхода DFS. Утверждается, что мы получим компоненту сильной связности. Пусть это не так. Тогда граф можно разбить на два подграфа A и B так, что не существует ребер, идущих из B в A. Причем изначально ребер между A и B хотя бы два. Но это невозможно, так как, зайдя в эту компоненту B, мы должны будем выйти по одному из ребер между A и B, а это невозможно. Противоречие.
Поэтому мы можем сжать все компоненты двусвязности.
Теперь надо обработать несколько запросов вида “ориентировать ребра на пути” и проследить за отсутствием конфликтов. Подвесим дерево за некоторую вершину и предподсчитаем LCA для исходных пар вершин. Запустим dfs из корня и для каждого поддерева посчитаем количество вершин, являющихся началами исходных путей (переменная а), вершин, являющихся концами исходных путей (переменная b), и предпосчитанных LCA (переменная c). По этой информации можно ориентировать ребро из корня поддерева в предка: если a - c положительно, тогда вверх, если b - c положительно, тогда вниз, если оба положительны, тогда решения нет, если оба нули, то как угодно.
Время: O(n + qlq) где lq это время подсчета LCA на запрос; решение, использующее немного другой метод для последней части.
