616A - Сравнение длинных чисел

Замечу, что в этой задаче решения использующие стандартные типы длинной арифметики (класс BigInteger в Java, стандартные длинные числа в Pyhon) не должны проходить. Это связано с тем, что они хранят число не в десятичной системе счиления и соответственно при создании длинного числа происходит его конвертация из десятичной системы счисления, которая является тяжёлой операцией и работает обычно за O(n²), где n — длина числа.

Для решения задачи можно просто добавить лидирующих нулей к более короткому числу, а далее сравнить, получившиеся строки в лексикографическом порядке (алфавитном).

С++ solution

Python solution

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

616B - Ужин с Наташей

В этой задаче нужно было сначала найти в каждой строке минимум, а далее взять максимум, получившихся минимумов. Это соответствует стратегии Павла и Наташи.

C++ solution

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

616C - Лабиринт

Давайте сначала пронумеруем все компоненты связности, запомним для каждой её размер, а также для каждой свободной клетки запомним номер её компоненты. Это можно сделать с помощью одного обхода в глубину. Теперь ответ для непроходимой клетки будет равен единице плюс размеры всех соседних различных компонент. Соседних в смысле компонент всех соседних клеток (в общем случае четырёх).

C++ solution

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

616D - Наидлиннейший k-хороший подотрезок

Эту задачу мы решили дать поскольку на страницах Codeforces часто видим вопрос "Что такое метод двух указателей?". Эта задача является типичным примером задачи, решаемой этим методом.

Будем искать для каждой левой границы l наибольшую границу r такую, что отрезок (l, r) k-хороший. Заметим следующее: если некоторый отрезок (l, r) k-хороший, то отрезок (l + 1, r), тоже является хорошим. Таким образом, поиск максимальной правой границы для левого конца l + 1 мы можем начинать с максимальной правой границы для левого конца l. Далее просто будем поддерживать в массиве cnt_x для каждого числа x количество его вхождений в текущий отрезок (l, r), а также количество различных чисел. Будем пытаться двигать правую границу пока можем, далее двигать на единицу левую границу. Итого два указателя l, r вместе передвинутся 2n раз.

C++ solution

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

616E - Сумма остатков

616F - Дорогие строки