Подписи сёл на карте
Картограф подписывает сёла на карте. Подпись села — прямоугольник: высотой 2h, по вертикали посередине точки села, а по горизонтали — вплотную справа от точки или вплотную слева, других мест нет. Ширина подписи w у каждого села своя — она зависит от длины названия. Подписи не должны перекрываться друг с другом и не должны закрывать точки других сёл; касаться краями можно, и сама точка села может лежать на краю чужой подписи.
Подпись села в точке (x, y) справа занимает прямоугольник [x, x + w] × [y − h, y + h], слева — [x − w, x] × [y − h, y + h]. Две подписи перекрываются, если у прямоугольников есть общая внутренняя точка. Подпись закрывает село, если его точка лежит строго внутри прямоугольника.
Расставьте подписи или скажите, что это невозможно.
Вход
В первой строке n и h (1 ≤ n ≤ 2000, 1 ≤ h ≤ 105). Дальше n строк x y w — координаты села в метрах и ширина его подписи (|x|, |y| ≤ 3 · 106, 1 ≤ w ≤ 105). Никакие два села не стоят в одной точке.
Выход
NO, если расставить подписи нельзя. Иначе YES и во второй строке n букв: R, если подпись села стоит справа, L — если слева, в порядке сёл на входе. Подходит любая правильная расстановка.
Тесты с 4-го по 8-й — 675 городов и сёл Южноморавского края из справочника GeoNames при пяти размерах шрифта: буква шириной 60, 80, 96, 98 и 150 метров, и h равно ширине буквы.
Примеры
Пример 1
3 2 0 0 6 8 0 6 20 0 6
YES RRR
Пример 2
3 2 0 0 10 4 0 10 8 0 10
NO
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 2000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
У каждого села ровно два варианта. Запишите его как логическую переменную: «подпись справа» или нет. Как выглядит условие «подписи сёл i и j в этих положениях перекрываются»?
2Подсказка 2
«Не (A и B)» — это «не A или не B», дизъюнкция двух переменных. А дизъюнкцию двух переменных можно прочитать как два следствия: если A, то не B, и если B, то не A. Нарисуйте все эти следствия стрелками.
3Подсказка 3
Если по стрелкам можно дойти от «справа» до «слева» для одного села и обратно, что это значит?
4Идея
Это задача 2-SAT: набор условий вида «a или b», где a и b — переменные или их отрицания. Для села i заведём два утверждения: Ri — «подпись справа» и ¬Ri — «слева». Каждая пара положений, в которой подписи двух сёл перекрываются, запрещает их сочетание: ¬(p ∧ q), то есть стрелки p → ¬q и q → ¬p. Положение, в котором подпись закрывает чужое село, запрещено само: стрелка p → ¬p.
Получился граф следствий на 2n вершинах. Найдём в нём компоненты сильной связности. Если Ri и ¬Ri оказались в одной компоненте, то из «справа» следует «слева», а из «слева» — «справа», и ни одно положение невозможно: ответ NO. Иначе расстановка есть, и её даёт порядок компонент: для каждого села выбираем то утверждение, чья компонента стоит дальше по стрелкам конденсации. Тарьян закрывает компоненты начиная со стоков, поэтому это утверждение с меньшим номером компоненты.
5Разбор
Почему выбор «то, что дальше по стрелкам» не противоречит ни одному условию. Пусть выбрано p, и есть стрелка p → q. Граф следствий симметричен: вместе с ней есть стрелка ¬q → ¬p. Если бы выбрали ¬q, то компонента ¬q стояла бы дальше q; но ¬q → ¬p, поэтому ¬p стоит не раньше ¬q, а p → q ставит q не раньше p. Получается цепочка «p не дальше q, q раньше ¬q, ¬q не дальше ¬p», то есть ¬p дальше p — а выбрали p. Противоречие.
Пары, которые могут мешать друг другу, ищем, отсортировав сёла по y: подписи пересекаются по вертикали только у сёл, чьи y отличаются меньше чем на 2h. Так же быстро находятся точки сёл, которые закрывает подпись.
Самые наглядные тесты — шестой и седьмой. При букве в 96 метров подписи Южной Моравии расставить можно. При 98 — уже нет, и виновата тройка сёл: подписи Горни-Лоучки (Horní Loučky) и Уезда-у-Тишнова (Újezd u Tišnova) помещаются рядом только одним способом — первая справа, вторая слева, — а подпись Уезда слева закрывает село Ржиконин (Řikonín).
5+Решение
6Сложность
Граф следствий — 2n вершин и по две стрелки на каждую запрещённую пару; Тарьян — линейный по их числу. Поиск пар после сортировки зависит от плотности сёл: в худшем случае O(n²), если все сёла в одной полосе высотой 2h, на настоящих картах — почти линейно.
7Типичные ошибки
- Жадность с запада на восток. Ставить подпись справа, если помещается, иначе слева. На карте Моравии при букве в 80 метров так не получается, хотя расстановка есть: жадный выбор на западе отнимает место у сёл восточнее. В одиннадцатом тесте ловушка из трёх сёл повторена 400 раз.
- Забыть про точки сёл. Подпись, которая закрывает соседнее село, запрещена даже тогда, когда ни с одной подписью не пересекается.
- Строгость сравнений. Касание краями разрешено: сравнения с концами отрезков строгие.
- Не тот порядок. Брать утверждение из компоненты, которая стоит раньше по стрелкам, — значит выбирать то, из чего что-то следует, и нарушать условия.