Problem You are given a full binary tree with n leaves that have either the value 1 or the value 0. You are playing the following game with your friend. You get to play first and decide whether to go to the left or the right subtree of the root and then your friend plays and decides whether to continue to the left or right subtree. You continue playing like that until you reach a leaf node. You win when you the game ends on a leaf node with value 1. Equivalently you may assume that each node of the binary tree is either a "max"/"or" node or a "min"/"and" node, see Figure 1. By V we denote max or the "or" binary operator and by A we denote min or "and". In what follows we always assume that the root node is ^ or equivalently that player 0 plays first. We want to know which player wins which corresponds to the value at the root of the tree. It is easy to evaluate the value at the root node with a recursive algorithm that visits all n leaves of the tree (similarly to the first Midterm problem), see Figure 1 for an example. By using randomness we can improve this runtime. Instead of trying both left and right child at every round we consider Algorithm 1 which picks a random branch at every round. On expectation Algorithm 1 will require to visit much less than n leaves. This is because for A nodes or nodes where Player 0 plays if we look at a random branch and see that its value is 0 we immediately know that the value of the current node is 0 (this is because 0 A 1 = 0, 1 A 0 = 0, 0 A 0 = 0). Similarly, for V nodes if the random branch returns 1 we do not need to recurse to the other branch. In Algorithm 1 the global variable /V is initialized to 0 and counts the number of leaves that this randomized algorithm visits. Observe that since at every step in Algorithm 1 we pick a branch at random, the value of N when all recursive calls return is a random variable. Your task is to design an algorithm that takes as input the values of the leaves of the tree as a binary string and outputs the expected number of leaves visited by the given randomized algorithm, Algorithm 1, i.e., the expected value of NV after the Who Wins(v, 0) returns. Input: * Input should be read in from stdin. . The first line will contain the height of the tree (n). . One n-character line will follow, with each character indicating whether player 0 or 1 wins. . Os and Is are listed in the order they appear in a printout of the tree - first the element found by only taking left branches, then the element found by taking n - 1 lefts and a right, then the element found by taking n - 2 lefts, one right, and one left, then n - 2 lefts and two rights, then n - 3 lefts, one right and two lefts, etc.Player 0 Player 1 Player 1 Player 0 Player 0 Player O Player 0 Figure 1: By V we denote max or the "or" binary operator and by A we denote min or "and". In this case we have that the values of the bottom level A nodes are 0, 0, 0, 1 from right to left. The values of the V nodes are 0, 1 from right to left. Therefore, the value at the root of the tree is 0 The expected value of N of Algorithm 1 in the above example is 3.0. Algorithm 1: Who Wins(v, player) /* Initialize some global variable / = 0, i.e., N is not re-initialized at every recursive call */ 1 if v is a leaf node then 2 N =N+1 Return (value of v) 4 else Let $1, $2 be the left and right subtrees of v in a random order next + (player + 1) mod 2 next contains the next player. if Who Wins(81, next) = player then Return player player 0 is A, player 1 is V. else Return Who Wins($2, next) Output: . The output should be written to stdout. The output should be the expected value of total leaves, N, at the end of execution (e.g. 2 . 5). A small margin of error is allowed\f
