Codeforces Round #310 Editorial

Правка ru15, от Lord_F, 2016-01-28 12:44:35

Привет всем!

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)

555A - Дело о матрешках

Предположим нам не нужно разбирать некоторую последовательность. Тогда ни в одну из матрешек этой последовательности не нужно вставить другую. Поэтому нам не нужно разбирать последовательность матрешек лишь в случае, если они идут подряд, начиная с 1. Пусть длина этой последовательности равна l. Тогда вытащить одну из другой нам нужно будет n - k - l + 1 раз, при этом останется одна цепочка из l матрешек 1 → 2 → ... → l и остальные цепочки по одной матрешке. Всего n - k + 1 цепочка, поэтому вложить одну в другую нужно n - k раз. Всего будет сделано 2n - l - 2k + 1 операций.

Время: O(n); решение.

555B - Дело о беглеце

Между островами i и i + 1 мы можем положить мост, длина которого попадает в отрезок [li + 1 - ri;ri + 1 - li]. Получаем задачу: есть n - 1 отрезков и m точек на прямой, необходимо каждому отрезку сопоставить какую-то точку, лежащую в нем, причем каждую точку можно сопоставить только одному отрезку. Будем идти по точкам слева направо, и хранить в сете отрезки, которые еще ничему не сопоставлены и которые содержат рассматриваемую точку. Пусть мы обрабатываем очередную точку. Сначала добавим в сет все отрезки, которые начинаются в этой точке. Далее выберем из них тот, чей правый конец имеет наименьшую координату. Утверждается, что этот алгоритм находит ответ, если он есть. Предположим это не так. Пусть мы на каком-то шаге выбрали для точки A другой отрезок (пропускать точку не имеет смысла). Тогда посмотрим, какая точка B сопоставлена отрезку, который был бы выбран нашим решением. Точка B лежит заведомо правее A. Поэтому мы можем поменять точки для этих отрезков и снова получить ответ.

Время: O((n + m)log(n + m)); решение.

555C - Дело о шоколаде

Решим задачу с помощью двух деревьев отрезков: для столбцов и для строк. Будем хранить для каждого столбца самую нижнюю съеденную дольку, а для каждой строки — самую левую. Пусть приходит запрос 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 на запрос; решение, использующее немного другой метод для последней части.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru15 Русский Lord_F 2016-01-28 12:44:35 4 Мелкая правка: 'сделаем $max(#единиц,#' -> 'сделаем $min(#единиц,#'
ru14 Русский Lord_F 2015-07-19 06:54:38 10 Мелкая правка: 'ntu.com/11788459/), исполь' -> 'ntu.com/11902227/), исполь'
en17 Английский Lord_F 2015-07-19 06:54:27 10 Tiny change: 'ntu.com/11788459/) that us' -> 'ntu.com/11902227/) that us'
ru13 Русский Lord_F 2015-06-29 21:07:43 2 Мелкая правка: 'елано $2n-m-2k+1$ опе' -> 'елано $2n-l-2k+1$ опе'
ru12 Русский Lord_F 2015-06-29 16:27:01 28
en16 Английский Lord_F 2015-06-29 16:26:01 2 Tiny change: ' $2n-k-2l+2$ operatio' -> ' $2n-k-2l+1$ operatio'
ru11 Русский Lord_F 2015-06-29 16:25:30 12005
ru10 Русский Lord_F 2015-06-29 15:41:36 35 Мелкая правка: 's shorter we procee' -> 's shorter _or current step is the first one_ we procee'
en15 Английский Lord_F 2015-06-29 15:40:24 35 Tiny change: 's shorter we procee' -
ru9 Русский Lord_F 2015-06-28 23:06:48 2 Мелкая правка: 'Time: $O(nl_q)$ wher' -> 'Time: $O(n+ql_q)$ wher'
en14 Английский Lord_F 2015-06-28 23:05:55 2 Tiny change: 'Time: $O(nl_q)$ wher' -> 'Time: $O(n+ql_q)$ wher'
ru8 Русский Lord_F 2015-06-28 19:02:24 314
en13 Английский Lord_F 2015-06-28 19:01:34 314
ru7 Русский Lord_F 2015-06-28 18:49:48 62
ru6 Русский Lord_F 2015-06-28 18:49:31 1514
en12 Английский Lord_F 2015-06-28 18:48:19 22
en11 Английский Lord_F 2015-06-28 18:47:44 1476
en10 Английский Lord_F 2015-06-28 18:05:08 1
en9 Английский Lord_F 2015-06-28 18:04:19 1038
ru5 Русский Lord_F 2015-06-28 18:02:54 1039
ru4 Русский Lord_F 2015-06-28 17:25:21 3 Мелкая правка: 'es. $2n-k-l+1$ operatio' -> 'es. $2n-k-2l+2$ operatio'
en8 Английский Lord_F 2015-06-28 17:25:01 3 Tiny change: 'es. $2n-k-l+1$ operatio' -> 'es. $2n-k-2l+2$ operatio'
en7 Английский Lord_F 2015-06-28 17:23:45 271
ru3 Русский Lord_F 2015-06-28 17:21:24 3567
en6 Английский Lord_F 2015-06-28 16:56:11 636 Tiny change: 'ogq)$ or $qlogq$; solutio' -
ru2 Русский Lord_F 2015-06-28 16:37:50 60
en5 Английский Lord_F 2015-06-28 16:33:48 1080
en4 Английский Lord_F 2015-06-28 15:58:49 657
en3 Английский Lord_F 2015-06-28 15:34:14 12 Tiny change: '1$ output \t{Yes} else \t{No}. But thi' -> '1$ output "Yes" else "No". But thi'
en2 Английский Lord_F 2015-06-28 15:27:30 1038
ru1 Русский Lord_F 2015-06-27 23:03:38 332 Первая редакция перевода на Русский
en1 Английский Lord_F 2015-06-27 22:57:25 327 Initial revision (published)