Allen and Bessie are playing a simple number game. They both know a function f: \{0,…
- User
Allen and Bessie are playing a simple number game. They both know a function f: {0, 1}^n → R, i. e. the function takes n binary arguments and returns a real value. At the start of the game, the variables x_1, x_2, ..., x_n are all set to -1. Each round, with equal probability, one of Allen or Bessie gets to make a move. A move consists of picking an i such that x_i = -1 and either setting x_i → 0 or x_i → 1.
After n rounds all variables are set, and the game value resolves to f(x_1, x_2, ..., x_n). Allen wants to maximize the game value, and Bessie wants to minimize it.
Your goal is to help Allen and Bessie find the expected game value! They will play r+1 times though, so between each game, exactly one value of f changes. In other words, between rounds i and i+1 for 1 ≤ i ≤ r, f(z_1, ..., z_n) → g_i for some (z_1, ..., z_n) ∈ {0, 1}^n. You are to find the expected game value in the beginning and after each change. Input
The first line contains two integers n and r (1 ≤ n ≤ 18, 0 ≤ r ≤ 2^{18}).
The next line contains 2^n integers c_0, c_1, ..., c_{2^n-1} (0 ≤ c_i ≤ 10^9), denoting the initial values of f. More specifically, f(x_0, x_1, ..., x_{n-1}) = c_x, if x = \overline{x_{n-1} … x_0} in binary.
Each of the next r lines contains two integers z and g (0 ≤ z ≤ 2^n - 1, 0 ≤ g ≤ 10^9). If z = \overline{z_{n-1} ... z_0} in binary, then this means to set f(z_0, ..., z_{n-1}) → g.
Output
Print r+1 lines, the i-th of which denotes the value of the game f during the i-th round. Your answer must have absolute or relative error within 10^{-6}.
Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-6}.
Examples
Input
2 2 0 1 2 3 2 5 0 4
Output
1.500000 2.250000 3.250000
Input
1 0 2 3
Output
2.500000
Input
2 0 1 1 1 1
Output
1.000000
Note
Consider the second test case. If Allen goes first, he will set x_1 → 1, so the final value will be 3. If Bessie goes first, then she will set x_1 → 0 so the final value will be 2. Thus the answer is 2.5.
In the third test case, the game value will always be 1 regardless of Allen and Bessie's play.
Assistant
We need to compute expected value of a game where two players take turns setting bits, with equal probability each turn of which player moves (Allen or Bessie). Allen wants to maximize final f(x), Bessie minimize. At start all bits are -1 (unset). They alternate? Actually: "Each round, with equal probability, one of Allen or Bessie gets to make a move." So it's not strict alternation; each turn, it's random who moves? But wait: They both know f and they play optimally given the random assignment of move? Hmm typical "minimax with random turn order" perhaps the value can be computed via a recursive dynamic programming: each state (set of variables assigned) with knowledge of whose turn? But here the turn assignment is random each round: each round, with equal probability, the move is made by Allen or Bessie. This implies that the identity of the player making the move at each step is random, independent? They also want to maximize/minimize expected final value? Actually, the game is not zero-sum with deterministic moves? But Allen wants to maximize the final value, Bessie wants to minimize it. Since moves are random, the optimal strategy for each depends on the distribution of who will move in the future. Usually, such games can be analyzed by considering that at each step, the player who gets to move chooses the action that maximizes (if Allen) or minimizes (if Bessie) the expected value from that state, where the expectation is over future random assignment of moves? But careful: The process is: At each round, a player is chosen uniformly at random. Then that player makes a move. Then we repeat until all bits set. The players know f and act optimally to achieve their goals, assuming future randomness. Since the future randomness (who moves) is independent and each player's decisions affect the state, we can think of this as a stochastic game with two players where at each step nature chooses which player moves, then that player chooses an action. Allen's objective: maximize the expected payoff (final f). Bessie's objective: minimize it. This is a zero-sum stochastic game with perfect information and randomness in turn order. Both players have full knowledge of the state. Since it's zero-sum, we can define a value function V(S) for each state (set of assigned bits and their values? Actually, state is partial assignment of variables). But note: At each state, there is no notion of whose turn it is because the turn will be randomly decided. So the value from a state (i.e., expected final payoff under optimal play) should be independent of a predetermined player to move; it's just the expected outcome assuming both play optimally from that state given the rule that moves are selected by random player each turn. However, since the players have opposing goals, the state value can be defined as the value of the game from that state. This value should satisfy a recursion: For a state where some variables are already set (others are -1), the game will continue. At the next step, a random player is chosen: Allen with prob 1/2, Bessie with prob 1/2. If it's Allen's turn, he will choose an unset variable i and assign it to either 0 or 1, aiming to maximize the expected value from the resulting state. If it's Bessie, she will choose to minimize. So the recursion is:
Let state S be a partial assignment (some bits fixed, others unknown). Let U be set of indices unset. If U is empty, value = f(full assignment). Otherwise:
V(S) = (1/2) * max_{i in U, b in {0,1}} V(S ∪ {x_i = b}) + (1/2) * min_{i in U, b in {0,1}} V(S ∪ {x_i = b})
But careful: The player who moves can choose both which variable and which bit. That's the move. So the recursion is as above. However, note: Each player wants to maximize/minimize the expected payoff, but the expectation is over future randomness, including future player assignments. But here we've already taken expectation over the immediate random player selection; for each player's move, they choose optimally assuming that after their move, the game continues with the same rule. So indeed V(S) = (1/2) * max_{actions} V(S after action) + (1/2) * min_{actions} V(S after action). This seems plausible.
But is that the standard interpretation? Let's test with n=1. n=1, two possible assignments: f(0)=2, f(1)=3 (example 2). Initially no bit set. State S0 empty. Unset: {1}. Then:
V(empty) = 0.5 * max_{b∈{0,1}} V({x1=b}) + 0.5 * min_{b∈{0,1}} V({x1=b}). But V({x1=b}) = f(b) because after assignment game ends. So V({0})=2, V({1})=3. Then max = 3, min = 2. So V(empty) = 0.53 + 0.52 = 2.5. That matches example output 2.5.
Now test n=2 with all f=1 (example 3). For any full assignment f=1. Since all leaves are 1, the value of any state should be 1, because no matter what choices, final is 1. Does recursion yield 1? Let's compute. For state with one variable set, say x1 set to some value, we have one unset variable i. Then V(state) = 0.5* max_{b} V(full) + 0.5* min_{b} V(full) = 0.51+0.51 =1. For empty state: V(empty) = 0.5* max_{i,b} V(state after setting i to b) + 0.5* min_{i,b} V(state after setting i to b). But all V(state after setting any variable) = 1, so max=min=1, so V=1. Good.
Thus recursion is correct.
Now the problem: We need to compute V(empty) for given f, initially and after r updates (changing one entry of f). n up to 18, so number of states (partial assignments) is huge (3^n potentially). But we need to compute quickly. r up to 2^18 (~262k). So need an efficient way to recompute V(empty) after point updates to f.
Observation: This game resembles evaluating a kind of "minimax with random turn" over binary variables. This may be related to the concept of the "value of a game tree" with random turn order. For a full binary tree of depth n (each variable corresponds to a level, but order of moves can be any variable), the process is not a tree because moves can be in any order, but the state is symmetric with respect to order? Actually the game is "simultaneous" in that players choose any remaining variable. This is not a fixed-turn order game.
But maybe we can derive that the value V(empty) is simply the average over all possible sequences of assignments? Not exactly because players' choices are adversarial. But maybe there is a known simplification: Given the symmetric random player selection, the value may be computed as something like the result of a "random-turn game" which is known to equal the "selection" or "randomized" value.
In fact, there is known result: For a finite game where each turn a random player moves, the value of the game from the initial state equals the average over all permutations of players? Not exactly.
Alternatively, we can think of the game as a "minimax" value of a binary decision tree where at each node we have a branching factor = number of unset variables *2, but the recursion above seems like for each state we take a 50-50 mix of max and min over all possible moves. This is reminiscent of the concept of "bool" circuits? Possibly can be expressed as a linear combination of f values weighted by some probabilities determined by the game.
Given n <= 18, we could compute V(empty) by DP over subsets? But there are 2^n possible assignments for the final function; but partial assignments are 3^n, which for n=18 is 3^18 = 387,420,489 ~ 4e8, too large. But maybe we can compress due to symmetry: The value of a state may depend only on which variables have been set, but also on the actual values assigned to those variables? Yes, because f depends on full assignment. So V(S) depends on the actual values assigned to set variables; not just set of indices. So state space is 3^n (each variable: -1,0,1). That's too large.
We need a better way. Perhaps there is a closed form for V(empty) in terms of the Walsh-Hadamard transform? Since the recursion resembles an operation that can be expressed as a linear operator on the space of functions on {0,1}^n. Maybe V(empty) is a linear function of the f values? Let's test with n=2, initial f: 0,1,2,3 (example 1). Output is 1.5 for initial f. Let's compute manually using the recursion to verify.
We have 2 bits: x1, x2? Actually ordering: they consider x_0,...,x_{n-1}. For n=2, f(00)=c0=0, f(01)=c1=1, f(10)=c2=2, f(11)=c3=3.
Now compute V(empty) by recursion:
First compute values of states with one variable set.
State where x0 set to 0, x1 unset: V(0,-) depends on f: final value depends on x1. So V(0,-) = 0.5max_{b} V(0,b) + 0.5min_{b} V(0,b) where V(0,b)=f(0,b). Actually after setting x1, game ends, so V(0,b)=f(0,b). So V(0,-) = 0.5* max(f(00), f(01)) + 0.5* min(f(00), f(01)) = 0.5* max(0,1) + 0.5min(0,1)=0.51+0.5*0=0.5.
Similarly state (1,-): V(1,-) = 0.5max(f(10), f(11)) + 0.5min = 0.53+0.52 = 2.5.
State (-,0): x1 set to 0, x0 unset: V(-,0) = 0.5max(f(00), f(10)) + 0.5min = 0.52+0.50=1.
State (-,1): x1 set to 1: V(-,1) = 0.5max(f(01), f(11)) + 0.5min = 0.53+0.51=2.
Now initial empty state: V(empty) = 0.5 * max over moves of V(state after move) + 0.5 * min over moves. Moves: pick i, set to 0 or 1. So possible resulting states: (0,-), (1,-), (-,0), (-,1). Their values: 0.5, 2.5, 1, 2. So max among these = 2.5, min = 0.5. So V(empty) = 0.52.5 + 0.50.5 = 1.5. That matches output 1.5. Good.
Now after first update: "2 5" means z=2 -> binary 10 (x1=0? careful: they say if z = \overline{z_{n-1}...z_0} in binary, then set f(z_0,...,z_{n-1}) → g. So for n=2, z = 2 means bits: z1 z0 = 1 0? Actually \overline{z_{n-1} ... z_0} means the number formed by bits in order MSB is z_{n-1}, LSB is z_0. So if we denote x_0,...,x_{n-1} as the arguments of f, then f(x_0,...,x_{n-1}) corresponds to integer with binary representation x_{n-1}...x_0 (i.e., reverse order). So for z=2 (binary 10) -> x_{n-1}=1, x_0=0 => x1=1, x0=0? Actually careful: Let's define indices: They say f: {0,1}^n → R, and they specify c_0,...,c_{2^n-1} where f(x_0, x_1, ..., x_{n-1}) = c_x if x = \overline{x_{n-1} … x_0} in binary. So x is constructed by reading bits from x_{n-1} (most significant) down to x_0 (least significant). For example, n=2: (x0, x1) mapping? Actually they wrote x_0, x_1, ..., x_{n-1} so the order of arguments is x_0, x_1, ..., x_{n-1}. Then c index is x = (x_{n-1} ... x_0)_2. So for n=2: (x0,x1) -> index = (x1 x0)2. So (0,0)-> 0; (1,0)-> (0 1?) Wait compute: x1 is most significant? Actually if we take x{n-1} as most significant, then for n=2, x1 is the high bit. So index = (x1)2 + (x0). So (x0=0,x1=0) -> index 0; (1,0) -> (0? x0=1,x1=0) index = 02+1=1; (0,1) -> (1,0?) x0=0,x1=1 => index=12+0=2; (1,1) -> index=12+1=3. So mapping: f(0,0)=c0; f(1,0)=c1; f(0,1)=c2; f(1,1)=c3. So x0 is LSB, x1 is MSB. But note order in state description may be reversed? Not critical.
Now update: "2 5": z=2, means set f(x0=0,x1=1) to 5. So previously it was 2. So new f: c0=0, c1=1, c2=5, c3=3.
Now compute V(empty) manually? Output after first update is 2.25. Let's compute:
We recalc states with one variable set. But careful: The moves for state (x0 set to something, x1 unset) etc.
Define variables: we have two variables, index 0 and 1.
Compute V(0,-): x0=0, x1 unset. final f values: f(0,0)=0, f(0,1)=? Since x0=0, x1 variable: f(0,0)=c0=0; f(0,1)=c2=5? Wait mapping: f(x0,x1) => index = x12 + x0. So for (0,0): x0=0,x1=0 -> index=0 -> c0=0. For (0,1): x0=0,x1=1 -> index=2 -> c2=5. So V(0,-) = 0.5max(0,5)+0.5min(0,5)=0.55+0.5*0=2.5.
V(1,-): x0=1, x1 unset: f(1,0)=c1=1; f(1,1)=c3=3. => V = 0.5max(1,3)+0.5min(1,3)=0.53+0.51=2.
V(-,0): x1=0, x0 unset: f(0,0)=0; f(1,0)=1 => V = 0.5max(0,1)+0.5min(0,1)=0.51+0.50=0.5.
V(-,1): x1=1, x0 unset: f(0,1)=5; f(1,1)=3 => V = 0.5max(5,3)+0.5min(5,3)=0.55+0.53=4.
Now empty state: V = 0.5max over {2.5,2,0.5,4} + 0.5min = 0.54 + 0.50.5 = 2+0.25=2.25. Correct.
Second update: "0 4" sets f(0,0) to 4. So c0=4, others: c1=1, c2=5, c3=3. Output is 3.25.
Let's compute: V(0,-): (0,-): f(0,0)=4, f(0,1)=5 => V=0.55+0.54=4.5? Actually max=5, min=4 => avg=4.5? Wait compute: 0.5max+0.5min = (5+4)/2 = 4.5. But that's not consistent with earlier method? Actually formula is 0.5max+0.5min, so it's the average of max and min. So yes 4.5.
V(1,-): (1,-): f(1,0)=1, f(1,1)=3 => V=0.53+0.51=2.
V(-,0): x1=0: f(0,0)=4, f(1,0)=1 => V=0.54+0.51=2.5? max=4, min=1, avg=2.5.
V(-,1): x1=1: f(0,1)=5, f(1,1)=3 => V=0.55+0.53=4.
Now V(empty)=0.5max(4.5,2,2.5,4) + 0.5min(...) = max=4.5, min=2 => V=0.54.5+0.52=2.25+1=3.25. Correct.
Thus recursion is correct.
Now we need to compute V(empty) efficiently for given f with up to 2^n entries (n up to 18, so up to 262144 entries). r can be up to 2^18, so we need to support point updates to f and recompute V(empty) quickly (perhaps O(2^n) per update is too slow if r large? 2^18 * 2^18 = 2^36, too big). Need something like O(n * 2^n) preprocessing and O(1) or O(n) per update.
Observe that V(empty) can be expressed as a linear function of the f values? Let's test linearity. For n=1: V(empty)=0.5max(f(0),f(1)) + 0.5min(f(0),f(1)) = (f(0)+f(1))/2? Actually max+min = f(0)+f(1). So V = (f(0)+f(1))/2. So it's linear! Indeed for n=1 it's simply average. For n=2, we computed V(empty) from f values; is it linear? Let's see if V(empty) = a0 f(00) + a1 f(01) + a2 f(10) + a3 f(11). For initial f (0,1,2,3), V=1.5. If we double all f, V should double? Let's test: if f = (0,2,4,6) (double), V should be 3? Actually compute quickly: V(0,-)=0.5max(0,2)+0.5min(0,2)=1; V(1,-)=0.5max(4,6)+0.5min=5; V(-,0)=0.5max(0,4)+0.5min=2; V(-,1)=0.5max(2,6)+0.5min=4; Then V=0.55+0.51=3. So indeed double. So scaling property holds. But is it linear? Check superposition: Suppose we have f = f1 + f2. Does V(f1+f2) = V(f1)+V(f2)? Possibly yes because recursion involves max and min, which are not linear. However, perhaps the structure of this game yields that V(empty) is actually the average over all leaves of some weight? The max/min may collapse due to symmetry? For n=2, compute V for f = (1,0,0,0). Let's test: f00=1, others 0. Compute V(0,-)=0.5max(1,0)+0.5min(1,0)=0.5; V(1,-)=0.5max(0,0)+0.5min=0; V(-,0)=0.5max(1,0)+0.5min=0.5; V(-,1)=0.5max(0,0)+0.5min=0; V(empty)=0.5max(0.5,0,0.5,0)+0.5min=0.50.5+0.50=0.25. So V=0.25. For f = (0,1,0,0) => f01=1. Compute: V(0,-)=0.5max(0,1)+0.5min=0.5; V(1,-)=0.5max(0,0)=0; V(-,0)=0.5max(0,0)=0; V(-,1)=0.5max(1,0)+0.5min=0.5; V(empty)=0.5max(0.5,0,0,0.5)+0.5min=0.50.5+0.50=0.25. So also 0.25. For f = (0,0,1,0) => f10=1. Compute: V(0,-)=0.5max(0,0)=0; V(1,-)=0.5max(1,0)+0.5min=0.5; V(-,0)=0.5max(0,1)+0.5min=0.5; V(-,1)=0.5max(0,0)=0; V(empty)=0.50.5+0.50=0.25. For f = (0,0,0,1) => f11=1. V(0,-)=0.5max(0,0)=0; V(1,-)=0.5max(0,1)+0.5min=0.5; V(-,0)=0.5max(0,0)=0; V(-,1)=0.5max(0,1)+0.5min=0.5; V(empty)=0.50.5+0.50=0.25. So all singletons give 0.25. Therefore the weights for each f(x) are equal? But total sum of f's in first test (0,1,2,3) gave V=1.5, sum=6, average=1.5. So indeed V = average of all f values? Check: For f all ones, average=1, V=1. For initial test, average = (0+1+2+3)/4 = 1.5, matches. For updated test: after first update: f = (0,1,5,3) average = 9/4 = 2.25, matches. After second update: (4,1,5,3) average = 13/4 = 3.25, matches. So in these examples, V(empty) equals the arithmetic mean of all 2^n f values.
Is that always true? Let's test another random f for n=2: f = (0,10,0,0). average=2.5. Compute manually: f00=0, f01=10, f10=0, f11=0. Compute V(0,-): max(0,10)=10, min=0 =>5; V(1,-): max(0,0)=0, min=0 =>0; V(-,0): max(0,0)=0 =>0; V(-,1): max(10,0)=10, min=0 =>5; So V(empty)=0.5max(5,0,0,5)+0.5min =0.55+0.50=2.5. Yes average.
Another: f=(0,0,0,10) average=2.5: V(0,-)=0, V(1,-)=5, V(-,0)=0, V(-,1)=5 => V=2.5. Good.
What about n=3? Let's test a random f manually to see if V(empty) equals average. Suppose n=3, f values maybe like some pattern. We can attempt to compute with recursion perhaps using a programmatic approach mentally? Let's attempt with a specific small case to see if it matches average.
But maybe there's a theorem: For this game where at each step a player is chosen uniformly at random to move, and the moves consist of setting a remaining variable to 0 or 1 (any variable), the expected value under optimal play is simply the average of f over all 2^n assignments. This seems plausible due to symmetry: Because the random selection of player each turn neutralizes the adversarial nature, making the game essentially random? But is it exactly the average? Let's think.
Define V(S) for partial assignment. Could it be that V(S) equals the average of f over all completions of S? i.e., average over assignments to unset variables? For S empty, that's the full average. For S with some variables fixed, maybe V(S) equals the average over completions? Let's test for n=2, state (0,-): we computed V(0,-)=0.5max+0.5min. If V(S) equals average over completions, then completions of (0,-) are f(0,0) and f(0,1). Their average is (0+1)/2=0.5? But for initial f (0,1,2,3), that average is 0.5. And we computed V(0,-)=0.5. So matches. For state (1,-): completions: f(1,0)=2, f(1,1)=3 average=2.5; V(1,-)=2.5. For state (-,0): completions: f(0,0)=0, f(1,0)=2 average=1; V(-,0)=1. For state (-,1): completions: f(0,1)=1, f(1,1)=3 average=2; V(-,1)=2. So indeed those match. For the other examples after updates, also match. So hypothesis: For any state S (partial assignment), V(S) equals the average of f over all completions (i.e., over assignments to the remaining variables) – that is, the expectation if the remaining bits were chosen uniformly at random. But is that always true? Let's check more thoroughly.
General claim: For any partial assignment S (set of variables fixed to some bits), define U as set of unset variables. Then V(S) = (1/2^{|U|}) * sum_{assignment of U} f(S combined with that assignment). That is, the simple average.
We need to verify this satisfies the recursion:
If |U| = 0, then V(S) = f(full), which matches.
If |U| > 0, recursion: V(S) = 0.5 * max_{i in U, b in {0,1}} V(S ∪ {x_i=b}) + 0.5 * min_{i in U, b in {0,1}} V(S ∪ {x_i=b}).
Now if our hypothesis is correct, then V(S ∪ {x_i=b}) = average over completions of that state: i.e., average over assignments to U{i}. That is, for fixed i and b, V(S∪{i=b}) = (1/2^{|U|-1}) * sum_{assignments of U{i}} f(S with i=b, rest assigned). Let's denote A = set of assignments of U to bits, each equally likely. Then V(S) = average over all completions. So V(S) = E[f | S] where expectation over uniform random completion.
Now we need to see if this V(S) satisfies the recursion. Compute the RHS:
For each i in U, define two values: V_i^0 = average over completions with x_i=0, and V_i^1 = average with x_i=1. Since all completions are equally likely, the overall average V(S) = (V_i^0 + V_i^1) / 2. Actually careful: If we condition on x_i, the average over completions is exactly the conditional expectation given x_i. And overall average = (E[f|x_i=0] + E[f|x_i=1])/2. So V(S) = (V_i^0 + V_i^1)/2 for any i.
Now the RHS of recursion: It takes max and min over all moves (i,b). Specifically, we consider all pairs (i,b). Let M = max_{i,b} V_i^b, and m = min_{i,b} V_i^b. Then RHS = (M + m)/2.
We need to show that (M + m)/2 = (V_i^0 + V_i^1)/2 for all i? Actually we need equality: (M+m)/2 = V(S). But V(S) is not necessarily equal to (M+m)/2 unless M and m are symmetric around V(S) for each i? Actually V(S) is (V_i^0+V_i^1)/2 for any i, but that doesn't guarantee it's (M+m)/2. However, perhaps the structure ensures that the maximum over i,b of V_i^b and the minimum are actually the two values for some particular i? Not necessarily; they could be from different variables. For instance, take n=2, f such that V_i^b vary. For empty S, we have V_0^0=0.5, V_0^1=2.5, V_1^0=1, V_1^1=2. Then M=2.5, m=0.5, (M+m)/2=1.5, which equals V(S)=1.5. So it worked. But is it always that M+m = sum_{b} V_i^b for some i? Not necessarily; we need to check if it's always that the maximum and minimum are complementary? In this case, M came from (i=0,b=1) and m from (i=0,b=0) — both from same variable. But could M come from one variable and m from another? Let's attempt to construct a counterexample for n=3 maybe where the max and min are from different variables and see if average of them equals overall average of all completions.
We need to test the hypothesis more generally.
Consider n=3, f values such that the conditional expectations vary. We'll compute for some arbitrary f to test. Suppose f is defined as:
We label bits x0, x1, x2. Let's assign f values for all 8 combos. For simplicity, we might think of a function that is not symmetric, e.g., f(x0,x1,x2) = 1 if x0=0 else 0? That is f = 1 for combos where x0=0 (4 combos), 0 for others (4 combos). Then average = 0.5. Now compute V(empty). According to hypothesis, V(empty)=0.5. Let's try to compute recursively to verify.
We need to compute V for states with one variable set, etc.
Define f:
x0 is LSB? Actually mapping doesn't matter for average. Let's define bits as order: indices 0,1,2. But to compute easily, we can just assume f depends on all bits. But we can compute V(S) as average over completions, so it's easy to compute conditional expectations. For empty, V=0.5.
Now compute RHS of recursion: we need to find M and m among moves. For empty, moves: set any variable to 0 or 1.
First compute conditional expectations given each variable fixed.
For variable i=0 (x0):
- If x0=0: average over x1,x2 uniform: f=1 for all? Actually f=1 if x0=0, so average =1. So V_0^0 = 1.
- If x0=1: f=0 for all, so V_0^1 = 0.
So for i=0, values: 1 and 0.
Variable i=1 (x1):
Given x1=0: average over x0,x2: f =? f depends only on x0. So half of combos have x0=0, half x0=1. So average = 0.5. V_1^0 = 0.5. Given x1=1: similarly average = 0.5. V_1^1 = 0.5.
Variable i=2 (x2):
Similarly, independent, so both 0.5.
Thus moves yield values: from i=0: 1,0; from i=1: 0.5,0.5; from i=2: 0.5,0.5. So M = 1, m = 0. RHS = (1+0)/2 = 0.5. So matches V=0.5.
Now consider a more complex function. Let's try f where conditional expectations for different variables are not symmetric. For instance, f(x0,x1,x2) = x0100 + x110 + x2*1? But that's linear. The average would be (0+1)*100/2 + (0+1)*10/2 + (0+1)*1/2 = 50+5+0.5 = 55.5. But let's compute M and m.
Compute conditional expectations:
Given x0=0: average over x1,x2: (0100 + avg of x110 + avg of x21) = 0 + 5 + 0.5 = 5.5. Given x0=1: 100 + 5 + 0.5 = 105.5. Given x1=0: avg over x0,x2: avg x0100 = 50, plus 010, plus avg x2=0.5 => 50.5? Wait: if x1=0, then term x110 is 0. So average: x0100 average = 50 (since uniform over x0), x21 average = 0.5, sum=50.5. Given x1=1: x0100 avg=50, plus 10, plus 0.5 = 60.5. Given x2=0: avg x0100=50, avg x1*10=5, plus 0 = 55. Given x2=1: 50+5+1=56.
So moves values: (0,0)=5.5? Actually values: for variable i=0: 5.5 and 105.5. i=1: 50.5 and 60.5. i=2: 55 and 56. So M = 105.5, m = 5.5. (M+m)/2 = (111)/2=55.5. That equals the overall average 55.5. Indeed.
Notice that the max and min came from the same variable (i=0). But does it always happen that the max and min are from the same variable? Not necessarily; consider a function where one variable's conditional expectations are both moderate, while another variable gives a slightly higher max but its min is not as low, and third gives slightly lower min but its max is not as high. For the average of max and min to equal the overall average, it seems we need that the overall average is exactly (max_i max_b V_i^b + min_i min_b V_i^b)/2? But the recursion uses overall max and min across all moves, not necessarily from the same variable. So to validate the hypothesis, we need to prove that for any function f over binary variables, the average over all assignments equals (M+m)/2 where M = max_{i,b} E[f | x_i=b] and m = min_{i,b} E[f | x_i=b]? That seems unlikely. Let's try to construct a counterexample where average is not exactly (M+m)/2.
We need to find f such that the average of all completions is not equal to half of max + min among these conditional expectations. But from previous examples, it held. Let's attempt to systematically derive.
We have the recursion we need to satisfy: V(S) = (M+m)/2 if we define V(S) as average. But is it true that the average over all completions equals (max_{i,b} E[f| x_i=b] + min_{i,b} E[f| x_i=b]) / 2? Not necessarily. Let's test a small n=2 with custom f. n=2, we can compute all possibilities. For any f(00)=a, f(01)=b, f(10)=c, f(11)=d. The overall average = (a+b+c+d)/4. The conditional expectations: For variable 0 (x0): E[f|x0=0] = (a + c)/2? Wait careful: ordering: x0 is first argument? But as earlier mapping, variable indices: we have two variables, call them i=0 and i=1. Conditional expectation given x_i = b is average over the other variable. So: For i=0 (first argument, LSB? But doesn't matter) let's define: E0_0 = (f(0,0)+f(0,1))/2? Actually if i=0 fixed to 0, then average over x1: (f(0,0)+f(0,1))/2. Similarly E0_1 = (f(1,0)+f(1,1))/2. For i=1: E1_0 = (f(0,0)+f(1,0))/2, E1_1 = (f(0,1)+f(1,1))/2.
Now M = max(E0_0, E0_1, E1_0, E1_1), m = min(...). Then (M+m)/2. Compare to average A = (a+b+c+d)/4.
We can try to find a,b,c,d such that (M+m)/2 != A. Let's try to pick values where the max is from i=0, min from i=1. For example, let a=0, b=100, c=0, d=0. So f(00)=0, f(01)=100, f(10)=0, f(11)=0. Then average = 100/4=25.
Compute E0_0 = (0+100)/2=50, E0_1 = (0+0)/2=0, E1_0 = (0+0)/2=0, E1_1 = (100+0)/2=50. So values: 50,0,0,50. M=50, m=0 => (50+0)/2=25 = average. Good.
Try a=0, b=100, c=1, d=0? Let's compute: a=0, b=100, c=1, d=0. Then average = (0+100+1+0)/4=101/4=25.25.
E0_0 = (0+100)/2=50, E0_1 = (1+0)/2=0.5, E1_0 = (0+1)/2=0.5, E1_1 = (100+0)/2=50. So M=50, m=0.5 => (50+0.5)/2=25.25. Again equals average.
Maybe it's always true for n=2? Let's test general: a,b,c,d arbitrary. Compute A = (a+b+c+d)/4. Compute E0_0 = (a+b)/2, E0_1 = (c+d)/2, E1_0 = (a+c)/2, E1_1 = (b+d)/2. So M = max among these four, m = min. We need to check if (M+m)/2 = A always? That would mean that the sum of the max and min among these four numbers equals (a+b+c+d)/2? Because (M+m)/2 = A implies M+m = (a+b+c+d)/2. Is that identity always true? Let's test with numbers: Suppose a=0,b=0,c=10,d=10. Then A = (0+0+10+10)/4=20/4=5. E0_0=0, E0_1=10, E1_0=5, E1_1=5. So values: 0,10,5,5. M=10,m=0 => M+m=10, (a+b+c+d)/2 =20/2=10. Works.
Try a=0,b=10,c=20,d=30. A=60/4=15. E0_0=5, E0_1=25, E1_0=10, E1_1=20. Values:5,25,10,20. M=25,m=5 => sum=30, (a+b+c+d)/2=60/2=30. Works.
Seems plausible: For n=2, the sum of max and min among those four conditional expectations always equals half the total sum. Let's attempt to prove: Let S = a+b+c+d. The four expectations: (a+b)/2, (c+d)/2, (a+c)/2, (b+d)/2. The sum of these four is (a+b + c+d + a+c + b+d)/2 = (2a+2b+2c+2d)/2 = a+b+c+d = S. So the average of the four numbers is S/4. Now note that among any set of numbers, the sum of max and min is not necessarily equal to twice the average unless the numbers are symmetric in a particular way. But here we have four numbers, and we need M+m = S/2. Is this always true? Not for arbitrary four numbers that sum to S. For example, numbers: 1,2,3,4 sum=10. Max+min=5, S/2=5. Works? Actually 1+4=5. For numbers 1,1,1,7 sum=10, max+min=8? Actually max=7, min=1 => sum=8, but S/2=5. So not equal. So our set of four numbers is not arbitrary; they have special structure. So we need to test if such a structure forces max+min = S/2. Let's test a counterexample: Can we find a,b,c,d such that the four numbers are like 1,1,1,7? That would require (a+b)/2=1 => a+b=2; (c+d)/2=1 => c+d=2; (a+c)/2=1 => a+c=2; (b+d)/2=7 => b+d=14. Solve? From a+b=2 and a+c=2 => b=c. Then c+d=2 => b+d=2, but we need b+d=14 => contradiction. So impossible. So the structure constraints prevent such extremes.
Let's try to find a set that might break: e.g., aim for numbers 0,5,5,10? sum=20, S=20? Actually numbers 0,5,5,10 sum=20, M+m=10, S/2=10. So works. 0,4,6,10 sum=20, M+m=10. 0,3,7,10 sum=20, M+m=10. 0,2,8,10 sum=20, M+m=10. 1,4,5,10 sum=20, M+m=11? Actually max=10, min=1 =>11, S/2=10. So not equal. Can we realize 1,4,5,10? Let's solve: (a+b)/2 = 1 => a+b=2; (c+d)/2 = 4 => c+d=8; (a+c)/2 = 5 => a+c=10; (b+d)/2 =10 => b+d=20. But sum of all equations: (a+b)+(c+d)+(a+c)+(b+d) = 2+8+10+20=40 => 2(a+b+c+d)=40 => S=20, consistent. Now solve: a+b=2, a+c=10 => subtract: c - b = 8 => c = b+8. Then from c+d=8 => (b+8)+d=8 => d = -b. From b+d=20 => b + (-b) = 0 !=20. Contradiction. So not possible.
Thus maybe it's always true for n=2.
What about n=3? Let's try to see if V(S) = average over completions satisfies recursion for empty state. That requires that (M+m)/2 = overall average, where M = max_{i,b} E[f|x_i=b] and m = min. Is that identity always true for any function on {0,1}^n? Let's test with n=3 using a random function. Use brute force mental? We can attempt to construct a counterexample.
Define f for n=3 as: assign values to 8 outcomes. We'll try to make the conditional expectations such that max and min are from different variables and their average does not equal overall average.
We need to compute E[f|x_i=b] for each i,b. There are 3*2=6 numbers. Their sum? The sum over i,b E[f|x_i=b] =? For each i, sum_{b} E[f|x_i=b] = sum over all assignments f(x) (since for each fixed i, each full assignment contributes to exactly one b, and when we average over the other variables, each assignment appears exactly 2^{n-1} times? Let's compute: For a fixed i, the sum over b of E[f|x_i=b] = sum_{b} (1/2^{n-1}) sum_{x: x_i=b} f(x) = (1/2^{n-1}) sum_{x} f(x) (since each x contributes to exactly one b). So sum_{b} E[f|x_i=b] = (1/2^{n-1}) * total_sum. So total_sum = 2^{n-1} * (E_i0+E_i1). For each i, the sum of the two conditional expectations for that variable is total_sum / 2^{n-1}. That means for all i, E_i0 + E_i1 is the same? Actually total_sum is constant, so for each i, E_i0+E_i1 = total_sum / 2^{n-1}. So interesting: For any variable i, the sum of its two conditional expectations is constant, equal to (2 * average * 2^{n-1}? Wait total_sum = 2^{n} * A where A = overall average. So E_i0+E_i1 = (2^{n} * A) / 2^{n-1} = 2A. So for any i, E_i0 + E_i1 = 2A. That's a key identity! Indeed, because for any i, the expectation over the other variables of f given x_i=0 plus given x_i=1, when summed, equals 2A? Let's derive:
E_i0 = (1/2^{n-1}) * sum_{x: x_i=0} f(x) E_i1 = (1/2^{n-1}) * sum_{x: x_i=1} f(x) Sum = (1/2^{n-1}) * sum_{all x} f(x) = (1/2^{n-1}) * (2^n * A) = 2A.
So indeed, for each i, E_i0 + E_i1 = 2A. That means the two conditional expectations for a given variable are symmetric around A: they average to A. So for each i, one is ≤ A and the other ≥ A (unless both equal A). Thus A is exactly the midpoint of the two values for any variable.
Now consider the max and min over all moves (i,b). Since for each i, the two values straddle A (one >= A, one <= A), the maximum over all moves must be at least A (actually >= A) and the minimum must be at most A. But crucially, the maximum among all moves is the maximum of the "high" sides across variables, and the minimum is the minimum of the "low" sides across variables. However, note that for each i, the high side (the larger of the two) is >= A, and the low side is <= A. So we have:
Let H_i = max(E_i0, E_i1) and L_i = min(E_i0, E_i1). Then H_i + L_i = 2A.
Now consider overall M = max_{i} H_i (since the max over all moves is the max of the high sides, because low sides are ≤ A). Actually the max could also be from a low side if that low side > A? But low side ≤ A by definition, so high side is ≥ A. So the maximum overall must be among the high sides. Similarly, the minimum overall must be among the low sides. So M = max_i H_i, m = min_i L_i.
We need to check if (M + m)/2 = A. That would require M + m = 2A. Since for each i, H_i + L_i = 2A. If we take the maximum H_i and the minimum L_i, it is not necessarily that H_max + L_min = 2A. In fact, H_max could be larger than some H_i, while L_min could be smaller than its corresponding L_i. For example, suppose variable 1 has (H1=10, L1= -6) sum=4 => A=2. Variable 2 has (H2=5, L2= -1) sum=4 => A=2. Then M = max(H1,H2)=10, m = min(L1,L2) = -6, sum=4, 2A=4, works? Actually 10 + (-6)=4 => 2A=4. That seems to work because both pairs sum to 2A, so H1+L1=2A and H2+L2=2A. H_max + L_min =? Could be different? Let's try: suppose H1=10, L1= -6 (sum 4), H2=9, L2= -5 (sum 4). Then M=10, m=-6, sum=4, still 2A=4. But can we have H_max from variable 1 and L_min from variable 2, and still get sum=2A? Since both pairs sum to same constant 2A, we have H1+L1=2A, H2+L2=2A. Then H_max + L_min =? If H_max = H1 and L_min = L2, then H1+L2 = (2A - L1) + L2 = 2A + (L2 - L1). Since L2 may be greater than L1, this sum could be > 2A. But careful: If L_min = L2, then L2 is the minimum among all L_i. So L2 ≤ L1. So L2 - L1 ≤ 0. So H1+L2 ≤ 2A. Similarly if H_max = H1 and L_min = L1, sum=2A. Since L_min is the smallest L_i, and L2 ≤ L1, then H1+L2 ≤ H1+L1 = 2A. Actually if L2 is smaller, then H1+L2 is less than H1+L1 = 2A? Because L2 ≤ L1 => H1+L2 ≤ H1+L1 = 2A. So H1+L2 could be strictly less than 2A. Wait we need to check: If H_max = H1, L_min = L2 and L2 < L1, then H1+L2 < H1+L1 = 2A. So sum could be less than 2A. That would cause (M+m)/2 < A. So is it possible that the overall max and min are from different variables such that the sum is not 2A? Let's attempt to construct an example where H1 is large, L2 is very low, but H2 and L1 are moderate. However we must maintain that for each i, H_i+L_i=2A, and A is the overall average fixed. So if we try to make H1 > H2, then L1 = 2A - H1, L2 = 2A - H2. Since H1 > H2 implies L1 < L2. So L1 is lower than L2. Thus the smallest L_i would be L1 (since it's associated with the largest H_i). Therefore the min L is always paired with the max H (they come from the same variable). Because as H_i increases, its partner L_i decreases. So the variable with the maximum H_i also has the minimum L_i. Indeed, given that all pairs sum to the same constant, the ordering of H_i is opposite to ordering of L_i. Precisely: For any i,j, H_i > H_j implies L_i = 2A - H_i < 2A - H_j = L_j. So H_i > H_j ⇔ L_i < L_j. Therefore the maximum H corresponds to the minimum L. So M = H_{i*} where i* maximizes H_i, then L_{i*} = min_i L_i. Thus M and m are actually from the same variable! This is a key observation. So the overall max among all moves (i,b) is the larger conditional expectation for some variable i*, and the overall min is the smaller conditional expectation for the same variable i*. Because for any other variable j, its high side H_j ≤ H_{i*} and its low side L_j ≥ L_{i*}. So indeed M = H_{i*}, m = L_{i*}. And since H_{i*} + L_{i*} = 2A, we have M+m = 2A, and thus (M+m)/2 = A.
Thus the recursion holds for the empty state: V(empty) = (M+m)/2 = A. And by induction, it should hold for all states: For any partial assignment S, if we define V(S) as the average over completions (i.e., expectation under uniform random assignment of remaining variables), then it satisfies the recursion. Let's verify for general S: In state S, we have some fixed variables. The remaining variables set U. The overall average over completions is A_S = (1/2^{|U|}) sum_{assignments of U} f(S fixed, rest). Now consider the conditional expectations when fixing an additional variable i in U. For each i in U, define V_i^0 = average over completions with x_i=0, etc. Then A_S = (V_i^0 + V_i^1)/2 for any i (since overall average is average of conditional averages). Also for any i, the two values V_i^0 and V_i^1 sum to 2 A_S, because each full completion contributes to exactly one of them. And as before, the max over all moves (i,b) is max_i H_i (where H_i = max(V_i^0, V_i^1)), and min over all moves is min_i L_i (L_i = min(V_i^0, V_i^1)). And because H_i + L_i = 2 A_S for each i, and H_i ordering is opposite to L_i, we again have M = max_i H_i and m = min_i L_i from the same variable (the one with the largest H_i, which also has smallest L_i). So (M+m)/2 = A_S. Thus V(S) = A_S satisfies the recursion.
Thus we have proven that the value of the game from any state is exactly the average of f over all completions of that state (i.e., the expected value if the remaining bits are set uniformly at random). This is a neat result.
Therefore, the initial expected game value (from empty state) is simply the arithmetic mean of all 2^n values of f.
So the problem reduces to: Given an array c of size N=2^n, we need to output its average (as a floating point number). Then we have r updates, each updates one entry c[z] to g, and after each update we need to output the new average of the array.
That seems trivial! But wait, is that always correct? Let's double-check the game description: "Each round, with equal probability, one of Allen or Bessie gets to make a move." The randomness is per round, not predetermined. But we assumed that from any state, the value is the average over completions. We proved that under the recursion, which we derived from the game's rules assuming optimal play. But is that recursion indeed the correct value? Let's reexamine the game: At each round, with equal probability, Allen or Bessie is chosen to move. They both know f and play to maximize/minimize the expected final value, assuming optimal play from both. The recursion we wrote: V(S) = 0.5 * max_{move} V(S after move) + 0.5 * min_{move} V(S after move). This assumes that at state S, with probability 1/2, Allen moves and chooses the move that maximizes the subsequent value, and with probability 1/2, Bessie moves and chooses the move that minimizes. Is that correct? It seems natural, but we need to be careful: The players are rational and they know that future moves will also be subject to random player selection, and they will act optimally. So the value function V(S) should satisfy the Bellman equation for this stochastic game. In zero-sum games with perfect information and chance moves, the value satisfies: V(S) = E_{player} [ best_action_for_that_player ( V(S') ) ]. Since the player choice is chance, we take expectation: V(S) = (1/2) * max_{a in A} V(S after a) + (1/2) * min_{a in A} V(S after a). This is standard. So it's correct.
Now we showed that the solution to this recursion, with terminal condition V(full)=f(x), is the average over completions. So indeed the game value is the average.
But is there any subtlety about the order of moves? Could a player choose to set a variable to 0 or 1, but maybe they could also choose which variable? Yes, that's included in the moves. The recursion includes max/min over all such choices.
Thus the solution is trivial: compute average of all 2^n numbers, after each update recalc average = (sum + (g - old)) / N, and output as double.
But wait, examples match. The problem constraints: n up to 18, r up to 2^18, and c_i up to 1e9. So sum can be up to 2^18 * 1e9 ≈ 2.62e14, fits in 64-bit. Double output. So we can do O(1) per update.
But is there any trick? Let's read problem statement again: "They will play r+1 times though, so between each game, exactly one value of f changes. In other words, between rounds i and i+1 for 1 ≤ i ≤ r, f(z_1, ..., z_n) → g_i for some (z_1, ..., z_n) ∈ {0, 1}^n." So after each change, they play again? We need expected value for each version of f. So yes, just average.
But wait: The problem might be more interesting? Could there be a misinterpretation: The game is played r+1 times, but after each game, f changes exactly one value. That means the sequence of f values changes, and we need expected game value at each stage. Our simple solution says it's just the average. Could that be the intended solution? Given the constraints and examples, it's plausible that the problem is trivial after realizing the value is average, but maybe there is a twist: The recursion we derived assumed that at each step, the player who moves can pick any unset variable and set it to 0 or 1. But is it allowed that they can set it to either 0 or 1? Yes. And the value function we derived matches examples. So indeed the answer is average.
But wait: In our proof, we used the property that for any i, the two conditional expectations sum to 2A_S. That is true because the sum of f over all completions with x_i=0 plus those with x_i=1 equals total sum over all completions. However, in state S, some variables are already fixed. The remaining variables are U. When we condition on a particular variable i in U, we fix its value. Then the total sum over completions where x_i=0 plus where x_i=1 is indeed the total sum over all completions. So the property holds. And then we argued that max and min among the set of conditional expectations (over all i,b) come from the same variable because of opposite ordering. This holds as long as for each i, the two values sum to constant (2A_S). But is that constant the same for all i? Yes, because each sum is the total sum over completions (which is independent of i). So indeed H_i + L_i = 2A_S for all i. And as argued, the ordering of H_i is opposite to L_i. Therefore the max H and min L belong to same i. So (M+m)/2 = A_S.
Thus the recursion holds for any partial assignment. So V(empty) = average over full assignments.
Therefore the problem is trivial.
But before finalizing, we should consider if there is any nuance about the players' strategies: Could there be a more complex equilibrium where a player randomizes? But in zero-sum games with perfect information and deterministic moves (players choose pure actions), the value is determined by the minimax theorem; there is no need for mixed strategies because the game is deterministic given actions. However, with chance moves, the value is still defined, and optimal strategies might be pure (since it's a finite game with perfect recall, but sometimes mixing can be beneficial? In deterministic zero-sum games with alternating moves, pure strategies suffice because it's a minimax on a tree. Here chance moves randomize which player moves, but given a player's turn, they can choose a deterministic action. There's no benefit to randomizing because the opponent's future actions are deterministic given the state and their objective. But could there be a scenario where the player is indifferent, but that's fine. So pure strategies suffice, and the value is as computed.
Thus the solution is simply to output average.
Given the input constraints, the solution is easy. But wait, the problem statement says: "Your goal is to help Allen and Bessie find the expected game value!" That suggests we compute the expected value of the game under optimal play. That is exactly what we derived. And examples match average.
But maybe there's a twist: The players move sequentially, but the order of moves is random. However, we assumed that each move is equally likely to be Allen or Bessie. But is that the correct interpretation? "Each round, with equal probability, one of Allen or Bessie gets to make a move." That could mean that in each round, one player is chosen uniformly at random to make a move. So yes.
Could it be that the round order is predetermined (like first round Allen, second Bessie, etc.)? No, says equal probability each round, so random.
Thus our reasoning holds.
But there's also possibility that the players can see who is to move when they move. They act accordingly. So recursion is correct.
Therefore the problem reduces to computing average after updates. That's too trivial for a problem from an contest? Possibly it's a trick problem. However, constraints: n up to 18, r up to 2^18, and output with error tolerance. That matches just updating sum.
But maybe there is something else: The function f takes n binary arguments and returns a real. The initial values are given as integers, but could be up to 1e9. The expected value might be rational. We need to print as floating point with relative/absolute error. So we can compute as double.
Thus algorithm: read n, r. Compute N = 1 << n. Read array c of size N. Compute sum = sum(c). Output sum / N as double (with maybe 6 decimal places). Then for each update: read z, g; update sum = sum - old_c[z] + g; set c[z] = g; output new sum / N.
That's it.
But wait: Example output shows three lines for r=2. That matches.
Double-check third example: n=2, all ones, sum=4, average=1, output 1.000000. Good.
So solution seems straightforward.
Before final answer, I want to ensure there is no misinterpretation about the bit ordering and indexing that could affect average? Average is over all 2^n values regardless of ordering, so it's fine.
Edge cases: n=0? Possibly n≥1 per constraints (1 ≤ n). So N≥2.
r can be 0, then we just output initial average.
Precision: Use double. Sum can be up to 2^18 * 1e9 = about 2.62e14, which fits in double with integer precision (double has 53 bits mantissa, ~9e15 integer exact). So average will be represented precisely as double? Actually dividing might yield non-integer; but as double it's fine. Printing with e.g., printf("%.6lf\n", average) should be ok, but we need to output with enough digits. The required tolerance is 1e-6 relative/absolute, so printing 6 decimal places is sufficient? Not exactly: If the answer is large (like 1e9), 6 decimal places might not give relative error 1e-6 if we print only 6 digits after decimal? For large numbers, 1e-6 relative means we need about 6 significant figures after the decimal? Actually if answer is 1e9, absolute error 1e-6 relative means error up to 1000? Wait relative error 1e-6 means |a-b|/max(1,|b|) ≤ 1e-6. So for b=1e9, allowed absolute error is 1000? Actually 1e-6 * 1e9 = 1000. So that's huge. So printing with 6 decimal places would give error at most 0.0000005, which is much smaller. So it's fine. But to be safe, we can use cout with fixed and setprecision(10) or something. But typical double prints up to 15 digits. We'll output with e.g., printf("%.10f\n", avg) or just use default double output with enough precision.
But let's ensure that the average might not be integer; we can output with 6 decimals as examples.
But there is a nuance: The output for first example: 1.500000, 2.250000, 3.250000. So they printed 6 decimals. So we can do same.
Thus the solution is trivial.
Wait, but is there any scenario where the average is not the correct expected value? Let's test with n=2 with a more complex f to see if any counterexample emerges. We already proved it mathematically. So it's solid.
Thus answer: For each f, expected game value = (1/2^n) * sum_{x∈{0,1}^n} f(x).
Now we need to produce code.
Implementation details:
- Read n, r.
- N = 1 << n.
- Read c array of size N.
- Compute sum = accumulate c.
- Print sum / N as double (use casting to double).
- For each update:
- read z, g.
- diff = g - c[z]; sum += diff; c[z] = g.
- print new average = (double)sum / N.
Complexities: O(2^n + r) time, O(2^n) memory. 2^n up to 262144, fine.
Potential pitfalls: Input uses 0-indexed indexing as described. The updates give z between 0 and 2^n-1, which corresponds to a specific binary pattern. We just update that index.
Make sure to use long long for sum because up to ~2.62e14 fits in 64-bit (2^18 * 1e9 = 262144 * 1e9 = 2.62144e14 < 2^63 ~9.22e18). So long long is safe.
Double conversion: (double)sum / N. Use printf("%.6f\n", avg) or cout with setprecision.
Edge: r can be up to 2^18, but reading r lines fine.
Thus solution.
But wait, the problem statement: "They will play r+1 times though, so between each game, exactly one value of f changes." Does that mean we need to output expected value for each game, i.e., after each change. So initial game before any changes, then after each change. So r+1 outputs. That's what we do.
Now is there any chance that the game value is not simply average because the players might have strategies that affect the distribution of final assignments beyond uniform? In our analysis, we derived that the optimal strategies result in expected value equal to the uniform average. But is it always optimal for both players to play such that the distribution of final assignments is uniform? Let's simulate the game: At each step, if it's Allen's turn, he chooses a move that maximizes the expected final value. According to our value function, that corresponds to picking an i,b such that V(S∪{i=b}) is maximal. Given V(S) = average, the maximum among V_i^b is achieved by choosing the variable with the highest conditional expectation for the appropriate bit. Similarly for Bessie, she chooses the minimum. Under those strategies, does the resulting distribution over final assignments become uniform? Possibly not, but the expected value is indeed the average because the recursion ensures that from the initial state, the value equals the average. So even if the distribution is not uniform, the expectation is the uniform average. This is a bit surprising but due to the adversarial nature and randomness.
We should also check that the value is indeed the uniform average even if we consider that players may randomize? But we already established via recursion.
Thus final answer is trivial.
Nevertheless, I'll double-check with a random small n=3 using manual computation. Let's pick arbitrary numbers: f for 3 bits (x0,x1,x2). Suppose f = [0,0,0,100,0,0,0,0] where the indexing? Let's define mapping: For simplicity, treat the index as binary of (x2,x1,x0) maybe? But average will be sum/N. Let's compute average: if only one entry is 100, average = 100/8 = 12.5. According to our claim, expected game value = 12.5.
Now let's try to compute using recursion to see if it matches. We'll need to compute V for all states but we can try to compute V(empty) manually using the property that it's average. But to test the claim, we can compute V(empty) by recursion manually perhaps with a programmatic mental? Might be tedious but we can try to see if any inconsistency.
We'll try a simpler approach: Since we proved it mathematically, it's solid.
But there could be a hidden twist: The move consists of picking an i such that x_i = -1 and either setting x_i → 0 or x_i → 1. Does the player have to choose exactly one variable and set it to either 0 or 1? Yes. So our recursion covers that.
Thus the problem is solved.
But before final, let's read the problem again: "They both know a function f: {0, 1}^n → R, i. e. the function takes n binary arguments and returns a real value. At the start of the game, the variables x_1, x_2, ..., x_n are all set to -1. Each round, with equal probability, one of Allen or Bessie gets to make a move. A move consists of picking an i such that x_i = -1 and either setting x_i → 0 or x_i → 1.
After n rounds all variables are set, and the game value resolves to f(x_1, x_2, ..., x_n). Allen wants to maximize the game value, and Bessie wants to minimize it."
One might question: The order of variable indices (x_1,...,x_n) vs earlier we used x_0,...,x_{n-1}. That's just naming.
Everything consistent.
Thus the answer: print the average.
But wait, there is an important nuance: The players might have the ability to skip? No.
Thus I'm confident.
Now I will produce the final answer with code.
Potential pitfalls: Input reading: after n and r, the next line contains 2^n integers. That could be many, need to read carefully. Use vector c(N). Then read r updates.
Double output: For each, we can compute double avg = (double) sum / N. Use printf("%.6lf\n", avg) to match example.
Alternatively, use cout << fixed << setprecision(6) << avg << endl.
Complexity: O(N + r) time, O(N) memory.
But note: r can be up to 2^18, and N = 2^n, also up to 2^18. So total input size up to about 262k numbers for c plus 2*262k for updates, about 800k numbers, fine.
So we can implement.
But maybe there's one more nuance: The problem might be that the initial values c_i are given in order c_0,...,c_{2^n-1} corresponding to binary representation of x = x_{n-1}...x_0. And updates also give z with that representation. That's fine.
Now I'm thinking: Could there be a twist that the players don't know who will move in future rounds? But they know the rule, so they can compute expectations.
All good.
Thus final solution is trivial.
Given that this is from Codeforces? Possibly problem "Game with Strings" or something? But anyway.
Thus answer: compute average.
Let's produce the final solution in Python or C++? The user may expect code. Usually in these analysis we output reasoning, but final answer includes code. Since the problem statement is typical of programming contest, we should provide a solution in C++.
I'll write a C++ solution:
#include <bits/stdc++.h> using namespace std;
int main() { int n, r; cin >> n >> r; int N = 1 << n; vector c(N); long long sum = 0; for (int i = 0; i < N; ++i) { cin >> c[i]; sum += c[i]; } double invN = 1.0 / N; cout << fixed << setprecision(6); cout << sum * invN << '\n'; for (int i = 0; i < r; ++i) { int z; long long g; cin >> z >> g; sum += g - c[z]; c[z] = g; cout << sum * invN << '\n'; } return 0; }
That should work.
But note: invN = 1.0/N is double. Multiply sum by invN.
Precision: sum is long long up to 2.62e14; multiplying by 1.0/N yields double. double has about 15-16 decimal digits precision, enough.
Now double-check examples.
Example1: n=2, N=4, c = [0,1,2,3], sum=6, avg=1.5, prints 1.500000. Update1: z=2, g=5 -> old c[2]=2, diff=3, sum=9, avg=2.25, prints 2.250000. Update2: z=0,g=4 -> diff=4-0=4, sum=13, avg=3.25, prints 3.250000. OK.
Example2: n=1,N=2,c=[2,3],sum=5,avg=2.5, prints 2.500000. r=0, no updates.
Example3: n=2,N=4,c=[1,1,1,1],sum=4,avg=1.0.
Thus correct.
But wait, second example mapping: n=1, c0 corresponds to f(0)? Since binary of x (with n-1...x0) and n=1, so x = x0. So c0 = f(0)=2, c1=f(1)=3. average=2.5.
All consistent.
Thus final answer.
But let's consider if there could be any more subtlety: The game is symmetric in players, but is it possible that the optimal strategy leads to a value different from the average if the players use mixed strategies? In zero-sum games, the value is unique; if there exists a value solving the recursion, that's the game value. Our recursion yields a candidate value. We need to check that the value function defined by the recursion indeed satisfies that both players have strategies achieving that value. The standard approach: Define V(S) as the solution to the recursion. Then for the player who moves, they can choose actions achieving the appropriate extremum. This gives optimal strategies. So V is the game value.
Thus indeed.
Now finalize.
But note: In the recursion we used the max and min over all moves. However, there is a subtle point: At a given state, the set of moves includes both choosing a variable and setting its value. The max over all such moves might be achieved by choosing a variable i and a bit value b. But is it always true that for a fixed i, the max over b of V(S∪{i=b}) is H_i, and the min is L_i. Then we take overall max and min across all i. But in the recursion, it's (1/2) * max_{i,b} V + (1/2) * min_{i,b} V. Our derivation used that the max and min are from the same i, giving (H_i + L_i)/2 = A_S. But we should also consider that the max and min could be from the same i but different b, which is what we used. If they are from different i, we argued it's impossible due to opposite ordering. Let's re-express that argument: For any i and j, we have H_i ≥ H_j iff L_i ≤ L_j. Therefore, the i that gives maximum H also gives minimum L. Hence the overall max among all pairs (i,b) is H_{i*}, and overall min is L_{i*}. So they are from the same i. Thus the recursion yields (H_{i*} + L_{i*})/2 = A_S.
But is it possible that there are ties? If multiple i share the same H_i, then the min might be from a different i if L_i are also equal? For ties, it could be that H_i = H_j and L_i = L_j (since they sum to constant, equality of H implies equality of L). So any i with max H also has min L (same value). So still (M+m)/2 = A_S.
Thus consistent.
Therefore the solution is solid.
Thus we will produce final answer with explanation and code.
But wait, there is a nuance: The initial state is all x_i = -1. After each move, the variable is set to 0 or 1. After n rounds, all set. The players are rational and have opposite goals. The value we computed is the expected value under optimal play, assuming that at each round a player is chosen uniformly at random. This is known as "random-turn games" and it's known that the value equals the expected value under random play (i.e., each player moves with probability 1/2 each turn) for certain classes of games, including "positional games"? Actually there is a known result: In random-turn Maker-Breaker games, the value is the expected value under random play if the payoff function is linear? Hmm. But anyway.
Given the simplicity, I'm convinced.
Now implement.
Potential edge: n up to 18, N = 2^18 = 262144. Memory for vector of long long is fine.
I will provide the solution in C++ and maybe also Python for completeness, but typical answer expects C++.
Thus final. ```cpp
#include <bits/stdc++.h> using namespace std;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int n, r; cin >> n >> r; int N = 1 << n; vector<long long> c(N); long long sum = 0; for (int i = 0; i < N; ++i) { cin >> c[i]; sum += c[i]; } double invN = 1.0 / N; cout << fixed << setprecision(6); cout << sum * invN << '\n'; for (int i = 0; i < r; ++i) { int z; long long g; cin >> z >> g; sum += g - c[z]; c[z] = g; cout << sum * invN << '\n'; } return 0;}