Эта задача решается жадным алгоритмом. Давайте отсортируем людей из первой очереди по тому, сколько они готовы пройти. И будем их поочерёдно расставлять, выбирая каждый раз место следующим образом: среди незанятых мест, до которых он может дойти, выберем то, которое наиболее удалено от второй очереди (точки с координатами (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).