Две руки
Пианист решает, какой рукой играть каждую ноту. Нота звучит от момента s до момента e, две ноты звучат вместе, если их отрезки [s, e) пересекаются. Для каждой пары нот разной высоты, звучащих вместе, действуют два правила:
- руки не перекрещиваются: нижняя нота не может быть у правой руки, когда верхняя у левой;
- рука берёт разом не шире растяжки S: если ноты дальше друг от друга, чем на S полутонов, их играют разные руки.
Две ноты одной высоты, звучащие вместе, — это одна клавиша (так бывает, когда два голоса сходятся в унисон), и правил для них нет. Сколько нот у одной руки, не важно. Раздайте ноты рукам или скажите, что двух рук не хватает.
Тесты с третьего по десятый — настоящие пьесы из MIDI-файлов проекта Mutopia: прелюдии Баха и Шопена, два рэга Джоплина и органная токката Баха, каждая при растяжке, которой хватает, и при меньшей.
Вход
В первой строке n и S (1 ≤ n ≤ 2 · 10⁴, 1 ≤ S ≤ 60). Дальше n строк по три целых: начало s, конец e и высота p ноты (0 ≤ s < e ≤ 10⁶, 0 ≤ p ≤ 127). Высота — номер клавиши, как в MIDI: соседние числа — полутон, 60 — до первой октавы. Пар нот, звучащих вместе, не больше 2 · 10⁵.
Выход
Если двух рук хватает — YES, а во второй строке n букв: i-я — L, если i-ю ноту играет левая рука, и R, если правая. Если раздач несколько, выведите любую. Если двух рук не хватает — одно слово NO.
Примеры
Пример 1
4 12 0 4 48 0 4 64 2 6 72 4 8 52
YES LRRL
Пример 2
3 12 0 4 36 0 4 60 0 4 84
NO
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 15 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
У каждой ноты два варианта — левая или правая. Запишите оба правила для пары нот a ниже b как условия вида «это или то» про две ноты сразу. Сколько таких условий даёт одна пара?
2Подсказка 2
«Руки не перекрещиваются» — это «a левой или b правой». «Шире растяжки» — это два условия: «a правой или b правой» (не обе левой) и «a левой или b левой» (не обе правой). Все условия — из двух литералов. Какой алгоритм решает такие формулы за линейное время?
3Идея
2-SAT. Переменная — нота, «истина» — правая рука. Каждое условие «x или y» даёт две стрелки ¬x → y и ¬y → x в графе следствий на 2n литералах. Двух рук не хватает ровно тогда, когда какая-то нота и её отрицание оказались в одной компоненте сильной связности; иначе нота у правой руки, если её компонента «правой» позже компоненты «левой» в топологическом порядке. Доказательство — в статье.
4Разбор
Сортируем ноты по началу. Для каждой ноты идём по следующим, пока они начинаются раньше её конца: это и есть все ноты, звучащие с ней вместе, и перебор стоит столько, сколько пар (не больше 2 · 10⁵). Ноты одной высоты пропускаем. Для пары нижней a и верхней b кладём условие о перекрещивании, а если b − a > S, ещё два. Литерал 2i — нота i правой, 2i + 1 — левой, отрицание — x ^ 1. Компоненты — Тарьян со своим стеком: номера компонент у него идут в обратном топологическом порядке, поэтому нота у правой руки, если номер компоненты 2i меньше номера компоненты 2i + 1.
4+Решение
5Сложность
O(n log n + m), где m — число пар, звучащих вместе: сортировка, по одной-три пары стрелок на пару нот и один обход графа из 2n вершин и не больше 6m стрелок.
6Типичные ошибки
- Решать момент за моментом. Это
wrong.py: каждая нота получает руку в момент, когда начинается, — звучащие сейчас ноты делятся по самому широкому промежутку по высоте. Но выбор для долгой ноты потом не пересматривается. Прелюдия Баха начинается с до первой октавы, которое звучит в одиночку и достаётся правой руке, а через долю над ним вступает ми второй октавы: 16 полутонов у одной руки при растяжке в октаву. И такой способ никогда не говоритNO, а во втором тесте три ноты через две октавы двумя руками не взять никак. - Одна стрелка на условие. Без второй стрелки ¬y → x граф теряет симметрию, и раздача из порядка компонент может нарушить правило.
- Перепутанный порядок компонент. У Тарьяна номера идут в обратном топологическом порядке, у Косараю — в прямом. Правило выбора литерала зависит от того, какой обход взят.
- Унисон. Две ноты одной высоты, звучащие вместе, нельзя считать парой «нижняя — верхняя»: условие о перекрещивании запретит одну из раздач, а по условию задачи для унисона правил нет. В пятнадцатом тесте два таких места, устроенных зеркально: какую бы из двух нот ни считать нижней, одно из них станет противоречием, и ответ выйдет
NOвместоYES. - Рекурсия. В четырнадцатом тесте низкие и высокие ноты чередуются и каждая звучит вместе со следующей: следствия выстраиваются в цепочку из 20 000 литералов. Рекурсивный обход в Python упрётся в предел глубины.