A place in the catalogue
A seismological service accompanies each new earthquake with a line “this is the k-th strongest earthquake since records began”. The catalogue grows event by event, and for each new event you need to know how many previous ones were strictly stronger: the place of the new event is that number plus one. Earthquakes of equal strength do not outrank each other.
One of the tests is all the earthquakes of magnitude 5 and above from 2015 to 2025 from the USGS catalogue in time order, 19,073 events; the magnitude is multiplied by 100.
Input
The first line holds n (1 ≤ n ≤ 100,000). The second holds n integers a1, …, an (|ai| ≤ 10⁹), the strengths of the events in time order.
Output
n lines: the i-th holds the number 1 + |{j < i : aj > ai}|.
Examples
Example 1
7 510 536 550 540 540 610 500
1 1 1 2 2 1 7
Example 2
6 7 7 3 9 7 3
1 1 3 1 2 5
Limits
- Time · Python
- 6000 ms
- Time · Go
- 2000 ms
- Memory
- 256 MB
- Judging
- 9 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
Going over all the previous events for each new one is n²/2 comparisons, five billion with a hundred thousand events. What do you need to remember about the previous events to answer faster?
2Hint 2
Counts are enough: how many previous events had each strength. Then the answer is the sum of the counts of all strengths greater than the given one. A range sum with single updates is a job for a Fenwick tree. But strengths go up to a billion.
3The idea
First compress the values: sort the distinct strengths in descending order and number them from one. Now “stronger” means “with a smaller number”, and the number of previous stronger events is the sum of the counts with numbers from 1 to number − 1, that is, a prefix sum. Go through the events: ask for the prefix sum, print it plus one, add one to the count of your own number.
4Walkthrough
Compression is a “value → number” dictionary after sorting in Python and a binary search over the sorted slice in Go. The Fenwick tree holds k + 1 numbers, where k is the number of distinct strengths; a prefix sum removes the lowest one bit of the number, an addition adds it.
Equal strengths take care of themselves: an event of the same strength gets the same number and is not included in the prefix sum up to number − 1. If you had to count “not weaker”, the prefix would be taken up to your own number inclusive.
You can also do without the tree: keep the previous strengths in a sorted list and insert each new one by binary search (bisect.insort). The answer is how many elements of the list are to the right of the insertion point. An insertion shifts the tail of the list, O(n), but this is one fast memory shift in C, and with a hundred thousand events such a solution fits within the limits; on millions of events the shifts would lose to the tree many times over.
4+Solution
5Complexity
Sorting is O(n log n), each event is two tree operations of O(log k). O(n log n) time and O(n) memory in all.
6Common mistakes
- Going over the previous events. Correct, but O(n²): the fifth and sixth tests have 30,000 events in a row in descending and ascending order, the fourth a hundred thousand.
- A tree over the values themselves. An array of two billion counts will not fit in memory; the values have to be compressed.
- A non-strict comparison. An event of the same strength is not stronger: in the second example the third seven is in second place, not fourth.
- Compressing in ascending order without reversing. Then the prefix sum counts the weaker events; either number in descending order or take a difference: all the previous ones minus those not stronger.