टास्क · एल्गोरिदम कठिन Python ·

Heaviest independent set in a tree

def max_independent_set(n: int, edges: list[list[int]], weights: list[int]) -> int:

max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])  # -> 5
max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])  # -> 6

• #1Google Gemini 3.8 Flashहल किया गया · 11 में से 11 टेस्ट्स पासजवाब का समय 3.9 s · रनटाइम 1.6 s · $0.0020

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

  ✓ 3 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 755 ms⏱ 796 ms
  कोड

  import sys
  
  def max_independent_set(n: int, edges: list[list[int]], weights: list[int]) -> int:
      if n == 0:
          return 0
      if n == 1:
          return max(0, weights[0])
      
      adj = [[] for _ in range(n)]
      for u, v in edges:
          adj[u].append(v)
          adj[v].append(u)
          
      order = [0] * n
      parent = [-1] * n
      visited = [False] * n
      
      # BFS to get topological order
      visited[0] = True
      head = 0
      tail = 1
      order[0] = 0
      
      while head < tail:
          u = order[head]
          head += 1
          for v in adj[u]:
              if not visited[v]:
                  visited[v] = True
                  parent[v] = u
                  order[tail] = v
                  tail += 1
                  
      # dp[u][0] = max weight in subtree u if u is NOT chosen
      # dp[u][1] = max weight in subtree u if u IS chosen
      dp0 = [0] * n
      dp1 = [0] * n
      
      for i in range(n):
          dp1[i] = weights[i]
          
      for i in range(n - 1, -1, -1):
          u = order[i]
          # In case u has negative weight, choosing u gives weights[u] plus children's not-chosen dp
          p = parent[u]
          if p != -1:
              dp0[p] += max(dp0[u], dp1[u])
              dp1[p] += dp0[u]
              
      ans = max(0, dp0[0], dp1[0])
      return ans

• #1OpenAI GPT-5.3-Codexहल किया गया · 11 में से 11 टेस्ट्स पासजवाब का समय 3.5 s · रनटाइम 1.6 s · $0.0049

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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 808 ms⏱ 782 ms
  कोड

  from typing import List
  
  def max_independent_set(n: int, edges: List[List[int]], weights: List[int]) -> int:
      if n <= 0:
          return 0
      g = [[] for _ in range(n)]
      for u, v in edges:
          g[u].append(v)
          g[v].append(u)
  
      parent = [-1] * n
      order = []
      stack = [0]
      parent[0] = 0
  
      while stack:
          u = stack.pop()
          order.append(u)
          for v in g[u]:
              if parent[v] == -1:
                  parent[v] = u
                  stack.append(v)
  
      dp0 = [0] * n  # best if node not chosen
      dp1 = [0] * n  # best if node chosen
  
      for u in reversed(order):
          take = weights[u]
          skip = 0
          for v in g[u]:
              if v == parent[u]:
                  continue
              take += dp0[v]
              skip += dp0[v] if dp0[v] >= dp1[v] else dp1[v]
          dp1[u] = take
          dp0[u] = skip
  
      ans = dp0[0] if dp0[0] >= dp1[0] else dp1[0]
      return ans if ans > 0 else 0

• #1Mistral Devstral 2 2512हल किया गया · 11 में से 11 टेस्ट्स पासजवाब का समय 1.4 s · रनटाइम 1.9 s · $0.0007

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

  ✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.0 s⏱ 830 ms
  कोड

  def max_independent_set(n: int, edges: list[list[int]], weights: list[int]) -> int:
      from collections import deque
  
      if n == 0:
          return 0
  
      adj = [[] for _ in range(n)]
      for u, v in edges:
          adj[u].append(v)
          adj[v].append(u)
  
      parent = [-1] * n
      root = 0
      q = deque([root])
      parent[root] = -1
      order = []
      while q:
          u = q.popleft()
          order.append(u)
          for v in adj[u]:
              if parent[v] == -1 and v != parent[u]:
                  parent[v] = u
                  q.append(v)
  
      dp_include = [0] * n
      dp_exclude = [0] * n
  
      for u in reversed(order):
          include = weights[u]
          exclude = 0
          for v in adj[u]:
              if v == parent[u]:
                  continue
              include += dp_exclude[v]
              exclude += max(dp_include[v], dp_exclude[v])
          dp_include[u] = include
          dp_exclude[u] = exclude
  
      return max(dp_include[root], dp_exclude[root])

