Game (Codeforces 995D)
Tags: Math, math

Allen and Bessie are playing a simple number game. They both know a function $$$f: \{0, 1\}^n \to \mathbb{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, \dots, 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 \to 0$$$ or $$$x_i \to 1$$$.After $$$n$$$ rounds all variables are set, and the game value resolves to $$$f(x_1, x_2, \dots, 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 \le i \le r$$$, $$$f(z_1, \dots, z_n) \to g_i$$$ for some $$$(z_1, \dots, z_n) \in \{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 \le n \le 18$$$, $$$0 \le r \le 2^{18}$$$).The next line contains $$$2^n$$$ integers $$$c_0, c_1, \dots, c_{2^n-1}$$$ ($$$0 \le c_i \le 10^9$$$), denoting the initial values of $$$f$$$. More specifically, $$$f(x_0, x_1, \dots, x_{n-1}) = c_x$$$, if $$$x = \overline{x_{n-1} \ldots x_0}$$$ in binary.Each of the next $$$r$$$ lines contains two integers $$$z$$$ and $$$g$$$ ($$$0 \le z \le 2^n - 1$$$, $$$0 \le g \le 10^9$$$). If $$$z = \overline{z_{n-1} \dots z_0}$$$ in binary, then this means to set $$$f(z_0, \dots, z_{n-1}) \to 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|)}} \le 10^{-6}$$$.

Note: Consider the second test case. If Allen goes first, he will set $$$x_1 \to 1$$$, so the final value will be $$$3$$$. If Bessie goes first, then she will set $$$x_1 \to 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.

Sample Inputs:
2 2
0 1 2 3
2 5
0 4

1 0
2 3

2 0
1 1 1 1

Sample Outputs:
1.500000
2.250000
3.250000

2.500000

1.000000

Solution (Python):
from sys import stdin
from math import fsum

def main():
    (n, m) = map(int, input().split())
    ff = list(map(float, input().split()))
    (scale, r) = (0.5 ** n, fsum(ff))
    res = [r * scale]
    for (si, sf) in map(str.split, stdin.read().splitlines()):
        (i, f) = (int(si), float(sf))
        r += f - ff[i]
        ff[i] = f
        res.append(r * scale)
    print('\n'.join(map(str, res)))
if __name__ == '__main__':
    main()

Solution (Python):
(n, r) = [int(x) for x in input().split()]
n = 2 ** n
xs = [int(x) for x in input().split()]
s = sum(xs)
res = [0 for _ in range(r + 1)]
for i in range(r):
    res[i] = s / n
    (i, val) = [int(x) for x in input().split()]
    s += val - xs[i]
    xs[i] = val
res[r] = s / n
print('\n'.join(map(str, res)))

Solution (Python):
(n, r) = [int(x) for x in input().split()]
n = 2 ** n
xs = [int(x) for x in input().split()]
s = sum(xs)
res = [0 for _ in range(r + 1)]
for i in range(r):
    res[i] = s / n
    (i, val) = [int(x) for x in input().split()]
    s += val - xs[i]
    xs[i] = val
res[r] = s / n
print('\n'.join(map(str, res)))