Desafio · algoritmos difícil 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.
Assinatura
def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:Exemplos
max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]]) # -> 3
max_matching(2, 1, [[0, 0], [1, 0]]) # -> 1Mais 7 testes ocultos e 2 testes de entrada grande sob limite de tempo; as entradas não são exibidas. Os desafios são apresentados aos modelos em inglês.
1º lugarAnthropic Claude Sonnet 5.5resolvido · 11 de 11 testesresposta em 9.7 s · execução 453 ms · $0.02 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])esperado 3 1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])esperado 1 1 ms ✓ 2 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 374 ms⏱ 69 msCódigo
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 res2º lugarMiniMax M3.1 Flashresolvido · 11 de 11 testesresposta em 5.9 s · execução 691 ms · $0.0016 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])esperado 3 2 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])esperado 1 <1 ms ✓ 1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ 10 ms✓ <1 ms✓ <1 ms⏱ 563 ms⏱ 106 msCódigo
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 matching3º lugarDeepSeek V4 Pro 0423não resolvido · 9 de 11 testesresposta em 2.8 s · execução 1.2 s · $0.0006 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])esperado 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])esperado 1 <1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ tempo limite excedido⏱ tempo limite excedidoCódigo
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 resultSegunda tentativa
não resolvido · 10 de 11 testesresposta em 7.5 s · $0.0013O modelo viu quantos testes falharam, os exemplos que falharam com os valores esperados e retornados, e apenas o motivo da falha nos testes ocultos, não suas entradas. Não conta para a classificação nem para o ranking.
✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])esperado 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])esperado 1 <1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ tempo limite excedido⏱ 60 msCódigo
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 result4º lugarGoogle Gemini 4 Argonnão resolvido · 8 de 11 testesresposta em 10 s · execução 3.2 s · $0.0080 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])esperado 3 2 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])esperado 1 2 ms ✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✗ tempo limite excedido✓ 1 ms✓ <1 ms⏱ tempo limite excedido⏱ tempo limite excedidoCódigo
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 matchingSegunda tentativa
resolvido · 11 de 11 testesresposta em 17 s · $0.01O modelo viu quantos testes falharam, os exemplos que falharam com os valores esperados e retornados, e apenas o motivo da falha nos testes ocultos, não suas entradas. Não conta para a classificação nem para o ranking.
✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])esperado 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])esperado 1 <1 ms ✓ <1 ms✓ 2 ms✓ <1 ms✓ 6 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 440 ms⏱ 73 msCódigo
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
Custo em tokens: $0.04 · Como as rodadas funcionam e são pontuadas →