SkewTree
TCCC '03 Finals · 2003-04-05 · by brett1479
TCCC '03 Finals · 2003-04-05 · by brett1479 · Dynamic Programming
Problem Statement
Problem Statement
In a binary tree, every node has an optional left, and optional right child node. A BST (binary search tree) is a binary tree that satsifies the following properties:
1) Every node has a unique value
2) The value at a given node must be greater than the value at every node in its left subtree
3) The value at a given node must be less than the value at every node in its right subtree
The depth of a node in a BST is defined as such:
1) The top node (root) has depth 0
2) Every node has depth 1 higher than its parent
Usually, when given a list of distinct values, it is best to build a balanced binary search tree - a tree where the size of the left subtree is approximately the same as the size of the right subtree at each node. A balanced tree isn't always the best solution though. Given aint[] values of distinct values and a int[] probs containing the percentage chance of each element being accessed, your method will return the best (lowest) access score achievable by a BST containing the given values. The access score of any BST is computed by adding together the access scores for all of its nodes. The access score for a particular node is calculated by the formula p*(d+1) where p is the probability of that node being accessed, and d is the depth of that node in the tree.
1) Every node has a unique value
2) The value at a given node must be greater than the value at every node in its left subtree
3) The value at a given node must be less than the value at every node in its right subtree
The depth of a node in a BST is defined as such:
1) The top node (root) has depth 0
2) Every node has depth 1 higher than its parent
Usually, when given a list of distinct values, it is best to build a balanced binary search tree - a tree where the size of the left subtree is approximately the same as the size of the right subtree at each node. A balanced tree isn't always the best solution though. Given a
Constraints
- values and probs will both contain between 1 and 50 elements, inclusive.
- Each element of values and probs will be between 1 and 1000, inclusive.
- Each element of values will be unique.
- values and probs will contain the same number of elements.
Examples
0)
{1,2}
{1,2}
Returns: 4
The best tree looks like: 2 \ 1
1)
{1,2,4,3,5,6}
{1,2,3,4,5,6}
Returns: 44
Here the best tree is: 5 / \ / \ 3 6 / \ 2 4 / 1 The score is 5*1 + 4*2 + 6*2 + 2*3 + 3*3 + 1*4 = 44
2)
{6,5,3,7,51,36}
{65,13,49,62,34,16}
Returns: 492
3)
{44,211,92,88,688,569,143,291,145,28,188,550,331,327,603,46,497,479,250,903,905,735,539,726,382,745,196,57,98,926,728,205,4,366,899}
{666,256,8,318,743,842,515,415,31,352,929,665,170,512,184,901,613,669,615,971,197,866,803,773,4,564,521,921,306,316,69,921,421,916,985}
Returns: 74366
4)
{879,244,142,959,141,145,343,881,871,456,398,707,262,566,85,831,518,182,604,179,435,728,763,307,617,545,703,322,930,926,147,424,463,953,209,247,837}
{169,132,174,184,345,185,521,464,14,97,803,125,950,84,298,255,511,485,785,504,584,493,629,59,917,287,361,832,758,89,526,892,75,360,836,846,103}
Returns: 61345
Submissions are judged against all 43 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SkewTree with a public method int bestScore(vector<int> values, vector<int> probs) · 43 test cases · 2 s / 256 MB per case