Разбор задач Educational Codeforces Round 6

Revision ru2, by Edvard, 2016-01-21 22:22:44

620A - Professor GukiZ's Robot

Легко видеть, что ответ в задаче равен max(|x1 - x2, y1 - y2|).

С++ solution

Сложность: O(1).

620B - Grandfather Dovlet’s calculator

В этой задаче достаточно было пройти по всем числам от a до b и прибавить к ответу количество сегментов, необходимое для отображения очередного числа. Для подсчёта этой величины нужно пройти по всем десятичным цифрам числа и прибавить к ответу количество сегментов, наобходимой для отображения очередной цифры. Последние величины можно просто посчитать по картинке и вбить в один массив.

C++ solution

Сложность: O((b - a)logb).

620C - Pearls in a Row

Будем решать задачу жадно. Давайте набирать жемчужинки в самый левый хороший подотрезок по одному, начиная с первой жемчужинки. Как только подотрезок станет хорошим (то есть встретится повторение) начнём набирать новый хорощий подотрезок. Если мы не смогли набрать ни одного хорошего подотрезка, то ответ  - 1. В противном случае, в конце массива может остаться некоторое количество различных элементов, их нужно отнести к последнему набранному отрезку. Легко доказать, что такая жадность правильная: нужно рассмотреть первые два отрезка в оптимальном ответе и понять, что второй отрезок можно расширить пока первый не станет размера первого подотрезка в нашем ответе.

C++ solution

Сложность: O(nlogn).

620D - Professor GukiZ and Two Arrays

Случаи когда нужно сделать одну операцию или их не нужно делать вовсе легко разобрать в лоб (за O(n2)). Теперь рассмотрим случай когда нужно сделать две операции. Заметим, что можно считать, что после двух операций два элемента первого массива перейдёт во второй массив и наоборот, поскольку в противном случае то же самое можно сделать и за одну операцию и значит мы уже рассмотрели этот случай. Давайте переберём пару чисел, которая перейдёт во второй массив и сложим суммы в некоторую структуру данных (например, можно сложить в map в C++). Далее переберём пару чисел во втором массиве bi, bj и найдём в нашей структуре данных сумму v наиболее близкую к числу x = sa - sb + 2·(b[i] + b[j]) и обновим ответ значением |x - v|. Нужную сумму можно искать бинарным поиском по структуре данных (для map есть функция lower_bound).

C++ solution

Сложность: O((n2 + m2)log(n + m)).

620E - New Year Tree

Запустим dfs из корня дерева и выпишем вершины в порядке в котором их обойдёт dfs (эта перестановка называется обходом Эйлера). Легко видеть, что поддерево в этой перестановке является подотрезком. Заметим, что цветов всего 60, таким образом, мы можем хранить множество цветов просто как маску двоичных битов в 64-битном типе (*long long* в C++, long в Java). Построим дерево отрезков над Эйлеровым обходом, который поддерживает операцию покраски подотрезка и нахождения маски цветов на подотрезке.

С++ solution

Сложность: O(nlogn).

Tags учебный раунд 6, разбор задач

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Edvard 2016-01-22 02:01:59 2211
en4 English Edvard 2016-01-22 00:51:22 646
en3 English Edvard 2016-01-21 23:59:52 785
ru8 Russian Edvard 2016-01-21 23:58:33 6 Мелкая правка: '2 \cdot (b[i] + b[j])$ и обнов' -> '2 \cdot (b_i + b_j)$ и обнов'
ru7 Russian Edvard 2016-01-21 23:52:05 3 Мелкая правка: 'б (за $O(n^2)$). Тепер' -> 'б (за $O(nm)$). Тепер'
en2 English Edvard 2016-01-21 23:50:53 647
ru6 Russian Edvard 2016-01-21 23:44:22 2 Мелкая правка: 'новый хорощий подотре' -> 'новый хороший подотре'
en1 English Edvard 2016-01-21 23:34:37 694 Initial revision for English translation
ru5 Russian Edvard 2016-01-21 23:33:29 2 Мелкая правка: 'гментов, наобходимой ' -> 'гментов, необходимой '
ru4 Russian Edvard 2016-01-21 23:29:31 2 Мелкая правка: 'x(|x_1-x_2, y_1-y_2|)$' -> 'x(|x_1-x_2|, |y_1-y_2|)$'
ru3 Russian Edvard 2016-01-21 23:25:46 1987 Мелкая правка: 'но делать делать во' -
ru2 Russian Edvard 2016-01-21 22:22:44 615
ru1 Russian Edvard 2016-01-21 20:03:21 2438 Первая редакция (опубликовано)