Problem p02901 (python)

Fixed submission:
# coding: utf-8
from functools import reduce


def solve(*args: str) -> str:
    a_max = 1+12*10**5
    n, m = map(int, args[0].split())
    cache = {}

    for i in range(1, 1+2*m, 2):
        a, _ = map(int, args[i].split())
        c = reduce(
            lambda x, y: x | 1 << y-1,
            [0] + list(map(int, args[i+1].split()))
        )
        cache[c] = min(cache.get(c, a_max), a)

    for C in tuple(cache.items()):
        unlocked, cost = C
        for E in tuple(cache.items()):
            c, a = E
            cache[unlocked | c] = min(
                cache.get(unlocked | c, a_max),
                a + cost
            )

    return str(cache.get(2**n-1, -1))


if __name__ == "__main__":
    nm = input()
    _, m = map(int, nm.split())
    print(solve(*([nm]+[input() for _ in range(2*m)])))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
from functools import lru_cache


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())

    keys = list(zip(
        list(map(lambda _: int(_.split()[0]), args[1::2])),
        map(
            lambda _: set2bin(
                set(map(int, _.split())),
                n, start=1
            ), args[2::2])
    ))
    dp = DP(keys, n)

    return str(
        dp.search_min_cost(0, 0)
    )


class DP:
    def __init__(self, keys: list, n: int):
        self.keys = keys
        self.mask = int('1'*n, 2)

    @lru_cache(maxsize=None)
    def search_min_cost(self, index: int, unlocked: int) -> int:
        ret = 0

        if len(self.keys) == index:
            if unlocked != self.mask:
                ret = -1

        else:
            a, C = self.keys[index]
            take = self.search_min_cost(index+1, C | unlocked)
            skip = self.search_min_cost(index+1, unlocked)

            if take == -1 and skip == -1:
                ret = -1
            elif take == -1:
                ret = skip
            elif skip == -1:
                ret = a + take
            else:
                ret = min(a+take, skip)

        return ret


def set2bin(S: set, n: int, start: int = 0) -> int:
    ret = 0
    for s in S:
        ret += 2**(s-start)
    return ret


def bin2int(B: list) -> int:
    ret = 0
    for n in range(len(B)):
        if B[n]:
            ret += 2**n

    return ret


if __name__ == "__main__":
    nm = input()
    _, m = map(int, nm.split())
    print(solve(*([nm]+[input() for _ in range(2*m)])))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())

    keys = list(zip(
        list(map(lambda _: int(_.split()[0]), args[1::2])),
        map(
            lambda _: set2bin(
                set(map(int, _.split())),
                n, start=1, initial=False
            ), args[2::2])
    ))
    dp = DP()

    return str(
        dp.search_min_cost(
            keys, np.array([False for _ in range(n)], dtype=bool)
        )
    )


class DP:
    def __init__(self):
        self.cache = {}

    def search_min_cost(self, keys: list, unlocked: list) -> int:
        ret = 0
        args = '{},{}'.format(len(keys), bin2int(unlocked))

        if args in self.cache.keys():
            ret = self.cache[args]

        elif len(keys) == 0:
            if not all(unlocked):
                ret = -1

        else:
            a, C = keys[0]
            take = self.search_min_cost(keys[1:], C | unlocked)
            skip = self.search_min_cost(keys[1:], unlocked)

            if take == -1 and skip == -1:
                ret = -1
            elif take == -1:
                ret = skip
            elif skip == -1:
                ret = a + take
            else:
                ret = min(a+take, skip)

        self.cache[args] = ret
        return ret


def set2bin(S: set, n: int, start: int = 0, initial: bool = True) -> list:
    ret = np.array([initial for _ in range(n)], dtype=bool)
    for s in S:
        ret[s-start] = not initial
    return ret


def bin2int(B: list) -> int:
    ret = 0
    for n in range(len(B)):
        if B[n]:
            ret += 2**n

    return ret


