Aufgabe · Algorithmen schwer Python ·
Maximum bipartite matching
There are n_left workers (0..n_left-1) and n_right jobs (0..n_right-1). Each pair [u, v] in edges says worker u can do job v; pairs can repeat. Every worker takes at most one job and every job goes to at most one worker. Return the largest possible number of assigned workers. Up to 20,000 workers, 20,000 jobs and 100,000 pairs.
Signatur
def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:Beispiele
max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]]) # -> 3
max_matching(2, 1, [[0, 0], [1, 0]]) # -> 1Zusätzlich 7 versteckte Tests und 2 Performance-Tests mit großem Input unter Zeitlimit; deren Inputs werden nicht angezeigt. Die Aufgaben werden den Modellen auf Englisch gestellt.
Platz 1Anthropic Claude Sonnet 5.5gelöst · 11 von 11 TestsAntwort in 9.7 s · Laufzeit 453 ms · $0.02 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])erwartet 3 1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])erwartet 1 1 ms ✓ 2 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 374 ms⏱ 69 msCode
def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int: adj = [[] for _ in range(n_left)] for u, v in edges: if 0 <= u < n_left and 0 <= v < n_right: adj[u].append(v) matchL = [-1] * n_left matchR = [-1] * n_right res = 0 for u in range(n_left): for v in adj[u]: if matchR[v] == -1: matchR[v] = u matchL[u] = v res += 1 break while True: dist = [-1] * n_left q = [] for u in range(n_left): if matchL[u] == -1 and adj[u]: dist[u] = 0 q.append(u) found = False qi = 0 while qi < len(q): u = q[qi] qi += 1 du = dist[u] + 1 for v in adj[u]: w = matchR[v] if w == -1: found = True elif dist[w] == -1: dist[w] = du q.append(w) if not found: break it = [0] * n_left aug = 0 for r in range(n_left): if matchL[r] != -1 or dist[r] != 0: continue stack = [r] while stack: u = stack[-1] au = adj[u] i = it[u] pushed = False done = False while i < len(au): v = au[i] i += 1 w = matchR[v] if w == -1: it[u] = i done = True break if dist[w] == dist[u] + 1: it[u] = i stack.append(w) pushed = True break if done: for x in stack: v = adj[x][it[x] - 1] matchL[x] = v matchR[v] = x aug += 1 break if pushed: continue it[u] = i dist[u] = -2 stack.pop() if aug == 0: break res += aug return resPlatz 2MiniMax M3.1 Flashgelöst · 11 von 11 TestsAntwort in 5.9 s · Laufzeit 691 ms · $0.0016 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])erwartet 3 2 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])erwartet 1 <1 ms ✓ 1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ 10 ms✓ <1 ms✓ <1 ms⏱ 563 ms⏱ 106 msCode
from collections import deque def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int: if n_left == 0 or n_right == 0: return 0 adj = [None] * n_left for u in range(n_left): adj[u] = [] seen_sets = [set() for _ in range(n_left)] for e in edges: u = e[0] v = e[1] s = seen_sets[u] if v not in s: s.add(v) adj[u].append(v) for u in range(n_left): adj[u] = list(seen_sets[u]) match_l = [-1] * n_left match_r = [-1] * n_right matching = 0 INF = n_left + 1 while True: # BFS layering dist = [-1] * n_left q = deque() for u in range(n_left): if match_l[u] == -1: dist[u] = 0 q.append(u) limit = INF while q: u = q.popleft() du = dist[u] if du + 1 > limit: continue for v in adj[u]: w = match_r[v] if w == -1: if du + 1 < limit: limit = du + 1 elif dist[w] == -1 and du + 1 < limit: dist[w] = du + 1 q.append(w) if limit == INF: break ptr = [0] * n_left for root in range(n_left): if match_l[root] != -1 or dist[root] != 0: continue # iterative DFS for an augmenting path stack = [root] rights = [] # rights[i]: right vertex used from stack[i] to stack[i+1] found = False while stack: u = stack[-1] a = adj[u] advanced = False i = ptr[u] ln = len(a) while i < ln: v = a[i] i += 1 w = match_r[v] if w == -1: if dist[u] + 1 == limit: match_l[u] = v match_r[v] = u for k in range(len(stack) - 2, -1, -1): p = stack[k] rv = rights[k] match_l[p] = rv match_r[rv] = p matching += 1 found = True break elif dist[w] == dist[u] + 1: ptr[u] = i stack.append(w) rights.append(v) advanced = True break if found: break ptr[u] = i if not advanced: dist[u] = -1 stack.pop() if rights: rights.pop() return matchingPlatz 3DeepSeek V4 Pro 0423nicht gelöst · 9 von 11 TestsAntwort in 2.8 s · Laufzeit 1.2 s · $0.0006 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])erwartet 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])erwartet 1 <1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ Zeitlimit überschritten⏱ Zeitlimit überschrittenCode
def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int: # Build adjacency list for left side graph = [[] for _ in range(n_left)] for u, v in edges: graph[u].append(v) # matchR[v] = u if job v is matched to worker u, else -1 matchR = [-1] * n_right # Standard DFS for augmenting path (Kuhn's algorithm) def dfs(u, seen): for v in graph[u]: if seen[v]: continue seen[v] = True if matchR[v] == -1 or dfs(matchR[v], seen): matchR[v] = u return True return False result = 0 for u in range(n_left): # seen array for this DFS iteration seen = [False] * n_right if dfs(u, seen): result += 1 return resultZweiter Versuch
nicht gelöst · 10 von 11 TestsAntwort in 7.5 s · $0.0013Das Modell sah, wie viele Tests fehlschlugen, die fehlerhaften Beispiele samt erwarteten und gelieferten Werten sowie den Grund für das Scheitern versteckter Tests, nicht aber deren Eingaben. Zählt nicht für Platzierungen oder das Rating.
✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])erwartet 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])erwartet 1 <1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ Zeitlimit überschritten⏱ 60 msCode
def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int: # Build adjacency (remove duplicates per worker) graph = [set() for _ in range(n_left)] for u, v in edges: graph[u].add(v) graph = [list(adj) for adj in graph] matchR = [-1] * n_right # DFS with pointer for visited tracking using iteration counter visited = [0] * n_right visit_counter = 0 def dfs(u): nonlocal visit_counter for v in graph[u]: if visited[v] == visit_counter: continue visited[v] = visit_counter if matchR[v] == -1 or dfs(matchR[v]): matchR[v] = u return True return False result = 0 for u in range(n_left): visit_counter += 1 if dfs(u): result += 1 return resultPlatz 4Google Gemini 4 Argonnicht gelöst · 8 von 11 TestsAntwort in 10 s · Laufzeit 3.2 s · $0.0080 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])erwartet 3 2 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])erwartet 1 2 ms ✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✗ Zeitlimit überschritten✓ 1 ms✓ <1 ms⏱ Zeitlimit überschritten⏱ Zeitlimit überschrittenCode
from collections import deque def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int: if n_left == 0 or n_right == 0 or not edges: return 0 adj = [[] for _ in range(n_left)] for u, v in edges: adj[u].append(v) pair_u = [-1] * n_left pair_v = [-1] * n_right matching = 0 # Greedy initialization for u in range(n_left): for v in adj[u]: if pair_v[v] == -1: pair_u[u] = v pair_v[v] = u matching += 1 break dist = [0] * n_left INF = 10**9 # Hopcroft-Karp algorithm while True: queue = deque() for u in range(n_left): if pair_u[u] == -1: dist[u] = 0 queue.append(u) else: dist[u] = INF found_augmenting_path = False while queue: u = queue.popleft() d_next = dist[u] + 1 for v in adj[u]: pu = pair_v[v] if pu == -1: found_augmenting_path = True elif dist[pu] == INF: dist[pu] = d_next queue.append(pu) if not found_augmenting_path: break # Iterative DFS to avoid recursion limit and overhead for start_u in range(n_left): if pair_u[start_u] == -1: stack = [(start_u, 0)] while stack: u, idx = stack[-1] adj_u = adj[u] n_adj = len(adj_u) while idx < n_adj: v = adj_u[idx] pu = pair_v[v] if pu == -1: # Found augmenting path, trace back and flip edges pair_v[v] = u pair_u[u] = v stack.pop() while stack: parent_u, parent_idx = stack.pop() parent_v = adj[parent_u][parent_idx] pair_v[parent_v] = parent_u pair_u[parent_u] = parent_v matching += 1 break elif dist[pu] == dist[u] + 1: stack[-1] = (u, idx) dist[pu] = INF # Mark visited in this phase stack.append((pu, 0)) break idx += 1 else: stack.pop() return matchingZweiter Versuch
gelöst · 11 von 11 TestsAntwort in 17 s · $0.01Das Modell sah, wie viele Tests fehlschlugen, die fehlerhaften Beispiele samt erwarteten und gelieferten Werten sowie den Grund für das Scheitern versteckter Tests, nicht aber deren Eingaben. Zählt nicht für Platzierungen oder das Rating.
✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])erwartet 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])erwartet 1 <1 ms ✓ <1 ms✓ 2 ms✓ <1 ms✓ 6 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 440 ms⏱ 73 msCode
from collections import deque def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int: if n_left == 0 or n_right == 0 or not edges: return 0 adj = [[] for _ in range(n_left)] for u, v in edges: adj[u].append(v) pair_u = [-1] * n_left pair_v = [-1] * n_right matching = 0 # Greedy initialization for u in range(n_left): for v in adj[u]: if pair_v[v] == -1: pair_u[u] = v pair_v[v] = u matching += 1 break INF = 10**9 unmatched = [u for u in range(n_left) if pair_u[u] == -1] while unmatched: dist = [INF] * n_left for u in unmatched: dist[u] = 0 queue = deque(unmatched) min_free_dist = INF while queue: u = queue.popleft() d = dist[u] if d >= min_free_dist: continue d_next = d + 1 for v in adj[u]: pu = pair_v[v] if pu == -1: min_free_dist = d_next elif dist[pu] == INF: dist[pu] = d_next queue.append(pu) if min_free_dist == INF: break new_unmatched = [] for start_u in unmatched: stack = [(start_u, 0, 0)] dist[start_u] = INF while stack: u, idx, d = stack[-1] adj_u = adj[u] n_adj = len(adj_u) d_next = d + 1 while idx < n_adj: v = adj_u[idx] pu = pair_v[v] if pu == -1: if d_next == min_free_dist: pair_v[v] = u pair_u[u] = v stack.pop() while stack: parent_u, parent_idx, _ = stack.pop() parent_v = adj[parent_u][parent_idx] pair_v[parent_v] = parent_u pair_u[parent_u] = parent_v matching += 1 break elif dist[pu] == d_next and d_next < min_free_dist: stack[-1] = (u, idx, d) dist[pu] = INF stack.append((pu, 0, d_next)) break idx += 1 else: stack.pop() if stack: parent_u, parent_idx, parent_d = stack[-1] stack[-1] = (parent_u, parent_idx + 1, parent_d) if pair_u[start_u] == -1: new_unmatched.append(start_u) unmatched = new_unmatched return matching
Token-Kosten: $0.04 · So laufen Runden und Wertung ab →