Codeforces Round #310 Editorial

Revision ru12, by Lord_F, 2015-06-29 16:27:01

Привет всем!

556A - Case of the Zeros and Ones

Если в последовательности остались хотя бы одни единица и ноль, тогда существует подстрока 01 или 10, которую можно удалить. При этом порядок удаления не важен: в любом случае мы сделаем max(#единиц, #нулей) операций, так как за раз удаляется один ноль и одна единица. Поэтому ответ: #единиц + #нулей - 2min(#единиц, #нулей) = |#единиц - #нулей|.

Время: O(n).

556B - Case of Fake Numbers

Заметим, что через n нажатий кнопки система приходит в исходное положение. Поэтому самое простое решение — это промоделировать процесс из n шагов и, если на одном из них встретится последовательность 0, 1, ... , n - 1, выдать "Yes", иначе "No". Но можно это решение ускорить. Например, сразу по значению первого элемента определить нужное количество нажатий, перейти в это положение и один раз проверить.

Время: O(n) или O(n2); решения: O(n) и O(n^2)

555A - Case of Matryoshkas

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

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

555B - Case of Fugitive

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

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

555C - Case of Chocolate

Решим задачу с помощью двух деревьев отрезков: для столбцов и для строк. Будем хранить для каждого столбца самую нижнюю съеденную дольку, а для каждой строки — самую левую. Пусть приходит запрос x y L. Находим значение в дереве отрезков для строк на месте y. Пусть это значение равно ans. Теперь нужно вывести x - ans и в дереве для столбцов обновить значения на отрезке [ans + 1, x] до y, а в горизонтальном обновить значение в элементе y дo x. Аналогично с запросами типа U. Чтобы разобраться с большими ограничениями на n нужно писать либо неявное дерево отрезков, либо сжатие координат.

Время: O(qlogq) или O(qlogn); решения: 1 and 2.

555D - Case of a Top Secret

Назовем активной длиной 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 - Case of Computer Network

Для начала, сведем задачу к задаче на дереве. В каждой компоненте двусвязности ориентируем ребра в порядке обхода DFS. Утверждается, что мы получим компоненту сильной связности. Пусть это не так. Тогда граф можно разбить на два подграфа A и B так, что не существует ребер, идущих из B в A. Причем изначально ребер между A и B хотя бы два. Но это невозможно, так как, зайдя в эту компоненту B, мы должны будем выйти по одному из ребер между A и B, а это невозможно. Противоречие.

Поэтому мы можем сжать все компоненты двусвязности.

Теперь надо обработать несколько запросов вида “ориентировать ребра на пути” и проследить за отсутствием конфликтов. Подвесим дерево за некоторую вершину и предподсчитаем LCA для исходных пар вершин. Запустим dfs из корня и для каждого поддерева посчитаем количество вершин, являющихся началами исходных путей (переменная а), вершин, являющихся концами исходных путей (переменная b), и предпосчитанных LCA (переменная c). По этой информации можно ориентировать ребро из корня поддерева в предка: если a - c положительно, тогда вверх, если b - c положительно, тогда вниз, если оба положительны, тогда решения нет, если оба нули, то как угодно.

Время: O(n + qlq) где lq это время подсчета LCA на запрос; решение, использующее немного другой метод для последней части.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru15 Russian Lord_F 2016-01-28 12:44:35 4 Мелкая правка: 'сделаем $max(#единиц,#' -> 'сделаем $min(#единиц,#'
ru14 Russian Lord_F 2015-07-19 06:54:38 10 Мелкая правка: 'ntu.com/11788459/), исполь' -> 'ntu.com/11902227/), исполь'
en17 English Lord_F 2015-07-19 06:54:27 10 Tiny change: 'ntu.com/11788459/) that us' -> 'ntu.com/11902227/) that us'
ru13 Russian Lord_F 2015-06-29 21:07:43 2 Мелкая правка: 'елано $2n-m-2k+1$ опе' -> 'елано $2n-l-2k+1$ опе'
ru12 Russian Lord_F 2015-06-29 16:27:01 28
en16 English Lord_F 2015-06-29 16:26:01 2 Tiny change: ' $2n-k-2l+2$ operatio' -> ' $2n-k-2l+1$ operatio'
ru11 Russian Lord_F 2015-06-29 16:25:30 12005
ru10 Russian 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 English Lord_F 2015-06-29 15:40:24 35 Tiny change: 's shorter we procee' -
ru9 Russian Lord_F 2015-06-28 23:06:48 2 Мелкая правка: 'Time: $O(nl_q)$ wher' -> 'Time: $O(n+ql_q)$ wher'
en14 English Lord_F 2015-06-28 23:05:55 2 Tiny change: 'Time: $O(nl_q)$ wher' -> 'Time: $O(n+ql_q)$ wher'
ru8 Russian Lord_F 2015-06-28 19:02:24 314
en13 English Lord_F 2015-06-28 19:01:34 314
ru7 Russian Lord_F 2015-06-28 18:49:48 62
ru6 Russian Lord_F 2015-06-28 18:49:31 1514
en12 English Lord_F 2015-06-28 18:48:19 22
en11 English Lord_F 2015-06-28 18:47:44 1476
en10 English Lord_F 2015-06-28 18:05:08 1
en9 English Lord_F 2015-06-28 18:04:19 1038
ru5 Russian Lord_F 2015-06-28 18:02:54 1039
ru4 Russian Lord_F 2015-06-28 17:25:21 3 Мелкая правка: 'es. $2n-k-l+1$ operatio' -> 'es. $2n-k-2l+2$ operatio'
en8 English Lord_F 2015-06-28 17:25:01 3 Tiny change: 'es. $2n-k-l+1$ operatio' -> 'es. $2n-k-2l+2$ operatio'
en7 English Lord_F 2015-06-28 17:23:45 271
ru3 Russian Lord_F 2015-06-28 17:21:24 3567
en6 English Lord_F 2015-06-28 16:56:11 636 Tiny change: 'ogq)$ or $qlogq$; solutio' -
ru2 Russian Lord_F 2015-06-28 16:37:50 60
en5 English Lord_F 2015-06-28 16:33:48 1080
en4 English Lord_F 2015-06-28 15:58:49 657
en3 English 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 English Lord_F 2015-06-28 15:27:30 1038
ru1 Russian Lord_F 2015-06-27 23:03:38 332 Первая редакция перевода на Русский
en1 English Lord_F 2015-06-27 22:57:25 327 Initial revision (published)