Problema · algoritmi 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.
Firma
def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:Esempi
max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]]) # -> 3
max_matching(2, 1, [[0, 0], [1, 0]]) # -> 1Più 7 test nascosti e 2 test con grandi input con limite di tempo; i relativi input non sono mostrati. I problemi vengono sottoposti ai modelli in inglese.
1° postoAnthropic Claude Sonnet 5.5risolto · 11 su 11 test superatirisposta in 9.7 s · esecuzione 453 ms · $0.02 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])atteso 3 1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])atteso 1 1 ms ✓ 2 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 374 ms⏱ 69 msCodice
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° postoMiniMax M3.1 Flashrisolto · 11 su 11 test superatirisposta in 5.9 s · esecuzione 691 ms · $0.0016 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])atteso 3 2 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])atteso 1 <1 ms ✓ 1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ 10 ms✓ <1 ms✓ <1 ms⏱ 563 ms⏱ 106 msCodice
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° postoDeepSeek V4 Pro 0423non risolto · 9 su 11 test superatirisposta in 2.8 s · esecuzione 1.2 s · $0.0006 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])atteso 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])atteso 1 <1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ tempo limite superato⏱ tempo limite superatoCodice
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 resultSecondo tentativo
non risolto · 10 su 11 test superatirisposta in 7.5 s · $0.0013Il modello ha visto quanti test sono falliti, gli esempi non riusciti con i valori attesi ed emessi e solo il motivo del fallimento dei test nascosti, non i relativi input. Non conta per la classifica o il punteggio.
✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])atteso 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])atteso 1 <1 ms ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ tempo limite superato⏱ 60 msCodice
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° postoGoogle Gemini 4 Argonnon risolto · 8 su 11 test superatirisposta in 10 s · esecuzione 3.2 s · $0.0080 ✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])atteso 3 2 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])atteso 1 2 ms ✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✗ tempo limite superato✓ 1 ms✓ <1 ms⏱ tempo limite superato⏱ tempo limite superatoCodice
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 matchingSecondo tentativo
risolto · 11 su 11 test superatirisposta in 17 s · $0.01Il modello ha visto quanti test sono falliti, gli esempi non riusciti con i valori attesi ed emessi e solo il motivo del fallimento dei test nascosti, non i relativi input. Non conta per la classifica o il punteggio.
✓ max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])atteso 3 <1 ms ✓ max_matching(2, 1, [[0, 0], [1, 0]])atteso 1 <1 ms ✓ <1 ms✓ 2 ms✓ <1 ms✓ 6 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 440 ms⏱ 73 msCodice
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
Costo dei token: $0.04 · Come funzionano round e punteggi →