if __name__ == "__main__":
    nm = input()
    _, m = map(int, nm.split())
    print(solve(*([nm]+[input() for _ in range(2*m)])))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())

    keys = list(zip(
        list(map(lambda _: int(_.split()[0]), args[1::2])),
        map(
            lambda _: set2bin(
                set(map(int, _.split())),
                n, start=1, initial=False
            ), args[2::2])
    ))

    return str(
        search_min_cost(keys, np.array([False for _ in range(n)], dtype=bool))
    )


cache = {}


def search_min_cost(keys: list, unlocked: list) -> int:
    ret = 0
    args = str((len(keys), unlocked))

    if args in cache.keys():
        ret = cache[args]

    elif len(keys) == 0:
        if not all(unlocked):
            ret = -1

    else:
        a, C = keys[0]
        take = search_min_cost(keys[1:], C | unlocked)
        skip = search_min_cost(keys[1:], unlocked)

        if take == -1 and skip == -1:
            ret = -1
        elif take == -1:
            ret = skip
        elif skip == -1:
            ret = a + take
        else:
            ret = min(a+take, skip)

    cache[args] = ret
    return ret


def set2bin(S: set, n: int, start: int = 0, initial: bool = True):
    ret = np.array([initial for _ in range(n)], dtype=bool)
    for s in S:
        ret[s-start] = not initial
    return ret


if __name__ == "__main__":
    nm = input()
    _, m = map(int, nm.split())
    print(solve(*([nm]+[input() for _ in range(2*m)])))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())

    keys = list(zip(
        list(map(lambda _: int(_.split()[0]), args[1::2])),
        map(
            lambda _: set2bin(
                set(map(int, _.split())),
                n, start=1, initial=False
            ), args[2::2])
    ))

    return str(
        search_min_cost(keys, np.array([False for _ in range(n)], dtype=bool))
    )


cache = {}


def search_min_cost(keys: list, unlocked: list) -> int:
    ret = 0
    args = str((len(keys), unlocked))

    if args in cache.keys():
        ret = cache[args]

    elif len(keys) == 0:
        if not all(unlocked):
            ret = -1

    else:
        a, C = keys[0]
        take = search_min_cost(keys[1:], C | unlocked)
        skip = search_min_cost(keys[1:], unlocked)

        if take == -1 and skip == -1:
            ret = -1
        elif take == -1:
            ret = skip
        elif skip == -1:
            ret = a + take
        else:
            ret = min(a+take, skip)

    cache[args] = ret
    return ret


def set2bin(S: set, n: int, start: int = 0, initial: bool = True):
    ret = np.array([initial for _ in range(n)], dtype=bool)
    for s in S:
        ret[s-start] = not initial
    return ret


if __name__ == "__main__":
    nm = input()
    _, m = map(int, nm.split())
    print(solve(*([nm]+[input() for _ in range(2*m)])))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())
    prices = list(map(lambda _: int(_.split()[0]), args[1::2]))
    targets = []
    for C in args[2::2]:
        b = np.array([0 for _ in range(n)])
        for i in map(int, C.split()):
            b[i-1] = 1
        # b = 0
        # for ci in map(int, C.split()):
        #     b += 2**ci
        targets.append(b)

    s = np.array([0 for _ in range(n)])
    for t in targets:
        s += t

    if not all(map(lambda x: x > 0, s)):
        return str(-1)

    total = sum(prices)

    keys = sorted(zip(prices, targets))
    for k in reversed(keys):
        p, t = k
        if all(map(lambda x: x > 0, s-t)):
            total -= p
            s = s-t

    # if len(set(itertools.chain.from_iterable(targets))) != n:
    #     return str(-1)

    return str(total)


if __name__ == "__main__":
    nm = input()
    _, m = map(int, nm.split())
    print(solve(*([nm]+[input() for _ in range(2*m)])))