Problem:


Problem H: Twenty Questions

Consider a closed world and a set of features that are defined for all the objects in the world.
Each feature can be answered with "yes" or "no". Using those features, we can identify any
object from the rest of the objects in the world. In other words, each object can be represented
as a fixed-length sequence of booleans. Any object is different from other objects by at least
one feature.

You would like to identify an object from others. For this purpose, you can ask a series of
questions to someone who knows what the object is. Every question you can ask is about one
of the features. He/she immediately answers each question with "yes" or "no" correctly. You
can choose the next question after you get the answer to the previous question.

You kindly pay the answerer 100 yen as a tip for each question. Because you don' t have surplus
money, it is necessary to minimize the number of questions in the worst case. You don’t know
what is the correct answer, but fortunately know all the objects in the world. Therefore, you
can plan an optimal strategy before you start questioning.

The problem you have to solve is: given a set of boolean-encoded objects, minimize the maximum
number of questions by which every object in the set is identifiable.

Input

The input is a sequence of multiple datasets. Each dataset begins with a line which consists of
two integers, m and n: the number of features, and the number of objects, respectively. You
can assume 0 < m ≤ 11 and 0 < n ≤ 128. It is followed by n lines, each of which corresponds
to an object. Each line includes a binary string of length m which represent the value ("yes" or
"no") of features. There are no two identical objects.

The end of the input is indicated by a line containing two zeros. There are at most 100 datasets.

Output

For each dataset, minimize the maximum number of questions by which every object is identifiable and output the result.

Sample Input

8 1
11010101
11 4
00111001100
01001101011
01010000011
01100110001
11 16
01000101111
01011000000
01011111001
01101101001
01110010111
01110100111
10000001010
10010001000
10010110100
10100010100
10101010110
10110100010
11001010011
11011001001
11111000111
11111011101
11 12
10000000000
01000000000
00100000000
00010000000
00001000000
00000100000
00000010000
00000001000
00000000100
00000000010
00000000001
00000000000
9 32
001000000
000100000
000010000
000001000
000000100
000000010
000000001
000000000
011000000
010100000
010010000
010001000
010000100
010000010
010000001
010000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
100000000
111000000
110100000
110010000
110001000
110000100
110000010
110000001
110000000
0 0

Output for the Sample Input

0
2
4
11
9



Sample input:
8 1
11010101
11 4
00111001100
01001101011
01010000011
01100110001
11 16
01000101111
01011000000
01011111001
01101101001
01110010111
01110100111
10000001010
10010001000
10010110100
10100010100
10101010110
10110100010
11001010011
11011001001
11111000111
11111011101
11 12
10000000000
01000000000
00100000000
00010000000
00001000000
00000100000
00000010000
00000001000
00000000100
00000000010
00000000001
00000000000
9 32
001000000
000100000
000010000
000001000
000000100
000000010
000000001
000000000
011000000
010100000
010010000
010001000
010000100
010000010
010000001
010000000
101000000
100100000
100010000
100001000
100000100
100000010
100000001
100000000
111000000
110100000
110010000
110001000
110000100
110000010
110000001
110000000
0 0


Sample output:
0
2
4
11
9

Submission status: Accepted

Solution code:
from collections import Counter


while True:
    m, n = (int(s) for s in input().split())
    if not m:
        break

    objs = [int(input(), 2) for i in range(n)]
    dp = [[0] * (1 << m) for i in range(1 << m)]
    bits = [1 << i for i in range(m)]

    for mask in reversed(range(1 << m)):
        s = Counter(obj & mask for obj in objs)
        for masked, value in s.items():
            if value > 1:
                dp[mask][masked] = min(max(dp[mask | b][masked],
                                           dp[mask | b][masked | b]) + 1
                                       for b in bits if not b & mask)
    print(dp[0][0])

Submission status: Accepted

Solution code:
from collections import Counter


while True:
    m, n = (int(s) for s in input().split())
    if not m:
        break

    objs = [int(input(), 2) for i in range(n)]
    dp = [bytearray(1 << m) for i in range(1 << m)]
    bits = [1 << i for i in range(m)]

    for mask in reversed(range((1 << m) - 1)):
        s = Counter(obj & mask for obj in objs)
        for masked, count in s.items():
            if count > 1:
                dp[mask][masked] = min(max(dp[mask + b][masked],
                                           dp[mask + b][masked + b]) + 1
                                       for b in bits if not b & mask)
    print(dp[0][0])

Submission status: Accepted

Solution code:
from collections import Counter

