AlmostOptimalBST
2021 Regional 1 · 2021-04-13 · by misof
Problem Statement
In this problem we consider the simplest possible binary search trees (BSTs).
(When looking for an element in a BST, you start by comparing it to the root. If you are looking for a smaller element, you recursively search for it in the left subtree, and if you are looking for a bigger element, you do the same with the right subtree.
When inserting a new element into a BST, you follow the same path as when looking for it and then you insert it at the place where your unsuccessful search terminated.)
When searching for an element X in a BST, the time complexity is clearly proportional to the number of BST nodes we have to compare to X.
A BST is called worst-case optimal if it minimizes the maximum number of comparisons.
A BST is called average-case optimal if it minimizes the expected number of comparisons under the assumption that X is one of the elements present in the BST, picked uniformly at random.
A BST is called only WC optimal if it is worst-case optimal but not average-case optimal.
A BST is called only AC optimal if it is average-case optimal but not worst-case optimal.
Each permutation of numbers 0 to N-1 determines a binary search tree as follows: we start with an empty BST and we insert the 0 to N-1 in the order given by the permutation.
Note that different permutations may produce the same BST. For example, both the permutation {2, 1, 0, 3} and {2, 1, 3, 0} produce the BST shown below. (Node 2 is the root of that BST.)
2 / \ 1 3 / 0
For the BST above the maximum number of comparisons is 3 (when looking for element 0) and the expected number of comparisons is exactly 2 (the average of 3, 2, 1, and 2). For N = 4 this BST is both worst-case and average-case optimal.
Given N, let:
- OWC be the number of permutations of 0 to N-1 that determine a BST that is only WC optimal.
- OAC be the number of permutations of 0 to N-1 that determine a BST that is only AC optimal.
Return a
Constraints
- N will be between 1 and 4000, inclusive.
4
Returns: {4, 0 }
The BST shown below is one of the two BSTs that are worst-case but not average-case optimal for N = 4. 0 \ 2 / \ 1 3 There are two permutations that produce this BST: {0,2,1,3} and {0,2,3,1}. For N = 4 there are no only-AC-optimal BSTs.
8
Returns: {9680, 0 }
31
Returns: {0, 0 }
The only BST that is both worst-case and average-case optimal for N = 31 is the perfectly balanced BST with depth 4.
4000
Returns: {948317503, 0 }
1
Returns: {0, 0 }
Submissions are judged against all 24 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AlmostOptimalBST with a public method vector<int> count(int N) · 24 test cases · 2 s / 256 MB per case