Let $x_0, \ldots , x_{n-1}$ denote $n$ boolean variables (i.e., variables taking only values $0$ and $1$). A binary decision diagram (BDD) over these variables is a diagrammatic representation of a boolean function $f(x_0, \ldots , x_{n-1})$ as inputs.
A BDD is a rooted binary tree such that all internal vertices $v$ have precisely two children. The edges connecting an internal vertex $v$ with its children are labelled with a $0$ or $1$ (exactly one of each). Each leaf vertex is also labelled with a $0$ or $1$. We note that a BDD may consist of a single vertex, which is considered to be both the root and a leaf vertex.
Given input $(x_0, \ldots , x_{n-1})$, the boolean function represented by the BDD is evaluated as follows.
let $v$ be the root vertex
let $i \leftarrow 0$
while $v$ is not a leaf do
replace $v$ with the child vertex of $v$ by traversing the edge labelled $x_ i$
increase $i$ by $1$
output the label of leaf vertex $v$
Consider the function $f(x_0,x_1,x_2)$ represented by the BDD above. To evaluate $f(1,0,1)$, we start from the root, we descend along edges labelled $1$, $0$, and then $1$. We reach a leaf vertex labelled $1$, so $f(1,0,1) = 1$.
A BDD is minimal if there is no way to replace any subtree of an internal vertex of the BDD by a single leaf vertex to get a new BDD defining the same boolean function. The BDD depicted above is minimal. It is a fact that for each boolean function $f$, there is a unique minimal BDD that represents the boolean function.
In this problem, you are given an $n$-variable boolean function specified by a list of the $2^ n$ different values the function should take for various inputs. Compute the number of vertices in the minimal BDD representing this function.
The first line of input consists of a single integer $1 \leq n \leq 18$. Then one more line follows that contains $2^ n$ values (either $0$ or $1$) describing an $n$-variable boolean function.
We think of these values as being indexed from $0$ to $2^ n-1$. The $i$th such value represents $f(x_0, \ldots , x_{n-1})$ where $x_ j$ is the $j$th least-significant bit of the binary representation of $i$. In other words, $x_ j$ is the coefficient of $2^ j$ in the binary expansion of $i$.
The third sample input below corresponds to the BDD depicted above.
Output consists of a single integer $m$ that is the number of vertices in the unique minimal BDD representing the boolean function from the input.
Sample Input 1 | Sample Output 1 |
---|---|
2 1 1 0 1 |
5 |
Sample Input 2 | Sample Output 2 |
---|---|
2 0 0 0 0 |
1 |
Sample Input 3 | Sample Output 3 |
---|---|
3 1 0 1 0 1 1 1 0 |
7 |