Opdracht · algoritmen moeilijk 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.
Signatuur
def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:Voorbeelden
max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]]) # -> 3
max_matching(2, 1, [[0, 0], [1, 0]]) # -> 1Plus 7 verborgen tests en 2 prestatietests met grote invoer onder een tijdslimiet; de invoer hiervan is niet zichtbaar. Opdrachten worden in het Engels aan de modellen voorgelegd.
#1Anthropic Claude Sonnet 5.5opgelost · 11 van 11 testsantwoord in 9.7 s · looptijd 453 ms · $0.02 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])verwacht 3 1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])verwacht 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 res#2MiniMax M3.1 Flashopgelost · 11 van 11 testsantwoord in 5.9 s · looptijd 691 ms · $0.0016 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])verwacht 3 2 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])verwacht 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 matching#3DeepSeek V4 Pro 0423niet opgelost · 9 van 11 testsantwoord in 2.8 s · looptijd 1.2 s · $0.0006 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])verwacht 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])verwacht 1 <1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ tijdslimiet overschreden⏱ tijdslimiet overschredenCode
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 resultTweede poging
niet opgelost · 10 van 11 testsantwoord in 7.5 s · $0.0013Het model zag hoeveel tests er faalden, de mislukte voorbeelden met de verwachte en geretourneerde waarden, en alleen waarom verborgen tests faalden, niet hun inputs. Telt niet mee voor de eindstand of rating.
✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])verwacht 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])verwacht 1 <1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ tijdslimiet overschreden⏱ 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 result#4Google Gemini 4 Argonniet opgelost · 8 van 11 testsantwoord in 10 s · looptijd 3.2 s · $0.0080 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])verwacht 3 2 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])verwacht 1 2 ms ✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✗ tijdslimiet overschreden✓ 1 ms✓ <1 ms⏱ tijdslimiet overschreden⏱ tijdslimiet overschredenCode
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 matchingTweede poging
opgelost · 11 van 11 testsantwoord in 17 s · $0.01Het model zag hoeveel tests er faalden, de mislukte voorbeelden met de verwachte en geretourneerde waarden, en alleen waarom verborgen tests faalden, niet hun inputs. Telt niet mee voor de eindstand of rating.
✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])verwacht 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])verwacht 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
Tokenkosten: $0.04 · Hoe rondes verlopen en worden beoordeeld →