Задачу можно решать разными способами, но я попоробую рассказать самое короткое решение, которое только смог придумать.

Найдем bounding box закрашенных клеточек. Пускай мы будем знать его левую границу l, правую границу r, верхнюю границу u и нижнюю границу d. Теперь заметим, что у нас может быть только два случая:

1. Левая верхняя клетка одного квадрата находится в (u, l), правая нижняя клетка другого квадрата находится в (d, r).

2. Левая нижняя клетка одного квадрата находится в (d, l), правая верхняя клетка другого квадрата находится в (u, r).

Рассмотрим первый случай. Мы уже знаем, что первый квадрат находится в (u, l). Осталось найти, где находится второй квадрат. Для этого переберем размер k квадратов. Теперь осталось заметить, что нам достаточно проверять, закрашены ли клетки на границах bounding box'a (не все, а лишь те, что находятся на расстоянии k от уголков), чтобы определить, не взяли ли мы слишком большое k. Теперь мы с легкостью можем восстановить позицию второго квадрата: (d - k + 1, r - k + 1).

Второй случай аналогичен первому.

Сложность решения: O(n²).

Какие планки нам выгодно красить в первую очередь? А какие в последнюю?

Подсчитаем, какое количество планок нам нужно для i-го цвета. Теперь заметим, что закрашенные в нужный цвет планки мы уже никогда не сможем перекрасить. Поэтому будем красить жадно, стараясь «правильно» закрашивать как можно меньшее количество планок. Для этого отсортируем цвета по частоте во входных данных. Ну а дальше проходим и за линейное время считаем ответ.

Сложность решения: .

Возможно, с упорядоченными данными проще работать...

Попробуем зафиксировать какое-то число. Пусть это будет i. Есть числа меньшие, чем i, а есть...

Попробуем разбить все числа на группы размера i. Возможно, в таких группах будет проще подсчитывать сумму остатков.

Моя любимая задача на этом туре. Реализация — короткая, а идея — суперская.

Воспользуемся сортировкой подсчетом. Ответ будем считать как , где , a cnt_i — количество чисел равных i. Осталось эффективно подсчитывать sum_i.

Заметим, что все числа меньшие i дают в качестве остатка свое собственное значение, поэтому нам достаточно подсчитать сумму всех чисел, меньших i. С большими числами поступим похитрее. Разобьем их на такие отрезки: [i, 2·i), [2·i, 3·i), [3·i, 4·i), ... Научимся быстро находить ответ для таких отрезков.

Раcсмотрим отрезок [k·i, (k + 1)·i). Заметим, что число k·i + j при делении на i дает остаток j. Поэтому, если мы просто прибавим к ответу число k·i + j, то ответ будет увеличен на k·i больше, чем нужно. Поэтому, если мы сложим все числа из отрезка [k·i, (k + 1)·i), то нам нужно будет убрать (k·i)·cnt_{k·i..(k + 1)·i}. Поэтому сумму остатков на таком промежутке можно вычислить как sum_{k·i..(k + 1)·i} - (k·i)·cnt_{k·i..(k + 1)·i}.

Такое решение требует O(n) времени на сортировку и на вычисление ответа.

Количество начальных вершин совпадает с количеством путей, да? Вместо того, чтобы сортировать строки, попробуйте отсортировать вершины. А зная k-ю начальную вершину можно и сам путь найти.

Если склеить два ребра длинны 1, то получится одно ребро длины 2. А если два длинны 2, то получится одно длины 4...

Ничего страшного не произойдет, если мы случайно решим задачу для более длинных маршрутов.

Что-то я разленился. Если в кратце, то задача аналогична построению суффиксного массива. Что забавно, но можно написать решение, которое практически не зависит от m. Давайте будем считать m = 2²⁰, что даже больше, чем может быть во входных данных. Удлинять ребра в два раза будем точно так же как и в методе двоичного подъема.

Сложность по времени: .