620A - Professor GukiZ's Robot

Легко видеть, что ответ в задаче равен max(|x₁ - x₂, y₁ - y₂|).

С++ 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(n²)). Теперь рассмотрим случай когда нужно сделать две операции. Заметим, что можно считать, что после двух операций два элемента первого массива перейдёт во второй массив и наоборот, поскольку в противном случае то же самое можно сделать и за одну операцию и значит мы уже рассмотрели этот случай. Давайте переберём пару чисел, которая перейдёт во второй массив и сложим суммы в некоторую структуру данных (например, можно сложить в map в C++). Далее переберём пару чисел во втором массиве b_i, b_j и найдём в нашей структуре данных сумму v наиболее близкую к числу x = s_a - s_b + 2·(b[i] + b[j]) и обновим ответ значением |x - v|. Нужную сумму можно искать бинарным поиском по структуре данных (для map есть функция lower_bound).

C++ solution

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