620A - Professor GukiZ's Robot
Легко видеть, что ответ в задаче равен max(|x1 - x2, y1 - y2|).
Сложность: O(1).
620B - Grandfather Dovlet’s calculator
В этой задаче достаточно было пройти по всем числам от a до b и прибавить к ответу количество сегментов, необходимое для отображения очередного числа. Для подсчёта этой величины нужно пройти по всем десятичным цифрам числа и прибавить к ответу количество сегментов, наобходимой для отображения очередной цифры. Последние величины можно просто посчитать по картинке и вбить в один массив.
Сложность: O((b - a)logb).
620C - Pearls in a Row
Будем решать задачу жадно. Давайте набирать жемчужинки в самый левый хороший подотрезок по одному, начиная с первой жемчужинки. Как только подотрезок станет хорошим (то есть встретится повторение) начнём набирать новый хорощий подотрезок. Если мы не смогли набрать ни одного хорошего подотрезка, то ответ - 1. В противном случае, в конце массива может остаться некоторое количество различных элементов, их нужно отнести к последнему набранному отрезку. Легко доказать, что такая жадность правильная: нужно рассмотреть первые два отрезка в оптимальном ответе и понять, что второй отрезок можно расширить пока первый не станет размера первого подотрезка в нашем ответе.
Сложность: 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).
Сложность: O((n2 + m2)log(n + m)).
620E - New Year Tree
Запустим dfs из корня дерева и выпишем вершины в порядке в котором их обойдёт dfs (эта перестановка называется обходом Эйлера). Легко видеть, что поддерево в этой перестановке является подотрезком. Заметим, что цветов всего 60, таким образом, мы можем хранить множество цветов просто как маску двоичных битов в 64-битном типе (*long long* в C++, long в Java). Построим дерево отрезков над Эйлеровым обходом, который поддерживает операцию покраски подотрезка и нахождения маски цветов на подотрезке.
Сложность: O(nlogn).