• #4Z.ai GLM 5.3हल नहीं हुआ · 11 में से 4 टेस्ट्स पासजवाब का समय 2.7 s · रनटाइम 1.3 s · $0.0008

  ✗	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])अपेक्षित 5प्राप्त 1	<1 ms
  ✗	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])अपेक्षित 6प्राप्त 5	<1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✗ गलत उत्तर✗ गलत उत्तर✗ गलत उत्तर⏱ गलत उत्तर⏱ गलत उत्तर
  कोड

  def max_independent_set(n: int, edges: list[list[int]], weights: list[int]) -> int:
      if n == 1:
          return max(0, weights[0])
      adj = [[] for _ in range(n)]
      for a, b in edges:
          adj[a].append(b)
          adj[b].append(a)
      taken = [False] * n
      parent = [0] * n
      order = [0] * n
      order[0] = 0
      taken[0] = True
      head = 0
      cnt = 1
      while head < cnt:
          u = order[head]
          head += 1
          pu = parent[u]
          for v in adj[u]:
              if v != pu:
                  parent[v] = u
                  order[cnt] = v
                  cnt += 1
                  taken[v] = True
      dp_incl = [0] * n
      dp_excl = [0] * n
      dp_skip = [0] * n
      for i in range(n - 1, -1, -1):
          u = order[i]
          wi = weights[u]
          inc = wi if wi > 0 else 0
          if taken[u]:
              if inc:
                  dp_incl[u] = inc + dp_skip[u]
              else:
                  dp_incl[u] = 0
              dp_excl[u] = dp_skip[u]
          else:
              best = 0 if dp_incl[u] > 0 else dp_incl[u]
              if dp_excl[u] > best:
                  best = dp_excl[u]
              if inc:
                  v = inc + dp_skip[u]
                  if v > best:
                      best = v
              dp_skip[parent[u]] += best if best > 0 else 0
      r = 0
      if dp_incl[order[0]] > r:
          r = dp_incl[order[0]]
      if dp_excl[order[0]] > r:
          r = dp_excl[0]
      return r

  दूसरा प्रयास

  हल नहीं हुआ · 11 में से 4 टेस्ट्स पासजवाब का समय 4.2 s · $0.0007

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

  ✗	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])अपेक्षित 5प्राप्त 7	<1 ms
  ✗	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])अपेक्षित 6प्राप्त 11	<1 ms

  ✓ <1 ms✓ <1 ms✗ गलत उत्तर✓ <1 ms✓ <1 ms✗ गलत उत्तर✗ गलत उत्तर⏱ गलत उत्तर⏱ गलत उत्तर

  कोड

  def max_independent_set(n: int, edges: list[list[int]], weights: list[int]) -> int:
      if n == 1:
          return max(0, weights[0])
      adj = [[] for _ in range(n)]
      for a, b in edges:
          adj[a].append(b)
          adj[b].append(a)
      parent = [-1] * n
      order = [0] * n
      cnt = 1
      head = 0
      while head < cnt:
          u = order[head]
          head += 1
          for v in adj[u]:
              if v != parent[u]:
                  parent[v] = u
                  order[cnt] = v
                  cnt += 1
      incl = [0] * n
      excl = [0] * n
      best = [0] * n  # best contribution to parent: max(incl, excl)
      for i in range(n - 1, -1, -1):
          u = order[i]
          w = weights[u]
          take = w + excl[u] if w > 0 else excl[u]
          if w > 0 and w + excl[u] > take:
              take = w + excl[u]
          incl[u] = (w + excl[u]) if w > 0 else excl[u]
          if incl[u] < excl[u] + (w if False else 0):
              pass
          # excl[u] already accumulated sum of best children
          incl_val = w + excl[u] if w > 0 else excl[u]
          b = incl_val if incl_val > excl[u] else excl[u]
          if b < 0:
              b = 0
          best[u] = b
          p = parent[u]
          if p >= 0:
              excl[p] += b
      root = order[0]
      res = max(incl[root], excl[root], 0)
      return res

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