The snowplow's runs
A file is too large for memory, and it is sorted by external sorting. The first phase cuts the file into sorted runs by replacement selection; memory holds M keys. How many runs will there be, and how long is the longest?
Replacement selection works like this. First the first M keys of the file (or all of them, if there are fewer) are read into memory, and all of them belong to the first run. Then, while memory is not empty:
- if memory holds keys of the current run, the smallest of them is written to the run; if there are none, a new run begins, all the keys in memory now belong to it, and the smallest of them is written;
- in place of the written key x the next key of the file y is read, if the file has not ended. If y ≥ x, it still makes it into the current run; if y < x, it waits for the next one.
Each run comes out sorted, because keys go into it in non-decreasing order. Four tests are real data: the magnitudes and depths of earthquakes of magnitude 5 and above for 2015–2025 in time order (the USGS ComCat catalogue), and the populations and latitudes of the world’s cities of 10,000 people and more in the order of the GeoNames file.
In the first example the first run gets 1, 3, 5, 8, 9, while 2, 7 and 4 arrive after smaller keys have already been written and go to the second: 2, 4, 7. With chunks of three keys there would be three runs. In the second example a key equal to the one just written stays in the current run.
Input
The first line holds n and M (1 ≤ M ≤ n ≤ 200,000). The second holds n integer keys in file order, at most 109 in absolute value.
Output
Two numbers: how many runs there will be and how many keys the longest of them holds.
Examples
Example 1
8 3 5 1 9 3 8 2 7 4
2 5
Example 2
6 2 3 3 1 3 3 2
2 4
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 15 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
Memory holds two sorts of keys: those that still make it into the current run and those waiting for the next one. You need a structure that quickly gives the smallest key of the current run.
2Hint 2
If the keys of the next run are given a run number one higher, a single heap is enough: pairs (run number, key) are compared by the number first.
3The idea
A heap of pairs (run, key). The smallest pair is the smallest key of the current run, and when the keys of the current run are used up, the smallest key of the next one, and the run number in the pair itself says that a new run has begun. Having written the key x, put the next key y into the heap with the same run number if y ≥ x, and with a number one higher if y < x. The number only ever grows by one: a key from the next run never overtakes a key of the current one.
4Walkthrough
Fill the heap with the first M keys with number 0. While the heap is not empty, take out the smallest pair; if its number is greater than the number of the current run, close the run and remember its length. The length of the written piece grows by one, and the next key from the file takes the place of the key. At the end, close the last run.
What the tests show. On random keys the runs are on average twice as long as memory: 200,000 keys with M = 1000 give 101 runs instead of 200. On a sorted file there is one run, on a file in descending order exactly M each. With M = 1 the runs are simply the non-decreasing stretches of the file itself.
4+Solution
5Complexity
O(n log M) time and O(M) memory, not counting the input itself.
6Common mistakes
- A strict comparison. A key equal to the one just written still makes it into the run: the run is non-decreasing. If it is sent to the next one, a file of equal keys gives n/M runs instead of one, and the earthquake magnitudes, with many equal values, give 12 runs instead of 9. This is
wrong.py. - Comparing with the smallest in memory. What decides is the comparison with the key just written, not with the keys still lying in memory.
- Two heaps without switching. The current run and the next can be kept in separate heaps, but then the heaps must be swapped when the run changes, and that is easy to forget.
Algorithms behind it
O(n log n) comparisons; 2n·(1 + ⌈log_k R⌉) line reads and writes
1 problem
DS
Data structure
Binary heap
The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on.
O(log n)
2 problems