Huffman's Greed

We first fix some terminology on trees. A tree is defined inductively: it has a root which is either an external node (a leaf) or an internal node that has a sequence of trees as its children. An internal node is called the parent of the roots of its child trees. The level of a node is defined inductively: the root has level $0$, and every other node has level one greater than its parent.

In a binary tree every internal node has exactly two children: its left sub-tree and its right sub-tree. In a labelled binary tree every internal node also carries a string, its label. A binary search tree is a labelled binary tree in which every internal node $t$ satisfies: all labels in the left sub-tree of $t$ are less than the label of $t$, which in turn is less than all labels in the right sub-tree of $t$. Comparisons use lexicographic (alphabetic) order on strings.

An inorder traversal visits a leaf directly, and for an internal node it first traverses the left sub-tree, then visits the node, then traverses the right sub-tree. Hence an inorder traversal of a binary search tree lists the labels in lexicographic order. Binary search trees of different shapes may still yield the same inorder sequence.

To look up a string $s$, we compare $s$ with the label $l$ of the current root: we stop if $s = l$; if $s < l$ we continue in the left sub-tree; if $s > l$ we continue in the right sub-tree. Reaching a leaf means $s$ is not stored in the tree.

The number of comparisons depends on $s$ and on the shape of the tree, so we want to build a tree that stores a given set of strings while allowing access that is as fast as possible. Since we do not know in advance which strings will be searched for, we assume a probability distribution.

Let $n$ be the number of strings to store, and let $K_1, \dots, K_n$ be these strings in lexicographic order. Let $p_1, \dots, p_n$ and $q_0, \dots, q_n$ be $2n+1$ non-negative real numbers with

$\sum_{i=1}^{n} p_i + \sum_{i=0}^{n} q_i = 1.$

Their meaning is:

• $p_i$ = probability that the search string $s$ equals $K_i$.
• $q_i$ = probability that $s$ lies strictly (lexicographically) between $K_i$ and $K_{i+1}$.

By convention $q_0$ is the probability that $s < K_1$, and $q_n$ the probability that $s > K_n$.

We want a binary search tree over the labels $K_1, \dots, K_n$ that minimises the expected number of comparisons, namely

$\mathrm{cost} = \sum_{i=1}^{n} p_i \cdot \big(1 + \operatorname{level}(K_i)\big) + \sum_{i=0}^{n} q_i \cdot \operatorname{level}(\ell_i),$

where $\ell_i$ is the leaf reached when searching for a string that lies strictly between $K_i$ and $K_{i+1}$ (using the border convention above).

For example, when $n = 2$ there are exactly two possible binary search tree shapes; the answer is the one whose expected cost is smaller.

The input contains several test cases. Each test case starts with an integer $n$ with $1 \le n \le 200$. Then follow $2n+1$ non-negative integers, the frequencies. Let $s$ be the sum of all these frequencies; you may assume $1 \le s \le 1\,000\,000$. The probabilities $p_1, \dots, p_n$ and $q_0, \dots, q_n$ are obtained, in this order, by dividing the frequencies by $s$: the first $n$ frequencies give $p_1, \dots, p_n$, and the next $n+1$ give $q_0, \dots, q_n$. The last test case is followed by a single $0$.

For each test case, output on its own line the integer $\mathrm{cost} \cdot s$, where $\mathrm{cost}$ is the minimum expected number of comparisons achievable by any binary search tree for the given frequencies.