CS
Задачник Базовый курс EN

Задача

Каналы без помех

перебор с возвратом раскраска граф эвристика геоданные

В городах вокруг Алматы ставят передатчики, по одному в каждом. Два передатчика, которые стоят ближе D километров друг к другу, на одном канале мешают друг другу; на разных каналах или дальше — нет. Каждый канал стоит денег, поэтому каналов нужно как можно меньше. Сколько их хватит и как их раздать?

Тесты 3–5 — настоящие города от 10 тысяч жителей в радиусе 300 км от Алматы по справочнику GeoNames, положенные на плоскую карту с точностью до километра, при разных D. Остальные расстановки придуманы.

Вход

В первой строке число передатчиков n и расстояние D (1 ≤ n ≤ 40, 1 ≤ D ≤ 10⁴). Дальше n строк с координатами передатчиков x y в километрах, целые, |x|, |y| ≤ 10⁴. Передатчики мешают друг другу на одном канале, если расстояние между ними строго меньше D. Координаты разных передатчиков могут совпадать.

Выход

В первой строке — наименьшее число каналов k. Во второй — n чисел от 1 до k: канал каждого передатчика в порядке ввода. Если способов несколько, выведите любой.

Примеры

Пример 1

Вход
4 50
0 0
40 0
80 0
120 0
Выход
2
2 1 2 1

Пример 2

Вход
5 150
100 0
31 95
-81 59
-81 -59
31 -95
Выход
3
1 2 1 2 3

Ограничения

Время · Python
6000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
13 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Передатчики — вершины графа, пары, которые мешают друг другу, — рёбра. Раздать каналы — значит раскрасить вершины так, чтобы концы каждого ребра были разного цвета. Первое, что приходит в голову: идти по передатчикам и давать каждому наименьший канал, не занятый соседями. Это всегда даёт правильную раздачу, но наименьшую ли? Проверьте на восьмом тесте.

2Подсказка 2

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

3Подсказка 3

Раз формулы нет, остаётся искать. Перебором с возвратом проверьте, можно ли обойтись k каналами, для k от нижней оценки вверх. Чтобы перебор успевал, нужны три вещи: какой передатчик красить следующим, как не перебирать раздачи, которые отличаются только номерами каналов, и откуда начинать k.

4Идея

Для k = нижняя оценка, нижняя оценка + 1, … ищем раскраску в k цветов перебором с возвратом. Следующим красим передатчик, у которого меньше всего свободных каналов (при равенстве — у которого больше соседей). Новый, ещё не использованный канал даём только с наименьшим номером из неиспользованных: каналы взаимозаменяемы, и раздачи, которые отличаются только перестановкой номеров, перебирать незачем. Первое k, для которого раскраска нашлась, и есть ответ: для меньших перебор доказал, что раскраски нет.

5Разбор

Граф. Ребро между i и j, если (xi − xj)² + (yi − yj)² < D² — в целых числах, без корней.

Нижняя оценка. Клика — группа попарно соседних вершин. Найти самую большую клику — тоже трудная задача, но для оценки хватит жадной: из каждой вершины растим клику, добавляя соседа, у которого больше всего общих соседей с уже набранными. Чем лучше оценка, тем меньше бесполезных k придётся опровергать. В тестах с настоящими городами жадная клика сразу даёт ответ: там города сбиваются в тесные кучки вокруг больших городов, и ответ определяется самой плотной кучкой.

Перебор. Для каждой вершины храним, сколько её соседей уже окрашено в каждый цвет; свободные цвета — те, где счётчик ноль. На шаге выбираем непокрашенную вершину с наименьшим числом свободных цветов: если у какой-то их ноль, ветка мертва, и мы возвращаемся немедленно. Пробуем цвета по возрастанию, но не выше «наибольший использованный + 1». При возврате уменьшаем счётчики соседей.

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

5+Решение
6Сложность

Раскраска графа — NP-трудная задача, и в худшем случае перебор экспоненциален. Здесь n ≤ 40, а графы геометрические: соседи передатчика сами близко друг к другу и тоже соседи. На таких графах выбор самой стеснённой вершины почти сразу вынуждает каналы, и эталон на Python решает каждый тест за доли секунды. А перебор по порядку ввода, без выбора стеснённой вершины и без запрета лишних номеров, на тринадцатом тесте не находит раздачу на 21 канал и за минуту, хотя нижняя оценка там как раз 21.

7Типичные ошибки
  • Жадная раздача. Правильная, но не наименьшая: на восьмом тесте она выдаёт 13 каналов вместо 11, на тринадцатом — 25 вместо 21.
  • Ответ — размер наибольшей клики. Кольца из пяти и семи передатчиков (второй, шестой и седьмой тесты) требуют на канал больше.
  • Все номера каналов для новой вершины. Если разрешать вершине любой из k ещё не занятых номеров, каждая раздача повторится до k! раз, и доказать, что k каналов мало, не удастся за разумное время.
  • Расстояние в числах с плавающей точкой. Граница «строго меньше D» на целых координатах проверяется точно в квадратах; корень может превратить равенство в неравенство.

Алгоритмы задачи

PAR Приём Перебор с возвратом Строить решение по шагу, сразу проверять и отступать из тупика: судоку, ферзи, раскраски. O(bᵈ) в худшем случае 2 задачи GRA Алгоритм Раскраска графа Соседям — разные цвета: жадный способ, порядок «наименьший последним», DSatur и точный перебор на картах и расписаниях. O(V + E) — жадно в данном порядке и «наименьший последним»; O((V + E) log V) — DSatur с кучей 2 задачи
Каталог алгоритмов