Boxes in the archive
In an archive, n boxes of seismograph records stand on a long shelf, a box per earthquake. Each box bears the event’s number in the catalogue, all numbers distinct. For an exhibition the boxes were arranged by the earthquakes’ magnitude, and now they must be returned to number order, increasing from left to right. The boxes are heavy, and a forklift robot moves them: in one move it takes any two boxes and swaps them. In what smallest number of moves can it manage?
One of the tests is the real USGS catalogue: 19,073 earthquakes of magnitude 5 or more for 2015–2025, arranged by magnitude.
Input
The first line holds n (1 ≤ n ≤ 200,000). The second holds n distinct box numbers in the order they stand on the shelf; the numbers are integers from 1 to 10⁹.
Output
One number: the smallest number of moves after which the numbers are increasing.
Examples
Example 1
5 50 20 30 40 10
1
Example 2
4 2 1 4 3
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
Draw an arrow from each box to the place where it should stand. One arrow leaves each place and one enters it. What do such arrows form?
2Hint 2
The arrows form cycles: the box from place 1 must go to place 4, the box from place 4 to place 2, the box from place 2 back to place 1. How many moves does a cycle of k boxes need? And can one swap help two cycles at once?
3The idea
Let the arrows form c cycles (a box already in its place is a cycle of length 1). A sorted shelf has exactly n cycles. Swapping two boxes of one cycle cuts it in two, swapping boxes from different cycles glues them into one, that is, each move changes the number of cycles by exactly one. So at least n − c moves are needed. And that many is enough: put any box that is out of place where it belongs; one box is cut off from its cycle, and there is one more cycle.
This is exactly how selection sort works: each of its swaps puts the smallest of the remaining elements into place. So on distinct elements it makes the smallest possible number of swaps, n − c. The trouble is elsewhere: to find what to swap with what, it spends n²/2 comparisons.
4Walkthrough
The swaps themselves need not be made, only their number. Sort the numbers and find each box’s target place. Then walk the arrows: from each place not yet visited, follow the arrows until you return, marking what you pass. Each such walk is one cycle. The answer is n − c.
Compare with the problem on the card tray: there only neighbours can be swapped, and the answer is the number of inversions. In the first example here there is one move (10 and 50 swap places), while swapping neighbours would take seven.
4+Solution
5Complexity
Sorting is O(n log n), walking the cycles O(n): each place is visited once. Simulating selection is O(n²): for 200,000 boxes that is twenty billion comparisons.
6Common mistakes
- Simulating selection sort. The answer is right, but the time is quadratic: the large tests will not fit.
- Counting boxes out of place. In the second example there are four such, but two moves are needed: each move puts two boxes into place at once if they stand in each other’s places.
- Counting inversions. That is the answer for swaps of neighbours; here the robot can swap any two boxes.