Найдем 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. Возможно, в таких группах будет проще подсчитывать сумму остатков.

Воспользуемся сортировкой подсчетом. Ответ будем считать как , где , 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...

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