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

Правка ru8, от Edvard, 2016-01-21 23:58:33

620A - Робот профессора GukiZ

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

С++ solution

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

620B - Калькулятор дедушки Довлета

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

C++ solution

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

620C - Жемчужинки

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

C++ solution

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

620D - Профессор GukiZ и два массива

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

C++ solution

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

620E - Новогодняя ёлка

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

С++ solution

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

620F - Ксоры на подотрезке

В этой задаче неудачно были подобраны ограничения в связи с чем некоторые участники сдали решения со сложностью O(n2 + m).

Заметим сначала, что . Значения f(0, x) можно было просто предподсчитать или заметить что в зависимости от остатка числа x по модулю 4 значение функции равно x, 1, x + 1, 0 соответственно.

Воспользуемся алгоритмом Мо. Разобьём все запросы на блоков по левому концу. Внутри каждого блока отсортируем запросы по правому концу. Пусть r наибольшая левая граница внутри блока, тогда все левые границы отстоят от r на расстояние не более чем , а правые границы идут в порядке неубывания, поэтому их можно двигать по одному (в сумме на один блок мы сделаем не более n передвижений правой границы). Передвигая правую границу, внутри блока для чисел в позициях от r + 1 до текущей правой границы будем поддерживать два бора: первый для значений f(0, x - 1), второй для значений f(0, x), в первом будем поддерживать наименьшее значение x, во втором — наибольшее. Понятно как добавлять число в боры, после добавлений нужно найти наибольшее значение, которое может образовать текущий x для этого будем спускаться по первому бору, поддерживая инвариант того, что в текущем поддереве минимальное значение не больше x, и по возможности ходить по биту отличному от нашего. Аналогичное нужно делать во втором боре, только нужно поддерживать инвариант, что максимальное значение не меньше x. После того как для текущего запроса мы сдвинули правую границу на сколько нужно, нужно пройти от левой границы запроса до r и, не добавляя значения в бор, обновить ответы. Ещё отдельно для каждого запроса в новом (пустом) боре нужно пройти от левой границы до r добавляя значения в бор и обновляя ответ.

С++ solution: в коде 0-й бор соответсвует второму, а 1-й — первому.

Сложность: .

Теги учебный раунд 6, разбор задач

История

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