Task · algorithms hard Python ·

Maximum bipartite matching

def max_matching(n_left: int, n_right: int, edges: list[list[int]]) -> int:

max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])  # -> 3
max_matching(2, 1, [[0, 0], [1, 0]])  # -> 1

• #1Anthropic Claude Sonnet 5.5solved · 11 of 11 testsanswer in 9.7 s · runtime 453 ms · $0.02

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])expected 3	1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])expected 1	1 ms

  ✓ 2 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 374 ms⏱ 69 ms
  Code

  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 Flashsolved · 11 of 11 testsanswer in 5.9 s · runtime 691 ms · $0.0016

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])expected 3	2 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])expected 1	<1 ms

  ✓ 1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ 10 ms✓ <1 ms✓ <1 ms⏱ 563 ms⏱ 106 ms
  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:
          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 0423not solved · 9 of 11 testsanswer in 2.8 s · runtime 1.2 s · $0.0006

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])expected 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])expected 1	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ time limit exceeded⏱ time limit exceeded
  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 result

  Second try

  not solved · 10 of 11 testsanswer in 7.5 s · $0.0013

  The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])expected 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])expected 1	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ time limit exceeded⏱ 60 ms

  Code

  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 Argonnot solved · 8 of 11 testsanswer in 10 s · runtime 3.2 s · $0.0080

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])expected 3	2 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])expected 1	2 ms

  ✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✗ time limit exceeded✓ 1 ms✓ <1 ms⏱ time limit exceeded⏱ time limit exceeded
  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 matching

  Second try

  solved · 11 of 11 testsanswer in 17 s · $0.01

  The model saw how many tests failed, the failing examples with the expected and returned values, and only why hidden tests failed, not their inputs. Doesn't count for places or the rating.

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])expected 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])expected 1	<1 ms

  ✓ <1 ms✓ 2 ms✓ <1 ms✓ 6 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 440 ms⏱ 73 ms

  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
  
      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

Tokens cost: $0.04 · How rounds are run and scored →