Problem p03652 (python)

Fixed submission:
from collections import defaultdict
from operator import itemgetter


def sub(prefers, canceled):
    res = defaultdict(int)
    for pref in prefers:
        p = pref[-1]
        while p in canceled:
            pref.pop()
            p = pref[-1]
        res[p] += 1

    return max(res.items(), key=itemgetter(1))


def solve(m, prefers):
    canceled = set()
    ans = float('inf')
    for _ in range(m):
        s, c = sub(prefers, canceled)
        canceled.add(s)
        ans = min(ans, c)
    return ans


n, m = map(int, input().split())
prefers = [list(reversed(list(map(int, input().split())))) for _ in range(n)]

print(solve(m, prefers))

Buggy submission (verdict: Runtime Error):
def solve(m, prefers):
    if m == 1:
        return len(prefers)

    items = [True] * (m + 1)
    competes = {i: 0 for i in range(1, m + 1)}
    persons = [set() for _ in range(m + 1)]

    for i, prefer in enumerate(prefers):
        item = prefer[-1]
        competes[item] += 1
        persons[item].add(i)

    ans = m
    remain = m
    while ans > m // remain:
        mx = max(competes.values())
        ans = min(ans, mx)
        del_items = [a for a, k in competes.items() if k == mx]
        for a in del_items:
            items[a] = False
            del competes[a]
        if not competes:
            return ans
        for a in del_items:
            ps_a = persons[a]
            for p in ps_a:
                prefer = prefers[p]
                while not items[prefer[-1]]:
                    prefer.pop()
                item = prefer[-1]
                persons[item].add(p)
                competes[item] += 1
        remain -= 1

    return ans


n, m = map(int, input().split())
prefers = [list(reversed(list(map(int, input().split())))) for _ in range(n)]

print(solve(m, prefers))
def solve(m, prefers):
    if m == 1:
        return len(prefers)

    items = [True] * (m + 1)
    competes = {i: 0 for i in range(1, m + 1)}
    persons = [set() for _ in range(m + 1)]

    for i, prefer in enumerate(prefers):
        item = prefer[-1]
        competes[item] += 1
        persons[item].add(i)

    ans = m
    remain = m
    while ans > m // remain:
        mx = max(competes.values())
        ans = min(ans, mx)
        del_items = [a for a, k in competes.items() if k == mx]
        for a in del_items:
            items[a] = False
            del competes[a]
        if not competes:
            return ans
        for a in del_items:
            ps_a = persons[a]
            for p in ps_a:
                prefer = prefers[p]
                while not items[prefer[-1]]:
                    prefer.pop()
                item = prefer[-1]
                persons[item].add(p)
                competes[item] += 1
        remain -= 1

    return ans


n, m = map(int, input().split())
prefers = [list(reversed(list(map(int, input().split())))) for _ in range(n)]

print(solve(m, prefers))

Buggy submission (verdict: Runtime Error):
def solve(m, prefers):
    if m == 1:
        return 1

    items = [True] * (m + 1)
    competes = {i: 0 for i in range(1, m + 1)}
    persons = [set() for _ in range(m + 1)]

    for i, ps in enumerate(prefers):
        item = ps[-1]
        competes[item] += 1
        persons[item].add(i)

    ans = m
    remain = m
    while ans > m // remain:
        mx = max(competes.values())
        ans = min(ans, mx)
        del_items = [a for a, k in competes.items() if k == mx]
        for a in del_items:
            items[a] = False
            del competes[a]
        for a in del_items:
            pa = persons[a]
            for p in pa:
                pf = prefers[p]
                while not items[pf[-1]]:
                    pf.pop()
                item = pf[-1]
                persons[item].add(p)
                competes[item] += 1
        remain -= 1

    return ans


n, m = map(int, input().split())
prefers = [list(reversed(list(map(int, input().split())))) for _ in range(n)]

print(solve(m, prefers))

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
prefers = [list(reversed(list(map(int, input().split())))) for _ in range(n)]
items = [True] * (m + 1)
competes = {i: 0 for i in range(1, m + 1)}
persons = [set() for _ in range(m + 1)]

