Google Code Jam 2022, 1A, Equal Sum

equal_sum.py

#!/usr/bin/env python3

import random

UPPER_BOUND = 10**9
BINARY_BOUND = len(f'{UPPER_BOUND:b}')


def is_binary(x):
    return x == 2**len(f'{x:b}')


def make_binaries():
    return [2**i for i in range(BINARY_BOUND)]


def make_unique_random_evens(n):
    xs = [2*(x+1) for x in random.sample(range(UPPER_BOUND//2), n)]
    return [x for x in xs if not is_binary(x)][:n-BINARY_BOUND]


def strategic_picking(xs, diff=0):
    picks = []
    for x in xs:
        if diff < 0:
            diff += x
        else:
            diff -= x
            picks += [x]
    return diff, picks


def balance_with_binaries(odd_diff):
    assert odd_diff % 2 == 1
    _, picks = strategic_picking(reversed(make_binaries()), odd_diff)
    return picks


def ask(n):
    assert BINARY_BOUND <= n
    xs = make_unique_random_evens(n)
    print(' '.join(map(str, make_binaries() + xs)))
    return xs


def listen():
    return [int(x) for x in input().split()]


def answer(xs):
    diff, picks = strategic_picking(sorted(xs))
    print(' '.join(map(str, picks + balance_with_binaries(diff))))


for _ in range(int(input())):
    n = int(input())
    xs = ask(n)
    xs += listen()
    answer(xs)