A chronicle from regional catalogs
Earthquakes are recorded by k regional networks, each with its own catalogue ordered by time. For a common chronicle the catalogues have to be merged into one, also by time. If events of different networks have the same time, the event of the network with the smaller number comes first; events of one network keep the order of their catalogue. Print which network each event of the chronicle comes from.
One of the tests is the real USGS catalogue: 19,073 earthquakes of magnitude 5 and up in 2015–2025, divided into 36 networks by longitude (bands of 10°), with time in seconds from the start of 2015.
Input
The first line holds k (1 ≤ k ≤ 100,000). Then k lines: the i-th starts with the number of events mi ≥ 1, followed by mi moments of time, integers from 0 to 10⁹ in non-decreasing order. There are at most 100,000 events in all.
Output
For each event of the chronicle in order, the number of its network (from 1 to k), one per line.
Examples
Example 1
3 3 10 40 70 2 20 30 2 5 80
3 1 2 2 1 1 3
Example 2
3 2 100 100 1 100 2 50 100
3 1 1 2 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
Two catalogues are merged by ordinary merging with two pointers. What if they are merged in turn: the first with the second, the result with the third, then with the fourth? How many times will the very first event be rewritten?
2Hint 2
At every step the same thing is needed: the smallest of the k first unread events, and then to replace it with the next event of the same network. Which structure quickly gives the minimum and quickly takes a new element?
3The idea
Keep in a heap the first unread event of each network, keyed by the pair (time, network number), so that with equal times the network with the smaller number comes out first. Take out the minimum, print its network number and put the next event of that network into the heap, if there is one. The heap is never larger than k, and each operation costs O(log k).
There is also a solution without a heap, a tournament of merges as in merge sort: merge the catalogues in pairs, then pairs of pairs and so on. There are ⌈log₂ k⌉ levels, each rewriting at most N events, O(N log k) in all too. Merging in turn is bad: the first catalogue is rewritten in each of the k − 1 merges, and with k = 100,000 networks of one event each that is five billion operations.
4Walkthrough
In Python the triple (time, network number, place in the catalogue) is compared as a tuple: first by time, on a tie by network number. That is exactly what is needed. Instead of “take out and put in” it is convenient to call heapreplace: it replaces the top of the heap and restores the order in one sift. In Go heap.Fix(&h, 0) after replacing h[0] does the same.
A very short solution also works: write out all events as pairs (time, network number) and sort them. This is O(N log N), a little more than O(N log k), but within the limits. The heap is good for something else: it does not need to hold all the catalogues in memory; it is enough to read each one event at a time. That is how files that do not fit in memory are merged in external sorting.
4+Solution
5Complexity
The heap: O(N log k) time and O(k) memory on top of the input. Merging in turn: O(N·k) in the worst case.
6Common mistakes
- Merging in turn. Each separate merge is correct, but together they are quadratic in the number of networks: the fifth test is a hundred thousand networks of one event each.
- The wrong order on equal times. If (time, place in the catalogue, network number) is put into the heap, then on equal times the event earlier in its own catalogue wins, not the network with the smaller number. In the second example four events of three networks happened at moment 100.
- Slow output. A hundred thousand lines are better collected and printed at once than with a
printcall for each.