for i, ps in enumerate(prefers):
    item = ps[-1]
    competes[item] += 1
    persons[item].add(i)

ans = m
remain = m
while ans > m // remain:
    mx = max(competes.values())
    ans = min(ans, mx)
    del_items = [a for a, k in competes.items() if k == mx]
    for a in del_items:
        items[a] = False
        del competes[a]
    for a in del_items:
        pa = persons[a]
        try:
            for p in pa:
                pf = prefers[p]
                while not items[pf[-1]]:
                    pf.pop()
                item = pf[-1]
                persons[item].add(p)
                competes[item] += 1
        except:
            break
    remain -= 1

print(ans)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
prefers = [list(reversed(list(map(int, input().split())))) for _ in range(n)]
items = [True] * (m + 1)
competes = {i: 0 for i in range(1, m + 1)}
persons = [set() for _ in range(m + 1)]

for i, ps in enumerate(prefers):
    item = ps[-1]
    competes[item] += 1
    persons[item].add(i)

ans = m
remain = m
while ans > m // remain:
    mx = max(competes.values())
    ans = min(ans, mx)
    del_items = [a for a, k in competes.items() if k == mx]
    for a in del_items:
        items[a] = False
        del competes[a]
    for a in del_items:
        pa = persons[a]
        for p in pa:
            pf = prefers[p]
            try:
                while not items[pf[-1]]:
                    pf.pop()
            except:
                break
            item = pf[-1]
            persons[item].add(p)
            competes[item] += 1
    remain -= 1

print(ans)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
prefers = [list(reversed(list(map(int, input().split())))) for _ in range(n)]
items = [True] * (m + 1)
competes = {i: 0 for i in range(1, m + 1)}
persons = [set() for _ in range(m + 1)]

for i, ps in enumerate(prefers):
    item = ps[-1]
    competes[item] += 1
    persons[item].add(i)

ans = m
remain = m
while remain:
    mx = max(competes.values())
    ans = min(ans, mx)
    del_items = [a for a, k in competes.items() if k == mx]
    for a in del_items:
        items[a] = False
        del competes[a]
    for a in del_items:
        pa = persons[a]
        for p in pa:
            pf = prefers[p]
            while not items[pf[-1]]:
                pf.pop()
            item = pf[-1]
            persons[item].add(p)
            competes[item] += 1
    remain -= 1

print(ans)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
prefers = [list(reversed(list(map(int, input().split())))) for _ in range(n)]
items = [True] * (m + 1)
competes = {i: 0 for i in range(1, m + 1)}
persons = [set() for _ in range(m + 1)]

for i, ps in enumerate(prefers):
    item = ps[-1]
    competes[item] += 1
    persons[item].add(i)

ans = m
remain = m
while ans > m // remain:
    mx = max(competes.values())
    ans = min(ans, mx)
    del_items = [a for a, k in competes.items() if k == mx]
    for a in del_items:
        items[a] = False
    for a in del_items:
        pa = persons[a]
        for p in pa:
            pf = prefers[p]
            while not items[pf[-1]]:
                pf.pop()
            item = pf[-1]
            persons[item].add(p)
            competes[item] += 1
        persons[a] = None
        del competes[a]
    remain -= 1

print(ans)

Buggy submission (verdict: Runtime Error):
n, m = map(int, input().split())
prefers = [list(reversed(list(map(int, input().split())))) for _ in range(n)]
items = [True] * (m + 1)
competes = {i: 0 for i in range(1, m + 1)}
persons = [set() for _ in range(m + 1)]

for i, ps in enumerate(prefers):
    item = ps[-1]
    competes[item] += 1
    persons[item].add(i)

ans = m
remain = m
while ans > m // remain:
    mx = max(competes.values())
    ans = min(ans, mx)
    del_items = [a for a, k in competes.items() if k == mx]
    for a in del_items:
        items[a] = False
        pa = persons[a]
        for p in pa:
            pf = prefers[p]
            while not items[pf[-1]]:
                pf.pop()
            item = pf[-1]
            persons[item].add(p)
            competes[item] += 1
        persons[a] = None
        del competes[a]
    remain -= 1

print(ans)