Три класса глубины
Сейсмологи делят землетрясения по глубине очага на три класса: мелкофокусные (до 70 км), промежуточные (от 70 до 300 км) и глубокофокусные (глубже 300 км). На длинном стеллаже в ряд стоят n коробок с записями землетрясений, и на каждой написан класс: 1, 2 или 3. Коробки нужно переставить так, чтобы сначала шли все единицы, потом все двойки, потом все тройки. Робот за один ход меняет местами две любые коробки. Составьте для него план не длиннее n ходов.
Один из тестов — настоящий каталог USGS: 19 073 землетрясения силой от 5 за 2015–2025 годы в порядке времени.
Вход
В первой строке n (1 ≤ n ≤ 100 000), во второй — n чисел от 1 до 3: классы коробок слева направо.
Выход
В первой строке — число ходов k (0 ≤ k ≤ n). Дальше k строк по два числа i и j (1 ≤ i, j ≤ n): поменять местами коробки на местах i и j. Ходы выполняются по порядку. Если правильных планов несколько, выведите любой.
Примеры
Пример 1
12 1 1 2 1 1 1 1 1 3 1 1 1
9 3 4 4 5 5 6 6 7 7 8 9 12 8 9 9 10 10 11
Пример 2
3 2 3 1
2 2 3 1 2
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Это разбиение из быстрой сортировки, только частей не две, а три: меньше двойки, двойки и больше двойки. Можно ли разложить всё за один проход слева направо?
2Подсказка 2
Держите три границы. Левее lt — только единицы, от lt до i — двойки, правее gt — тройки, а между i и gt — коробки, на которые ещё не смотрели. Что делать с коробкой на месте i в каждом из трёх случаев?
3Подсказка 3
Если каждый ход окончательно ставит на место хотя бы одну коробку, ходов не может быть больше n.
4Идея
Это задача о трёхцветном флаге, которую Эдсгер Дейкстра разобрал в книге «A Discipline of Programming» (1976): разложить три цвета за один проход, не заводя второго массива. Смотрим на коробку на месте i. Единица — меняем её с коробкой на месте lt (там двойка или она сама) и сдвигаем обе границы вправо. Двойка — просто идём дальше. Тройка — меняем её с коробкой на месте gt и сдвигаем gt влево, а i оставляем: коробка, приехавшая справа, ещё не просмотрена.
Каждый обмен расширяет либо зону единиц, либо зону троек, а коробки, попавшие туда, больше не двигаются. Значит, обменов не больше n.
5Разбор
Обмен коробки самой с собой (когда lt = i или i = gt) в план не пишем: он ничего не меняет. План не обязан быть кратчайшим. В первом примере их девять, хотя хватило бы двух — переставить двойку и тройку в конец. Наименьшее число ходов — задача потруднее, она про циклы, как в задаче о коробках в архиве, только с повторяющимися значениями.
Годится и решение в два прохода в духе разбиения Ломуто: сначала собрать все единицы в начало, потом среди остальных — все двойки. Каждый обмен ставит на место одну единицу или одну двойку, и ходов не больше n.
5+Решение
6Сложность
Один проход: O(n) времени, O(1) памяти сверх массива, не больше n обменов. Именно такое разбиение на три части спасает быструю сортировку от одинаковых ключей: равные опорному остаются в середине и в рекурсию больше не идут.
7Типичные ошибки
- Сдвинуть i после обмена с правым концом. Коробка, приехавшая с места gt, остаётся непросмотренной, и единица или тройка застревает среди двоек. Первый пример — последние двенадцать землетрясений каталога — на этом ломается.
- Сортировать встроенной функцией. Порядок получится, а плана ходов — нет: его всё равно придётся строить.
- Пузырёк или вставки. Они меняют местами только соседей и делают столько ходов, сколько в ряду инверсий: в восьмом тесте, где пятьдесят тысяч троек стоят перед пятьюдесятью тысячами единиц, это два с половиной миллиарда ходов вместо ста тысяч.