टास्क · एल्गोरिदम कठिन 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.5हल किया गया · 11 में से 11 टेस्ट्स पासजवाब का समय 9.7 s · रनटाइम 453 ms · $0.02

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])अपेक्षित 3	1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])अपेक्षित 1	1 ms

  ✓ 2 ms✓ 2 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 374 ms⏱ 69 ms
  कोड

  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 Flashहल किया गया · 11 में से 11 टेस्ट्स पासजवाब का समय 5.9 s · रनटाइम 691 ms · $0.0016

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])अपेक्षित 3	2 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])अपेक्षित 1	<1 ms

  ✓ 1 ms✓ 1 ms✓ 3 ms✓ 2 ms✓ 10 ms✓ <1 ms✓ <1 ms⏱ 563 ms⏱ 106 ms
  कोड

  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 0423हल नहीं हुआ · 11 में से 9 टेस्ट्स पासजवाब का समय 2.8 s · रनटाइम 1.2 s · $0.0006

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])अपेक्षित 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])अपेक्षित 1	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ 2 ms✓ 2 ms⏱ समय सीमा समाप्त (time limit exceeded)⏱ समय सीमा समाप्त (time limit exceeded)
  कोड

  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

  दूसरा प्रयास

  हल नहीं हुआ · 11 में से 10 टेस्ट्स पासजवाब का समय 7.5 s · $0.0013

  मॉडल को दिखाया गया कि कितने टेस्ट फेल हुए, फेल हुए उदाहरणों के अपेक्षित और मिले हुए परिणाम क्या थे, और छिपे हुए टेस्ट्स के फेल होने का सिर्फ़ कारण (इनपुट्स नहीं)। यह रैंकिंग या रेटिंग में नहीं गिना जाता।

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])अपेक्षित 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])अपेक्षित 1	<1 ms

  ✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ समय सीमा समाप्त (time limit exceeded)⏱ 60 ms

  कोड

  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 Argonहल नहीं हुआ · 11 में से 8 टेस्ट्स पासजवाब का समय 10 s · रनटाइम 3.2 s · $0.0080

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])अपेक्षित 3	2 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])अपेक्षित 1	2 ms

  ✓ 1 ms✓ 1 ms✓ 2 ms✓ 3 ms✗ समय सीमा समाप्त (time limit exceeded)✓ 1 ms✓ <1 ms⏱ समय सीमा समाप्त (time limit exceeded)⏱ समय सीमा समाप्त (time limit exceeded)
  कोड

  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

  दूसरा प्रयास

  हल किया गया · 11 में से 11 टेस्ट्स पासजवाब का समय 17 s · $0.01

  मॉडल को दिखाया गया कि कितने टेस्ट फेल हुए, फेल हुए उदाहरणों के अपेक्षित और मिले हुए परिणाम क्या थे, और छिपे हुए टेस्ट्स के फेल होने का सिर्फ़ कारण (इनपुट्स नहीं)। यह रैंकिंग या रेटिंग में नहीं गिना जाता।

  ✓	max_matching(3, 3, [[0, 0], [0, 1], [1, 0], [2, 2]])अपेक्षित 3	<1 ms
  ✓	max_matching(2, 1, [[0, 0], [1, 0]])अपेक्षित 1	<1 ms

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

  कोड

  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

टोकन लागत: $0.04 · राउंड कैसे आयोजित और स्कोर किए जाते हैं →