The cost of a search
A sorted-set profiler took the shape of a skip list from a running server: for each element in key order, the height of its tower, how many levels it occupies. The coins have already been tossed, and the question now is not about the average but about a specific list: how many steps will the search for each element make, in total over all elements and in the worst case.
The list has a head with a tower of height H, the largest of the elements’ heights. A search for element x starts at the head on level H. On each level, while the next node on it exists and its key is less than x’s key, the search moves to that node: one step. When there is nowhere to move, the search goes down a level: also one step; from the first level, “down” is the step to x itself. A node is visible on level ℓ if its tower’s height is at least ℓ. The third test is the list from the article’s scene: the 735 pages of the Kennedy Space Center server after the whole day of 13 July 1995.
Input
The first line holds n (1 ≤ n ≤ 2·10⁵). The second holds n numbers h₁, …, hn (1 ≤ hi ≤ 32): the heights of the elements’ towers in increasing key order.
Output
Two numbers: the sum of search steps over all n elements and the largest number of steps of one search.
Examples
Example 1
12 1 2 1 3 1 2 1 4 1 2 1 3
68 7
Example 2
5 1 1 1 1 1
15 5
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
Walking every search honestly is correct, but a list where all towers have height 1 is an ordinary linked list, and the search for the last element walks all of it: 2·10¹⁰ steps for all of them. You need to count steps without stepping.
2Hint 2
There are always exactly H steps down, one per level. What remains is to count the steps right, that is, the nodes the search for x steps on. Which elements to the left of x lie on its path?
3Hint 3
Walk the path backwards, as in the proof in the article: from x to the left. The first is the left neighbour. Where does the path step after it?
4The idea
A node i to the left of x lies on the search path if and only if its tower is no lower than all the towers between it and x. So the backward path is a chain: the left neighbour of x, then the nearest element to its left with a tower no lower, then the nearest to the left of that one, and so on to the head. The length of such a chain for every element is computed by one pass with a monotonic stack: chain[i] = 1 + chain[the nearest to the left no lower than i]. The search for element j takes chain[j − 1] + H steps.
5Walkthrough
Why the path is exactly this. On level ℓ the search for x starts from the last element before x whose tower reaches level ℓ + 1 (or from the head) and goes right through all the elements before x whose towers reach ℓ. Element i is on the path if there is a level ℓ ≤ hi on which there are no towers taller than ℓ between i and x: then the search on level ℓ starts no further right than i and passes through it. The suitable ℓ is the largest of the heights between i and x (or 1 if there is nobody between them), and it is at most hi exactly when i’s tower is no lower than all the towers between them. That is the condition.
Equal towers. The condition is non-strict: if there is a tower of the same height between i and x, the search on that level passes through both. The chain “nearest to the left no lower” takes this into account; a strict “taller” would lose steps.
The stack. Go from left to right and keep on the stack elements whose towers strictly decrease from bottom to top. A new element i pops off the stack all elements lower than itself; the remaining top is the nearest to the left no lower than i, and its chain is one shorter than i’s. Each element enters the stack and leaves it once.
The sum of steps can exceed 2³¹ (in the sixth test, where all towers have height 1, it is 20,000,100,000), so Go needs int64. On the real list from the scene the sum is 12,973 steps for 735 searches, 17.65 steps on average; the longest search takes 42 steps.
5+Solution
6Complexity
O(n) time and memory: one stack pass and one pass over the answers, however many steps the searches themselves take.
7Common mistakes
- Honest simulation. Correct, but on a list without express lines each search is a pass from the start: the sixth test.
- A strict “taller”. It loses nodes with towers of the same height: in the second example, where all towers are of height one, you get 9 steps instead of 15.
- Forgotten descents. Besides the steps right, a search makes H steps down, and H is the height of the head, that is, of the tallest tower, not of the element itself.
- A 32-bit sum. In the sixth test the sum exceeds 2·10¹⁰.
Algorithms behind it
O(log n) on average for search, insertion, deletion and rank
1 problem
DS
Technique
Monotonic stack
A stack with ordered values: the nearest greater element and the largest rectangle in O(n).
O(n)
2 problems