Эта задача решается жадным алгоритмом. Давайте отсортируем людей из первой очереди по тому, сколько они готовы пройти. И будем их поочерёдно расставлять, выбирая каждый раз место следующим образом: среди незанятых мест, до которых он может дойти, выберем то, которое наиболее удалено от второй очереди (точки с координатами (0, m + 1)). После распределения мест для первой очереди, мы сортируем людей из второй очереди и жадно расставляем их по свободным местам, начиная с минимального.

В задаче проходили грамотно написанные решения с асимптотикой не более O((nm)²), которые соответствуют описанию этого жадного алгоритма. Если пользоваться сетом, то асимптотику можно сократить до O(nm log(nm))

Разобьем граф на блоки — циклы и мосты. Нужно из каждого цикла удалить одно ребро, и при этом оставить в графе максимально много различных цветов.

Построим двудольный граф, в котором левая доля — блоки, правая — цвета. Из блока проведем ребра в каждый цвет, который есть в этом блоке (если цвет встречается несколько раз, проведем несколько ребер). Из цветов ребра в сток. Из истока ребра в блок, если блок — мост, то с пропускной способностью 1, иначе с пропускной способностью на 1 меньше длины цикла. Несложно видеть, что максимальный поток в этом графе и будет являться ответом.

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

Задача решается придумыванием конструктивного алгоритма.

• Для упрощения разбора случаев для всех n, m < 5 запустим полный перебор. Здесь, чтобы избежать неасимптотических оптимизаций и уложиться в TL, стоило сделать предподсчет.
• Теперь, не умоляя общности, можем считать, что m ≥ 5.
• Начнем расставлять звездочки подряд по таблице (по строчкам сверху вниз, в каждой строке слева направо). При добавлении каждой звездочки (кроме крайних) добавляется 4 новых уголка. При добавлении звездочки в конец строки добавляется 3 новых уголка, в начало — 1. Прекращаем процесс как только k становится меньше 4 или как только свободных клеток в таблице остается меньше 5.
• Дальнейшее развитие событий делится на два случая:
  • осталась свободная строка
  • не осталось свободной строки
• Первый случай. Раз осталась свободная строка, значит мы прервались, потому что k стало меньше 4. Тогда:
  • k = 0: ничего добавлять не надо, все сошлось
  • k = 1: если в текущей строке поставлено уже  ≥ 2 звездочки, поставим звездочку в начало следующей строки, а если нет, то в конец текущей
  • k = 2: если в текущей строке поставлено уже  ≥ 3 звездочки, поставим звездочку во второй столбец следующей строки, а если нет, то в предпоследнюю клетку текущей
  • k = 3: если в текущей строке поставлено уже  ≥ 4 звездочек, поставим звездочки в первый и третий столбец следующей строки. Если поставлено три, поставим во второй столбец следующей и в предпоследний текущей. Если две — в начало следующей строки и в пред-предпоследний столбец текущей. Если одна — ставим звездочки в m - 1 и m - 3 столбцы текущей строки (нумерация с нуля).
• Второй случай. В таблице осталось 4 свободных клетки, куда можно поставить звездочки. Несложным перебором случаев можно вывести, что, ставя звездочки в эти клетки, можно получить следующие значения k: {0, 1, 2, 3, 4, 5, 6, 8, 9, 12, 15}. Разбор этих случаев остается читателю в качестве упражнения.
• Также стоило не забыть про случай прямоугольника 3 × m, где m ≥ 5 и k = 2 * (m - 1) - 8 — в этом случае надо оставить первый столбец пустым, а все остальные полностью заполнить.

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

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

Наивная реализация этого алгоритма требовала O(nm) памяти и O(nm²) времени, поэтому надо использовать дерево отрезков для оптимизации подсчета суммы при переходах динамического программирования, а также хранить не все поле, а только текущий столбец. Таким образом получается O(m) памяти и время работы составляет O(n log m).

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

Основная идея решения заключается в том, что нам не нужно проверять, что число можно отличить от всех 10ⁿ - 1 других. Утверждается, что если мы можем отличить число от такого же, в котором изменили ровно одну цифру, то можем отличить и от всех других чисел. Таким образом необходимо узнать первый момент времени, когда можно отличить число от 9n других.

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

Для начала заметим, что в ответ обязательно войдут min(k - n, 0) максимальных по сумме отрезков. Для решения задачи найдем сумму min(k - n, 0) максимальных отрезков и элементы, которые они покрывают, а так же следующие за ними min(k, n) отрезков в явном виде. Сделать это можно с помощью бинарного поиска по значению суммы на отрезке и структуры данных вроде дерева Фенвика: для заданного значения суммы дерево Фенвика поможет найти и количество отрезков с хотя бы такой суммой, и сумму отрезков с хотя бы такой суммой, и множество покрытых элементов, и перечислить все отрезки с такой суммой за их количество. Эту часть решения можно сделать за O(n log² n).

Немного отвлечемся, рассмотрим, как можно решать задачу за n² log n. Пускай мы перебрали x — количество максимальных по сумме отрезков в ответе (O(n) вариантов, поскольку min(k - n, 0) максимальных отрезков войдут в ответ обязательно). Пусть элементы с индексами i₁, ..., i_m остались непокрыты, и нужно их покрыть используя k - x отрезков. Заметим, что каждый из этих k - x отрезков обязан содержать хотя бы один i_j-й, при чем два отрезка не могут пересекаться по какому-нибудь i_j-му. Можно отсортировать эти k - x отрезков лексикографически, и если l-й отрезок покрывает число i_j, а l + 1-й отрезок покрывает i_j + 1, то эти два отрезка либо пересекаются по какому-то подотрезку отрезка [i_j + 1; i_j + 1 - 1], либо не пересекаются по какому-то подотрезку отрезка [i_j + 1; i_j + 1 - 1]. Таким образом, если для каждого отрезка [i_j + 1; i_j + 1 - 1] выписать число, равное максимуму из его максимального подотрезка и минус минимального, то наилучшее покрытие — взять весь массив, но не взять минимальный префикс (до i₁), минимальный суффикс (от i_m), и k - x максимальных чисел среди выписанных. Таким образом, решили задачу за n² log n.

Чтобы соптимизировать это решение, можно хранить отрезки [i_j + 1; i_j + 1 - 1] в упорядоченном множестве. При добавлении нового максимального отрезка нужно удалить несколько i_j-х, пересчитать в сете максимальные и минимальные подотрезки для затронутых отрезков (это можно сделать за O(1), зная максимальную сумму на префиксе и суффиксе подотрезка), и взять сумму k - x максимальных чисел из множества. Суммарно удалений i_j-х O(n), поэтому вся эта часть работает за O(n log n).

При решении этой задачи нужно заметить, что важна лишь разность площадей исходного прямоугольника и собранного, а форма может быть любая. Тогда очевидно, что в качестве ответа, подойдет прямоугольник со сторонами 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.

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

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

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