Binary Median (Codeforces 1360H)
Tags: Others, bitmasks

Consider all binary strings of length $$$m$$$ ($$$1 \le m \le 60$$$). A binary string is a string that consists of the characters 0 and 1 only. For example, 0110 is a binary string, and 012aba is not. Obviously, there are exactly $$$2^m$$$ such strings in total.The string $$$s$$$ is lexicographically smaller than the string $$$t$$$ (both have the same length $$$m$$$) if in the first position $$$i$$$ from the left in which they differ, we have $$$s[i] < t[i]$$$. This is exactly the way strings are compared in dictionaries and in most modern programming languages when comparing them in a standard way. For example, the string 01011 is lexicographically smaller than the string 01100, because the first two characters are the same, and the third character in the first string is less than that in the second.We remove from this set $$$n$$$ ($$$1 \le n \le \min(2^m-1, 100)$$$) distinct binary strings $$$a_1, a_2, \ldots, a_n$$$, each of length $$$m$$$. Thus, the set will have $$$k=2^m-n$$$ strings. Sort all strings of the resulting set in lexicographical ascending order (as in the dictionary).We number all the strings after sorting from $$$0$$$ to $$$k-1$$$. Print the string whose index is $$$\lfloor \frac{k-1}{2} \rfloor$$$ (such an element is called median), where $$$\lfloor x \rfloor$$$ is the rounding of the number down to the nearest integer.For example, if $$$n=3$$$, $$$m=3$$$ and $$$a=[$$$010, 111, 001$$$]$$$, then after removing the strings $$$a_i$$$ and sorting, the result will take the form: $$$[$$$000, 011, 100, 101, 110$$$]$$$. Thus, the desired median is 100.

Input: The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then, $$$t$$$ test cases follow.The first line of each test case contains integers $$$n$$$ ($$$1 \le n \le \min(2^m-1, 100)$$$) and $$$m$$$ ($$$1 \le m \le 60$$$), where $$$n$$$ is the number of strings to remove, and $$$m$$$ is the length of binary strings. The next $$$n$$$ lines contain $$$a_1, a_2, \ldots, a_n$$$ — distinct binary strings of length $$$m$$$.The total length of all given binary strings in all test cases in one test does not exceed $$$10^5$$$.

Output: Print $$$t$$$ answers to the test cases. For each test case, print a string of length $$$m$$$ — the median of the sorted sequence of remaining strings in the corresponding test case.

Note: The first test case is explained in the statement.In the second test case, the result after removing strings and sorting is $$$[$$$001, 010, 101, 110$$$]$$$. Therefore, the desired median is 010.

Sample Inputs:
5
3 3
010
001
111
4 3
000
111
100
011
1 1
1
1 1
0
3 2
00
01
10

Sample Outputs:
100
010
0
1
11

Solution (Python):
for _ in range(int(input())):
    (a, b) = map(int, input().split())
    t = (2 ** b - 1 - a) // 2
    A = []
    for _ in range(a):
        A += [int(input(), 2)]
    for i in sorted(A):
        if i > t:
            break
        t += 1
    k = bin(t)
    print('0' * (b - len(k) + 2) + k[2:])

Solution (Python):
import itertools
import heapq
import collections
import math
import sys
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def inis():
    return input().split()

def SieveOfEratosthenes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    l = []
    while p * p <= n:
        if prime[p] == True:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1
    for p in range(2, n + 1):
        if prime[p]:
            l.append(p)
    return l

def isPrime(n):
    prime_flag = 0
    if n > 1:
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                prime_flag = 1
                break
        if prime_flag == 0:
            return True
        else:
            return False
    else:
        return False

def gcd(a):
    x = 0
    for p in a:
        x = math.gcd(x, p)
    return x
import math

def printDivisors(n):
    i = 1
    ans = []
    while i <= math.sqrt(n):
        if n % i == 0:
            if n / i == i:
                ans.append(i)
            else:
                ans.append(i)
                ans.append(n // i)
        i = i + 1
    ans.sort()
    return ans

def binaryToDecimal(n):
    return int(n, 2)
for _ in range(inp()):
    (n, m) = invr()
    a = []
    for i in range(n):
        k = input()
        a.append(binaryToDecimal(k))
    a.sort()
    ans = (2 ** m - 1 - n) // 2
    for i in a:
        if i <= ans:
            ans += 1
    res = bin(ans).replace('0b', '')
    print('0' * (m - len(res)) + res)

Solution (Python):
import sys
caseNumber = int(sys.stdin.readline())
cases = []
for i in range(caseNumber):
    cases.append([])
    (removed, power) = list(map(int, sys.stdin.readline().split()))
    cases[-1].append(power)
    for j in range(removed):
        cases[-1].append(sys.stdin.readline().strip())
for case in cases:
    power = case[0]
    case.pop(0)
    converted = []
    for number in case:
        n = 0
        for i in range(power):
            n += int(number[i]) * 2 ** (power - i - 1)
        converted.append(n)
    converted.sort()
    middle = (2 ** power - 1) // 2
    counter = 1
    if len(converted) == 1:
        if converted[0] > middle:
            difference = -1
        else:
            difference = 1
    elif converted[0] >= middle:
        difference = -len(converted)
    elif converted[-1] < middle:
        difference = len(converted)
    else:
        while counter < len(converted):
            if converted[counter] == middle:
                difference = counter * 2 - len(converted) + 2
                if difference > 0:
                    counter += 1
                break
            elif converted[counter - 1] < middle and converted[counter] > middle:
                difference = (counter - 1) * 2 - len(converted) + 2
                if difference <= 0:
                    counter -= 1
                break
            counter += 1
        if difference <= 0:
            while difference % 2 + difference // 2 + middle <= converted[counter]:
                difference -= 2
                counter -= 1
                if counter == -1:
                    break
        elif counter != len(converted):
            while difference % 2 + difference // 2 + middle >= converted[counter]:
                difference += 2
                counter += 1
                if counter == len(converted):
                    break
    number = difference % 2 + difference // 2 + middle
    binaryNumber = ''
    while number != 0:
        binaryNumber += str(number % 2)
        number = number // 2
    print((power - len(binaryNumber)) * '0' + binaryNumber[::-1])