TopCoder problem "SkewTree" used in TCCC '03 Finals (Division I Level Three)



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 a int[] 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.
 

Definition

    
Class:SkewTree
Method:bestScore
Parameters:int[], int[]
Returns:int
Method signature:int bestScore(int[] values, int[] probs)
(be sure your method is public)
    
 

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1641

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4497&pm=1641

Writer:

brett1479

Testers:

zoidal , lbackstrom , schveiguy

Problem categories:

Dynamic Programming