The height without the tree
Keys are inserted one by one into an ordinary binary search tree, without any balancing. Each new key goes down from the root: left if it is smaller than the node's key, right if larger, and it becomes a leaf where the needed branch is missing. The whole list of keys is known before the insertions. Find how high the tree will grow and how many comparisons the insertions make in total: each key is compared with all nodes on the path from the root to its place.
The height is the number of nodes on the longest path from the root to a leaf: a one-node tree has height 1. The third and fourth tests are all 19,073 earthquakes of magnitude 5 and above for 2015–2025 from the USGS catalogue, in the order they happened; the key is the shock's rank by focal depth (in the third test) or by magnitude (in the fourth), equal values ordered by time.
Input
The first line holds n (1 ≤ n ≤ 2·10⁵). The second holds a permutation of the numbers from 1 to n: the keys in insertion order.
Output
Two numbers: the height of the tree and the total number of comparisons over all insertions.
Examples
Example 1
5 3 1 4 5 2
3 6
Example 2
5 1 2 3 4 5
5 10
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 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
Building the tree and inserting honestly is correct, but an insertion costs as many comparisons as the depth of the new node. Increasing keys give a stick of 2·10⁵ nodes and 2·10¹⁰ comparisons. In that case the answer can be computed without a tree. And in general?
2Hint 2
Let a key x be inserted when the tree already holds some keys. Look at the nearest smaller key a and the nearest larger key b among them. Where in the tree will x end up relative to a and b?
3Hint 3
The new node becomes a child of a or b, whichever of them was inserted later, which is also the deeper one. It remains to find, for each key, its neighbours by value at the moment of insertion. Try going through the insertions from the end.
4The idea
The depth of a new key is 1 + max(depth of a, depth of b), where a and b are its neighbours by value among those already inserted. A linked list finds the neighbours for all keys: line all keys up in increasing order and remove them in the reverse order of insertion. At the moment x is removed, the list holds exactly the keys inserted before it, and its neighbours in the list are the a and b we need.
5Walkthrough
Why a child of the later neighbour in particular. Let a have been inserted before b. When b was inserted, it passed by a: there were no keys between them, so at every node above a it went where a would have gone, and at a itself it turned right. So b lies in the right subtree of a, below it. A key x between them follows the same path down to b, turns left at b, and b has no left branch: a key in it would lie between a and b. So x becomes the left child of b, and its depth is one more than that of b, the deeper of the neighbours. If there is no neighbour on one side, take its depth as zero; the first key gets depth 1.
The list is the arrays prev and next over values from 0 to n + 1, where 0 and n + 1 are sentinels. Go through the permutation from the end: remember a key's neighbours and remove it, linking the neighbours to each other. Then go through the permutation from the start and compute the depths by the formula: the height is their maximum, the comparisons the sum of the depths minus one each. The sum reaches 2·10¹⁰, so Go needs an int64.
On the third test the height is 8350: 8349 shocks in the catalogue have a depth of exactly 10 km, the value USGS sets when the depth could not be determined, and they all line up in a chain.
5+Solution
6Complexity
O(n) time: two passes over the permutation, each step O(1). Memory O(n). It can also be done in O(n log n): any ordered set finds the neighbours by value at the moment of insertion, but in Python that needs a balanced tree, which the standard library does not have.
7Common mistakes
- Honest insertion. The sixth, seventh and eighth tests are increasing keys, decreasing keys and the “zigzag” 1, n, 2, n − 1, …: a height of 2·10⁵ and 2·10¹⁰ work.
- Recursion. Even on the third test the tree is eight thousand nodes deep, and a recursive insertion hits Python's depth limit.
- The depth of the earlier neighbour. The new node hangs under the later, that is, deeper neighbour: max, not the depth of a or b at will.
- A 32-bit sum. On the sixth test there are 19,999,900,000 comparisons.