Alice and the Cake (Codeforces 1652C)
Tags: Greedy, data structures

Alice has a cake, and she is going to cut it. She will perform the following operation $$$n-1$$$ times: choose a piece of the cake (initially, the cake is all one piece) with weight $$$w\ge 2$$$ and cut it into two smaller pieces of weight $$$\lfloor\frac{w}{2}\rfloor$$$ and $$$\lceil\frac{w}{2}\rceil$$$ ($$$\lfloor x \rfloor$$$ and $$$\lceil x \rceil$$$ denote floor and ceiling functions, respectively).After cutting the cake in $$$n$$$ pieces, she will line up these $$$n$$$ pieces on a table in an arbitrary order. Let $$$a_i$$$ be the weight of the $$$i$$$-th piece in the line.You are given the array $$$a$$$. Determine whether there exists an initial weight and sequence of operations which results in $$$a$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print a single line: print YES if the array $$$a$$$ could have resulted from Alice's operations, otherwise print NO.You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

Note: In the first test case, it's possible to get the array $$$a$$$ by performing $$$0$$$ operations on a cake with weight $$$327$$$.In the second test case, it's not possible to get the array $$$a$$$.In the third test case, it's possible to get the array $$$a$$$ by performing $$$1$$$ operation on a cake with weight $$$1\,970\,429\,473$$$:   Cut it in half, so that the weights are $$$[985\,214\,736, 985\,214\,737]$$$.  Note that the starting weight can be greater than $$$10^9$$$.In the fourth test case, it's possible to get the array $$$a$$$ by performing $$$2$$$ operations on a cake with weight $$$6$$$:  Cut it in half, so that the weights are $$$[3,3]$$$.  Cut one of the two pieces with weight $$$3$$$, so that the new weights are $$$[1, 2, 3]$$$ which is equivalent to $$$[2, 3, 1]$$$ up to reordering.

Sample Inputs:
14
1
327
2
869 541
2
985214736 985214737
3
2 3 1
3
2 3 3
6
1 1 1 1 1 1
6
100 100 100 100 100 100
8
100 100 100 100 100 100 100 100
8
2 16 1 8 64 1 4 32
10
1 2 4 7 1 1 1 1 7 2
10
7 1 1 1 3 1 3 3 2 3
10
1 4 4 1 1 1 3 3 3 1
10
2 3 2 2 1 2 2 2 2 2
4
999999999 999999999 999999999 999999999

Sample Outputs:
YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
YES

Solution (Python):
from math import ceil
''
t = int(input())
for _ in range(t):
    n = int(input())
    a = set()
    d = {}
    s = 0
    for el in list(map(int, input().split())):
        a.add(el)
        d.setdefault(el, 0)
        d[el] += 1
        s += el
    p = [s]
    while a and p:
        el = p.pop()
        if el in a and d[el] > 0:
            d[el] -= 1
        elif el == 1:
            break
        else:
            p.append(el // 2)
            p.append(ceil(el / 2))
    s1 = 0
    for (k, v) in d.items():
        s1 += v
    if not s1 and (not p):
        print('YES')
    else:
        print('NO')

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    g = {}
    sum = 0
    for x in l:
        sum += x
        g[x] = g.get(x, 0) + 1
    if n == 1:
        print('YES')
    else:
        gg = {}
        gg[sum] = 1
        while len(gg.keys()) != 0:
            x = max(gg.keys())
            if x == 1:
                if g.get(1, 0) == gg[x]:
                    del g[x]
                    del gg[x]
                else:
                    break
            elif x in g.keys():
                if g[x] > gg[x]:
                    break
                elif g[x] == gg[x]:
                    del g[x]
                    del gg[x]
                else:
                    gg[x // 2] = gg.get(x // 2, 0) + gg[x] - g[x]
                    gg[(x + 1) // 2] = gg.get((x + 1) // 2, 0) + gg[x] - g[x]
                    del g[x]
                    del gg[x]
            else:
                gg[x // 2] = gg.get(x // 2, 0) + gg[x]
                gg[(x + 1) // 2] = gg.get((x + 1) // 2, 0) + gg[x]
                del gg[x]
        if max(len(gg.keys()), len(g.keys())) == 0:
            print('YES')
        else:
            print('NO')

Solution (Python):
import sys
from collections import deque
for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    mas = list(map(int, sys.stdin.readline().split()))
    s = sum(mas)
    d = dict()
    for i in mas:
        if i not in d:
            d[i] = 0
        d[i] += 1
    t = deque()
    t.append(s)
    for i in range(n - 1):
        k = t.popleft()
        for j in range(2):
            a = (k + j) // 2
            if a in d:
                if d[a] > 0:
                    d[a] -= 1
                else:
                    t.append(a)
            else:
                t.append(a)
    otv = True
    for i in d:
        if d[i] != 0:
            otv = False
    if otv or n == 1:
        print('yes')
    else:
        print('no')