Three depth classes
Seismologists divide earthquakes by focal depth into three classes: shallow (down to 70 km), intermediate (from 70 to 300 km) and deep (deeper than 300 km). On a long shelf stand n boxes of earthquake records in a row, and each is labelled with its class: 1, 2 or 3. The boxes must be rearranged so that all the ones come first, then all the twos, then all the threes. In one move a robot swaps any two boxes. Write a plan for it of at most n moves.
One of the tests is the real USGS catalogue: 19,073 earthquakes of magnitude 5 or more for 2015–2025 in time order.
Input
The first line holds n (1 ≤ n ≤ 100,000), the second n numbers from 1 to 3: the classes of the boxes from left to right.
Output
The first line holds the number of moves k (0 ≤ k ≤ n). Then k lines of two numbers i and j (1 ≤ i, j ≤ n): swap the boxes at places i and j. The moves are carried out in order. If there are several correct plans, print any.
Examples
Example 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
Example 2
3 2 3 1
2 2 3 1 2
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
This is the partition from quicksort, only with three parts instead of two: less than two, twos, and greater than two. Can everything be laid out in one pass from left to right?
2Hint 2
Keep three boundaries. Left of lt there are only ones, from lt to i twos, right of gt threes, and between i and gt the boxes not yet looked at. What should be done with the box at place i in each of the three cases?
3Hint 3
If every move puts at least one box in its final place, there cannot be more than n moves.
4The idea
This is the Dutch national flag problem that Edsger Dijkstra worked through in the book “A Discipline of Programming” (1976): lay out three colours in one pass without a second array. Look at the box at place i. A one: swap it with the box at place lt (a two there, or the box itself) and move both boundaries right. A two: just go on. A three: swap it with the box at place gt and move gt left, but leave i where it is: the box that arrived from the right has not been looked at yet.
Every swap widens either the zone of ones or the zone of threes, and boxes that land there never move again. So there are at most n swaps.
5Walkthrough
A swap of a box with itself (when lt = i or i = gt) is not written into the plan: it changes nothing. The plan need not be the shortest. In the first example it has nine moves, although two would have done: move a two and a three to the end. The smallest number of moves is a harder problem, about cycles, as in the problem on boxes in an archive, only with repeated values.
A two-pass solution in the spirit of Lomuto’s partition also works: first gather all the ones at the front, then all the twos among the rest. Each swap puts one one or one two in place, so there are at most n moves.
5+Solution
6Complexity
One pass: O(n) time, O(1) memory beyond the array, at most n swaps. It is exactly this three-way partition that saves quicksort from equal keys: elements equal to the pivot stay in the middle and never go into the recursion again.
7Common mistakes
- Advancing i after a swap with the right end. The box that arrived from place gt stays unexamined, and a one or a three gets stuck among the twos. The first example, the last twelve earthquakes of the catalogue, breaks on this.
- Sorting with a built-in function. You get the order but not the plan of moves: that still has to be built.
- Bubble sort or insertion. They swap only neighbours and make as many moves as there are inversions in the row: in the eighth test, where fifty thousand threes stand before fifty thousand ones, that is two and a half billion moves instead of a hundred thousand.