Cards in a tray
A seismology laboratory keeps paper cards of earthquakes: a card per event, in a long narrow tray, in date order. For an exhibition the cards must be rearranged by magnitude, from weakest to strongest, while cards of equal magnitude may stay in any order. The tray is narrow: a card cannot be taken out, only two neighbouring ones can be swapped. How many such swaps are needed if not one is wasted?
Two tests are the real USGS catalogue: all earthquakes of magnitude 5 or more for 2025 and for 2015, in date order.
Input
The first line holds n (1 ≤ n ≤ 3000), the number of cards. The second holds n magnitudes in the order of the cards in the tray. Each magnitude is a number from 0 to 10 written with exactly two digits after the point.
Output
One number: the smallest number of swaps of neighbouring cards after which the magnitudes are non-decreasing.
Examples
Example 1
5 6.10 5.40 7.20 5.40 6.00
5
Example 2
4 6.00 5.00 6.00 5.00
3
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
Swap two neighbouring cards. How many pairs “a stronger card left of a weaker one” can disappear or appear because of it?
2Hint 2
If the tray has no pair “stronger left of weaker” left, it is already sorted. And while there are such pairs, is there a pair of neighbours among them?
3The idea
The answer is the number of inversions: pairs of cards where the left one is strictly stronger than the right. A swap of neighbours changes the relative order of exactly one pair, those two cards, so each swap removes at most one inversion, and at least as many swaps as inversions are needed. And that many is enough: while the tray is unsorted, somewhere there are neighbours “strong, weak”, and swapping them removes exactly one inversion. That is how bubble sort and insertion work: they make exactly as many swaps as there are inversions.
4Walkthrough
Cards of equal magnitude need not be swapped, so count only pairs with a strict inequality. The most direct way is a double loop over all pairs. With n ≤ 3000 that is four and a half million checks: milliseconds in Go, a fraction of a second in Python.
The reference solution counts faster, in the spirit of insertion. Take the cards from left to right, as insertion takes the next card. The new card, when inserted, passes all the stronger cards on its left: that is its contribution to the answer. If the magnitudes taken so far are kept in a sorted list, the number of stronger ones is i minus bisect_right(seen, m): all those taken minus those no stronger. The insertion insort shifts the tail of the list, but does it with a single memory copy, and on three thousand cards this goes unnoticed.
For a million cards even this is slow: counting inversions in O(n log n) is needed, alongside merge sort or with a Fenwick tree.
4+Solution
5Complexity
The double loop is O(n²) comparisons. The reference is O(n log n) comparisons and O(n²) memory shifts, which cost next to nothing. The answer is at most n(n − 1)/2 ≈ 4.5 million.
6Common mistakes
- Equal ones counted as an inversion. The condition “the left one is not weaker” instead of “the left one is stronger” adds pairs of equal magnitude, which need not be swapped. The second example: correctly 3, with this mistake 5.
- The number of bubble passes instead of the number of swaps. A pass may make many swaps or none, and the question is about swaps.
- Comparing fractions. It is safer to convert magnitudes to whole hundredths: 5.36 → 536.