while True:
    m, n = (int(s) for s in input().split())
    if not m:
        break

    objects = [int(input(), 2) for i in range(n)]
    dp = [bytearray(1 << m) for i in range(1 << m)]
    bits = [1 << i for i in range(m)]

    for mask in reversed(range((1 << m) - 1)):
        for masked, count in Counter(obj & mask for obj in objects).items():
            if count > 1:
                dp[mask][masked] = min(max(dp[mask + b][masked],
                                           dp[mask + b][masked + b]) + 1
                                       for b in bits if not b & mask)
    print(dp[0][0])

Submission status: Accepted

Solution code:
from collections import Counter

while True:
    m, n = (int(s) for s in input().split())
    if not m:
        break

    objects = [int(input(), 2) for i in range(n)]
    dp = [bytearray(1 << m) for i in range(1 << m)]
    bits = [1 << i for i in range(m)]

    for asked in reversed(range((1 << m) - 1)):
        for masked, count in Counter(obj & asked for obj in objects).items():
            if count > 1:
                dp[asked][masked] = min(max(dp[asked + b][masked],
                                            dp[asked + b][masked + b])
                                        for b in bits if not b & asked) + 1
    print(dp[0][0])

Submission status: Accepted

Solution code:
from collections import Counter
import sys
def solve():
    readline = sys.stdin.buffer.readline
    write = sys.stdout.buffer.write
    M, N = map(int, readline().split())
    if M == N == 0:
        return False
    B = [int(readline(), 2) for i in range(N)]
    memo = {}
    def dfs(s, t):
        key = (s, t)
        if key in memo:
            return memo[key]
        c = 0
        for b in B:
            if (b & s) == t:
                c += 1
        if c <= 1:
            memo[key] = 0
            return 0
        res = M
        for i in range(M):
            b = (1 << i)
            if s & b == 0:
                res = min(res, max(dfs(s|b, t), dfs(s|b, t|b))+1)
        memo[key] = res
        return res
    write(b"%d\n" % dfs(0, 0))
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n,m):
        a = [int(S(), 2) for _ in range(m)]
        mi = 0
        ma = max(a)
        while 2**mi <= ma:
            mi += 1
        ii = [2**i for i in range(mi+1)]

        fm = {}
        def _f(a):
            k = tuple(a)
            if k in fm:
                return fm[k]

            if len(a) < 2:
                fm[k] = 0
                return 0

            r = inf
            for i in ii:
                a1 = []
                a2 = []
                for c in a:
                    if i & c:
                        a1.append(c)
                    else:
                        a2.append(c)
                if not a1 or not a2:
                    continue
                r1 = _f(a1)
                r2 = _f(a2)
                tr = max(r1, r2) + 1
                if r > tr:
                    r = tr
            fm[k] = r
            return r

        r = _f(a)
        return r

    while 1:
        n,m = LI()
        if n == 0:
            break
        rr.append(f(n,m))

    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
from collections import Counter

while True:
    m, n = (int(s) for s in input().split())
    if not m:
        break

    objs = [int(input(), 2) for i in range(n)]
    f = [[0 for i in range(1 << m)] for i in range(1 << m)]

    for mask in reversed(range(1<<m)):
        s = Counter(obj & mask for obj in objs)
        for mask0 in range(mask + 1):
            if s[mask0] > 1:
                f[mask][mask0] = n + 1
                for b in [1<<k for k in range(m)]:
                    if not (b & mask):
                        f[mask][mask0] = min(f[mask][mask0],
                                             max(f[mask + b][mask0],
                                                 f[mask + b][mask0 + b]) + 1
                                             )
    print(f[0][0])

Submission status: Runtime Error

Solution code:
while True:
    m, n = (int(s) for s in input().split())
    if not m:
        break

    objs = [int(input(), 2) for i in range(n)]
    dp = [[0] * (1<<m) for i in range(1 << m)]
    bits = [1 << i for i in range(m)]

    for mask in reversed(range(1 << m)):
        s = Counter(obj & mask for obj in objs)
        for mask0, value in s.items():
            if value > 1:
                dp[mask][mask0] = min(max(dp[mask | b][mask0],
                                          dp[mask | b][mask0 | b]) + 1
                                      for b in bits if not b & mask)
    print(dp[0][0])

Submission status: Runtime Error

Solution code:
while True:
    m, n = (int(s) for s in raw_input().split())
    if not m:
        break

    objs = [int(raw_input(), 2) for i in range(n)]
    dp = [[0] * (1<<m) for i in range(1 << m)]
    bits = [1 << i for i in range(m)]

    for mask in reversed(range(1 << m)):
        s = Counter(obj & mask for obj in objs)
        for mask0, value in s.items():
            if value > 1:
                dp[mask][mask0] = min(max(dp[mask | b][mask0],
                                          dp[mask | b][mask0 | b]) + 1
                                      for b in bits if not b & mask)
    print dp[0][0]