Задача 7. Хорошие раскраски ≡

Условие

Назовем раскраску клеток таблицы n × m хорошей, если никакие четыре клетки, центры которых образуют вершины прямоугольника со сторонами, параллельными осям координат, не покрашены в один цвет.

Иначе говоря, для раскраски не должно быть такой четверки целых чисел x₁, x₂, y₁, y₂, что 1 ≤ x₁ < x₂ ≤ n, 1 ≤ y₁ < y₂ ≤ m, и клетки (x₁, y₁), (x₂, y₁), (x₁, y₂) и (x₂, y₂) покрашены в одинаковый цвет.

Требуется написать программу, которая по заданным целым числам n, m и c находит любую хорошую раскраску таблицы n × m в c цветов.

Формат входных данных

В первой строке записаны три целых числа n, m, c.

Гарантируется, что для заданных во входных данных значений существует хотя бы одна хорошая раскраска.

Формат выходных данных

Выведите n строк по m чисел в каждой.

В качестве j-го числа i-й строки выведите a_i,j — цвет клетки (i,j) (1 ≤ a_i,j ≤ c).

Если есть несколько хороших раскрасок, можно вывести любую из них.

Ограничения

2 ≤ n, m ≤ 10, 2 ≤ c ≤ 3

Система оценки

Кроме теста из примера в этой задаче 20 тестов, каждый независимо оценивается в 5 баллов. Среди этих тестов в пяти тестах c = 2 и в пятнадцати тестах c = 3.

Для каждого теста сообщается результат проверки на этом тесте.

Примеры тестов

2 2 2

1 2 
2 2 

Разбор

Эта задача — довольно нетрадиционная для олимпиад по информатике. Вместо конкретного конструктивного или алгоритмического решения участникам предлагалось поэкспериментировать с эвристиками и перебором.

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

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

Перейдем теперь к рассмотрению основных идей переборных решений и решений с помощью локальных оптимизаций.

Перебор

Самое простое решение это перебор за O(c^n ⋅ m), можно перебирать все раскраски простой рекурсией: перебирать цвета клеток в порядке сортировки по строкам и при равенстве по столбцам, и проверять, подходит ли итоговое поле. Чтобы оптимизировать это решение, в процессе перебора подходящих раскрасок, можно проверять, что среди клеток, которым уже проставлены значения, нет плохих четверок. Это решение уже может пройти все тесты с c = 2 и значительное число тестов с c = 3. Чтобы еще больше оптимизировать решение, можно перебирать цвета для клеток в случайном порядке.

Дополнительная оптимизация, которая сильно ускоряет перебор, — добавление мемоизации. А именно, давайте запоминать некоторую информацию про текущую раскраску, которая точно не приведет к ответу (так как такая же комбинация перебиралась ранее, и ответ найден не был). Например, можно хранить множество троек (c, y₁, y₂), для которых среди уже покрашенных клеток найдется такое x, что a_x,y1 = a_x,y2 = c, и проверять, что такое множество не встречалось, когда мы начинаем красить первую клетку в определенной строке.

Прошлое решение работает заметно лучше при m < n, в противном случае можно поменять местами n и m и транспонировать поле для ответа. С этими оптимизациями можно пройти почти все тесты.

Локальные оптимизации

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

Исходно проставим каждой клетке случайный цвет 1… c. Затем будем выбирать случайную клетку и изменять ей цвет, если при этом уменьшится стоимость поля.

Стоимостью поля может быть почти любая функция, которая будет равна нулю для хороших полей. Например, за нее можно взять количество таких четверок x₁, x₂, y₁, y₂, что 1 ≤ x₁ < x₂ ≤ n, 1 ≤ y₁ < y₂ ≤ m, и клетки (x₁, y₁), (x₂, y₁), (x₁, y₂) и (x₂, y₂) покрашены в одинаковый цвет. Когда никакое изменение цвета не приведет к уменьшению ответа, можно завершить процесс.

Для большинства случайных раскрасок стоимость в конечном итоге будет равна маленькому числу. А если с исходной раскраской "повезёт", то стоимость будет равна нулю, и поле сойдется к хорошему полю. Отсюда выходит следующее решение: будем случайно генерировать исходные поля, запускать описанный выше процесс, пока стоимость уменьшается, и проверять что в конце получился 0. Если получился, то можно вывести ответ. Иначе генерируем исходное поле заново.

Это решение способно пройти все тесты с ограничениями этой задачи меньше чем за секунду.