Bittijono

# Maximum subset amounts for different lengths of binary. Generated from a previous, failed attempt at solving this problem
optimization = [
1,
3,
6,
11,
20,
36,
59,
99,
172,
302,
486,
809,
1400,
2493,
3987,
6611,
11404,
20430,
33046,
54466,
93430,
166513,
276569,
452193,
769692
]

# Helper global variables for catalog_subsets()
subsets = set()
turns = None

# A single node in the binary tree, where the root node is the first binary digit from left. From there on out going left means skipping a digit,
# and going right means including it. This means all possible subsets are paths from the root node to a leaf node
class Node:
    l = None
    r = None
    b = None

# Gets all the subsets of certain length(stored in global variable 'turns') from a binary tree described above and stores them into a global variable
def catalog_subsets(node, bits=()):
    global subsets

    # Do we have all the bits we need
    if len(bits) == turns:
        subsets.add(bits)
        return

    #If this is not a leaf node
    if node.l is not None:
        #Only add our bit to the rightmost path
        catalog_subsets(node.l, bits)
        catalog_subsets(node.r, bits + (node.b,))
    else:
        #If we're a leaf node, and we need ony one bit more, add it and submit to subsets
        if len(bits) == turns - 1:
            subsets.add(bits + (node.b,))

# Returns the total number of subsets in a binary tree
def numSubSets(node):
    global subsets
    global turns

    depth = 0
    node1 = node
    subs = 0

    #Measure the depth
    while node1 is not None:
        node1 = node1.l
        depth = depth + 1

    # Loop through all the possible subset lengths, and count them all up
    for i in range(1, depth + 1):
        subsets = set()
        turns = i
        catalog_subsets(node)
        subs = subs + len(subsets)
    return subs

# Generates a binary tree from a list of bits
def gen_tree(bits):
    node = Node()
    node.b = bits[0]

    if len(bits) != 1:
        
        node.l = gen_tree(bits[1:])
        node.r = gen_tree(bits[1:])

    return node

#returns a smallest bitset with excactly n subsets
def get_answer(n):
    #Get the smallest possible length from the optimization list
    l = 1
    for j in range(25):
        if optimization[j] < n:
            l = j
            break
    
    #Keep increasing the length, and looking through all the possible values for the answer
    #Yeah brute force is not the best way, but I learned about this comp. on the friday evening, flew to france in sunday morning. Hour to the deadline, baby!
    while True:
        for i in range(2**l):
             bits = ("{0:0" + str(l) + "b}").format(i)
             bits = [int(s) for s in bits]
             node = gen_tree(bits)
             if numSubSets(node) == n:
                 return bits
        l = l + 1

inp = int(input())    

ans = get_answer(inp)

for b in ans:
    print(b, end="")
print()

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 31

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 33

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 36

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 4

Verdict: TIME LIMIT EXCEEDED