Сокровищница

Требуется построить несколько вложенных друг в друга латинских квадратов с заданными размерами и совпадающими верхними-левыми углами.

Для начала, научимся определять, когда решения не существует. Докажем, что размеры вложенных друг в друга латинских квадратов должны отличаться хотя бы в $$$2$$$ раза. Допустим, существуют два латинских квадрата с размерами $$$a \times a$$$ и $$$b \times b$$$, вложенные друг в друга, и при этом $$$a < b$$$ и $$$a \cdot 2 > b$$$. Тогда рассмотрим $$$a$$$ чисел, которые встречаются в меньшем квадрате. Они должны встречаться в каждой строке большого. При этом, в строках и столбцах с номерами от $$$1$$$ до $$$a$$$ они уже встречаются в меньшем квадрате. Значит, в строках с номерами $$$a + 1 \dots b$$$ должно быть по $$$a$$$ таких чисел. При этом, все эти числа должны стоять в столбцах с номерами $$$a + 1 \dots b$$$. Поэтому, с одной стороны нужно поставить хотя бы $$$(b - a) \cdot a$$$ чисел, а с другой стороны у нас есть для этого только $$$(b - a) \cdot (b - a)$$$ доступных клеток. Из предположения, что $$$a \cdot 2 > b$$$ следует, что доступных клеток меньше количества чисел, которые необходимо поставить. Пришли к противоречию. Значит, размеры двух вложенных латинских квадратов должны отличаться хотя бы в $$$2$$$ раза.

Оказывается, что во всех остальных случаях решение можно построить. Научимся решать задачу для двух квадратов размерами $$$a \times a$$$ и $$$b \times b$$$. Тогда мы будем уметь решать задачу для любой последовательности $$$a_1, a_2, \dots, a_n$$$ просто решая задачу сначала для $$$a_1$$$ и $$$a_2$$$, потом для $$$a_2$$$ и $$$a_3$$$ и так далее. Для начала, расставим числа $$$1 \dots a$$$ на пересечении строк и столбцов с номерами $$$a + 1 \dots b$$$. Это можно сделать просто расставив $$$1$$$ на главной диагонали, $$$2$$$ на один правее, $$$3$$$ еще на один правее и так далее (после столбца номер $$$b$$$ идет столбец номер $$$a + 1$$$). Осталось расставить числа $$$a + 1 \dots b$$$. Причем, каждое число должно встречаться ровно в одной строке и ровно в одном столбце. Несложно заметить, что позиции одного числа соответствуют ребрам из полного паросочетания в двудольном графе, левой долей которого являются строки, правой долей — столбцы, а ребрами — свободные клетки. Докажем, что полное паросочетание всегда будет существовать. В общем случае, у нас есть матрица $$$x \times x$$$ и в каждом столбце и каждой строке свободны ровно $$$y$$$ клеток. Применим лемму Холла. Рассмотрим некоторое множество строк размера $$$k$$$. Из этого множества выходит ровно $$$k \times y$$$ ребер. По принципу Дирихле, ребра ведут минимум в $$$k$$$ столбцов. Значит, лемма Холла выполнена и полное паросочетание существует. Причем, оно будет существовать и после того, как мы найдем одно полное паросочетание и займем очередным числом соответствующие клетки. Для того, чтобы находить паросочетания, можно воспользоваться алгоритмом Куна или Хопкрофта-Карпа. В зависимости от выбранного алгоритма и от оптимальности кода, решение может проходить или не проходить последнюю подзадачу.