Заметим, что если сила босса равна x, то сумма сил всех врагов равна 2x. Следовательно, чтобы найти силу босса, необходимо посчитать суммарную силу всех врагов и разделить ее на 2. После этого необходимо найти какого-нибудь врага с такой силой и поменять это значение в массиве f со значением последнего врага.

Будем обрабатывать пассажиров по очереди и для каждого определять, кем он мог бы быть. Сразу заметим, что Розовый Рейнджер может есть куда угодно, поэтому каждый пассажир мог бы быть Розовым.

Для каждого места будем помнить, свободно ли оно. Для этого заведем unordered_set, в котором будем хранить занятые места. Проверим, мог бы очередной пассажир быть Красным Рейнджером. Для этого найдём место, на которое сел бы Красный. Переберём циклом ряд от 1 до n, если попался ряд, в котором есть свободное место, выбираем левое, если оно свободно, или правое, если нет — это и есть место, куда сел бы Красный. Поскольку он выбирает место однозначно, мы можем определить, мог бы этот пассажир быть Красным — нужно проверить, что он сел именно на это место. Таким же образом узнаем, куда сели бы Синий, Жёлтый и Чёрный – разница будет в порядке перебора рядов (от 1 до n или наоборот) и в порядке выбора места в ряду (сначала левое или правое). После обработки пассажира отметим его место как занятое.

Решение работает за O(nk) и использует O(k) памяти.

Чтобы улучшить решение, заметим, что каждый из циклов останавливается, когда находит ряд, в котором есть свободное место. Это означает, что нужно быстро находить первый и последний незанятые ряды. Будем поддерживать эти значения — first и last. Изначально first = 1, last = n. После каждой итерации цикла обновим эти значения. Будем увеличивать first на 1, пока ряд first занят, затем уменьшать last на 1, пока ряд last занят. Занятых рядов не может оказаться больше k / 2, поэтому first и last сделают O(k) шагов. Таким образом, улучшенное решение работает за O(k) и проходит все тесты.

Предпочитаем массивы: R[a][b] — количество фрагментов у красного рейнджера, у которых первая цифра равна a, а последняя равна b; G[a] — количество фрагментов у зеленого рейнджера, у которых последняя цифра равна a; и B[b] — количество фрагментов у синего рейндждера, у которых первая цифра равна b.

Если бы у разных рейнджеров не было одинаковых моделей фрагментов, ответ был бы равен сумме по всем a и b значений G[a]·R[a][b]·B[b].

Чтобы учесть ситуацию, когда у какой-то пары совпадают модели, посчитаем количество пар фрагментов с одинаковым номером модели у красного и синего, красного и зеленого и синего и зеленого рейнджеров, соответственно (например, с помощью std::map). Заметим, что подходящими являются только номера, у которых первая и последняя цифра совпадает. Воспользуемся формулой включения-исключения, вычтем из ответа число таких пар, и добавим удвоенное количество троек фрагментов, когда у всех трех рейнджеров совпадают модели.

Будем решать задачу динамическим программированием по профилю. Найдем для примера максимальное количество рыцарей.

Пусть dp[i][mask_prev][mask_cur] — максимальное количество рыцарей, которые могут быть в расстановке из первых i столбцов, mask_cur — маска i-го столбца, а mask_prev — (i - 1)-го.

Затем переберем маску для (i + 1)-го столбца и проверим выполняются ли ограничения на соседей, для солдат из i-го столбца, так как теперь известны все их соседи.

Для первого и последнего столбца ограничения нужно проверять отдельно, потому что у них нет одного из соседей.

База: dp[2][mask_prev][mask_cur] равно количеству единиц в mask_prev и mask_cur, если mask_prev может стоять слева от mask_cur.

Переход: dp[i + 1][mask_cur][mask_next] = dp[i][mask_prev][mask_cur] + ones(mask_next), где ones(x) — количество единиц в маске x.

Ответ будет максимумом среди всех dp[k][mask_prev][mask_cur], таких что mask_cur может находится справа от mask_prev.

Наконец заметим, что случай k = 1 стоит разобрать отдельно, поскольку в этом случае нет предыдущего столбца.

Расскажем об основной идее решения. Во-первых, рассмотрим отдельно все параллелепипеды, у которых две или три стороны совпадают, это можно сделать за O(n).

Пусть теперь все три стороны различны. Построим следующий неориентированный граф: вершинами будут возможные длины сторон, соединим ребром числа a и b, если имеется хотя бы два листа размером a × b. Задача свелась к рассмотрению треугольников в получившемся графе, это можно сделать за O(n² / w) или O(nsqrt(n)) (здесь w обозначет размер машинного слва, 32 или 64, этот множитель возникает при битовом сжатии в поиске треугольников).