При решении этой задачи нужно заметить, что важна лишь разность площадей исходного прямоугольника и собранного, а форма может быть любая. Тогда очевидно, что в качестве ответа, подойдет прямоугольник со сторонами C и nC, где n — натуральное число.

Число n несложно вычислить. Оно равно частному A·B и C² округленному либо вверх, либо вниз. Осталось выбрать из этих ответов наиболее выгодный и не забыть учесть, что нужно использовать хотя бы один квадрат C × C.

Несложно заметить, что операцию инверсии имеет смысл применять только к одной строке: если после применения инверсий первая и вторая строка совпали, то операции со второй строкой можно отменить и применить их к первой строке, после этого строки все еще будут равными. Также заметим, что операции можно применять в любом порядке.

Из этого факта следует простой жадный алгоритм: будем идти по первой строке слева направо и поддерживать ее текущее состояние. Если, находясь в i-м символе, s₁[i] ≠ s₂[i], тогда следует применить инверсию к символам i, i + 1 первой строки. Если в конце s₁[n] ≠ s₂[n], то нужной последовательности инверсий не существует и ответ равен  - 1.

Это задача на конструктивное построение примера.

Покажем сначала, как построить пример с максимальным значением k. Начнем с горизонтального отрезка, а затем каждым очередным вертикальным отрезком будем пересекать все предыдущие перпендикулярные ему, кроме того, который идет непосредственно перед ним. Пример для 14 отрезков показан на рисунке.

Чтобы получить ровно k нужно взять 2l отрезков, что l(l - 1) ≥ 2k > (l - 1)(l - 2), и построить максимальный пример, правда, возможно, заранее завершив последний отрезок. Оставшиеся же n - 2l отрезков добавим в начало трассы, разместив вокруг по спирали. Пример приведён на рисунке при n = 17 и k = 9.

Ограничение на k взято не просто так. Это максимальное число пересечений при фиксированном n. Желающие могут доказать это самостоятельно, подсказка: рассмотрите число пересечений пары отрезков n и n - 1 с парами n - 3 и n - 4, n - 5 и n - 6, ..., 2 и 1 (или просто отрезка 1, если n — чётное).

Сделаем дерево взвешенным и изначально установим у всех ребер вес 1. Теперь заметим, что если вместо удаления вершины изменять на 0 вес ребра, которое из нее идет в ее родителя, то ответ на запрос на поиск расстояния будет равен расстоянию между вершинами из запроса по взвешенным ребрам в исходном дереве.

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

Тогда расстояние между вершинами можно найти так: d_ab = d_a + d_b - 2·d_lca, где lca — это наименьший общий предок a и b, а d_v — это расстояние от корня до v.

Заметим, что недовольство жителей островов, которые находятся в одной компоненте связности, равно их начальному недовольству, умноженному на некоторую величину, которая общая для всех этих островов. Будем поддерживать эти значения для всех компонент.

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

Если при удалении ребра мы будем знать, какая из компонент меньшая, то сможем обойти все ее вершины и переместить их в другую компоненту (пересчитав все нужные суммы). Чтобы найти меньшую из компонент, запустим два обхода в ширину в двух компонентах одновременно. А когда один из них посетит все вершины в своей компоненте, не будем продолжать работу второго обхода в ширину. Такой алгоритм работает за время, пропорциональное размеру меньшей из компонент.