Défi · algorithmes difficile 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.
Signature
def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:Exemples
max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]]) # -> 3
max_matching(2, 1, [[0, 0], [1, 0]]) # -> 1Plus 7 tests masqués et 2 tests de performance sous contrainte de temps ; leurs entrées ne sont pas affichées. Les défis sont soumis aux modèles en anglais.
#1Anthropic Claude Sonnet 5.5résolu · 11 sur 11 testsréponse en 9.7 s · exécution 453 ms · $0.02 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])attendu 3 1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])attendu 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 Flashrésolu · 11 sur 11 testsréponse en 5.9 s · exécution 691 ms · $0.0016 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])attendu 3 2 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])attendu 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 0423non résolu · 9 sur 11 testsréponse en 2.8 s · exécution 1.2 s · $0.0006 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])attendu 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])attendu 1 <1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ délai limite dépassé⏱ délai limite dépasséCode
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 resultSecond essai
non résolu · 10 sur 11 testsréponse en 7.5 s · $0.0013Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.
✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])attendu 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])attendu 1 <1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ délai limite dépassé⏱ 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 Argonnon résolu · 8 sur 11 testsréponse en 10 s · exécution 3.2 s · $0.0080 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])attendu 3 2 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])attendu 1 2 ms ✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✗ délai limite dépassé✓ 1 ms✓ <1 ms⏱ délai limite dépassé⏱ délai limite dépasséCode
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 matchingSecond essai
résolu · 11 sur 11 testsréponse en 17 s · $0.01Le modèle a eu accès au nombre de tests échoués, aux exemples en échec avec les valeurs attendues et obtenues, ainsi qu'au motif d'échec des tests cachés (sans leurs entrées). Ne compte ni pour le classement ni pour l'évaluation.
✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])attendu 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])attendu 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
Coût en jetons: $0.04 · Déroulement et calcul des scores →