Which runs to merge
Timsort puts runs on the stack one after another and merges neighbouring runs of the stack. Merging runs of lengths x and y costs x + y: that many elements are moved. You are given the lengths of the runs in the order in which they go on the stack. Compute the total cost of all merges under two rules: Timsort’s fixed 2015 rule and powersort.
The 2015 rule. After pushing a run, repeat while there is more than one run on the stack. Let the lengths of the top runs be …, D, C, B, A (A on top). If C ≤ B + A or D ≤ C + B (each condition only if the corresponding runs exist), merge B with the smaller of its neighbours: with C if C < A, otherwise with A. Otherwise, if B ≤ A, merge B and A. Otherwise stop.
Powersort. Let n be the sum of all lengths. When a new run of length n2 arrives, and the top run of the stack starts at position s1 (the sum of the lengths of all runs below it) and has length n1, compute the power of the boundary between them: a = 2s1 + n1, b = a + n1 + n2, p = 0, and repeat: p increases by 1; if a ≥ n, n is subtracted from a and b; otherwise, if b ≥ n, the computation is finished; then a and b are doubled. While the run lying under the top one has a right-boundary power greater than p, merge the two top runs. Then record the power p for the top run and push the new run.
At the end both rules merge everything that is left: while there is more than one run, take the second from the top and merge it with the smaller of its neighbours: with the one below it if that is shorter than the top one, otherwise with the top one.
Input
The first line holds the number of runs k (1 ≤ k ≤ 105), the second their lengths, from 1 to 107.
Output
Two numbers: the cost of all merges under the 2015 rule and under powersort.
The first example is the runs from the article: the 2002 rule would leave the stack invalid, but the final cost is the same. The second is the runs Timsort puts on the stack when sorting the commit times of this site.
Examples
Example 1
5 120 80 25 20 30
550 550
Example 2
15 40 70 65 40 364 88 40 40 255 57 60 40 41 40 18
5396 4534
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 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
Only a stack of lengths is needed: the data itself is not needed for the merge cost. Where in the stack should the power of a boundary be kept?
2The idea
Both rules are a simple simulation of a stack of lengths. In the 2015 rule the main thing is not to forget the second condition, on the fourth run from the top: without it the stack can violate the rule “each run is longer than the next two together” deep down, as in the first example, and then the stack stops growing logarithmically. Powersort, instead of rules about lengths, looks at the position of runs in the array: the power of a boundary is the depth of the node that separates the midpoints of two neighbouring runs in a perfect binary tree over the whole array. Merge while the boundary in the stack is deeper than the new one; that way the merges follow an almost balanced tree.
3Walkthrough
For the 2015 rule keep a list of lengths and after each new run repeat the check from the statement, merging and adding up the cost. For powersort store with each run the power of its right boundary; the start of the top run is the sum of the lengths of all runs below it, that is, the number of elements already pushed minus the length of the top run. Compute the power of the new boundary once, before the merges, then merge while the power under the top run is greater than the new one, and record the new power for the top run. At the end, the same finishing pass for both rules.
The sum of lengths reaches 1012, and the cost up to several dozen such sums: in Go a 64-bit int64 is needed. The values a and b in the power loop stay below 4n and fit too.
3+Solution
4Complexity
Each run is pushed once and merged at most once as the top run, so there are fewer than k merges and O(k) checks. The power loop takes at most log₂ n + 2 steps. In total O(k log n).
5Common mistakes
- The 2002 rule. Without checking the fourth run from the top, the cost differs on some inputs: the stack is merged later and more unevenly.
- Computing the power after the merges. The power of the new boundary depends on the top run as it was before the merges; that is how CPython computes it too.
- Merging at equal power. The condition is strict: at equal power the boundary stays on the stack.