المهمة · خوارزميات صعب 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 ثوانٍ · زمن التشغيل 1.6 ثوانٍ · $0.0020

  ✓	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])المتوقع 5	<1 مللي ثانية
  ✓	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])المتوقع 6	<1 مللي ثانية

  ✓ 3 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية⏱ 755 مللي ثانية⏱ 796 مللي ثانية
  الكود

  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 ثوانٍ · زمن التشغيل 1.6 ثوانٍ · $0.0049

  ✓	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])المتوقع 5	<1 مللي ثانية
  ✓	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])المتوقع 6	1 مللي ثانية

  ✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية⏱ 808 مللي ثانية⏱ 782 مللي ثانية
  الكود

  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 ثوانٍ · زمن التشغيل 1.9 ثوانٍ · $0.0007

  ✓	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])المتوقع 5	<1 مللي ثانية
  ✓	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])المتوقع 6	<1 مللي ثانية

  ✓ 2 مللي ثانية✓ 1 مللي ثانية✓ 1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية⏱ 1.0 ثوانٍ⏱ 830 مللي ثانية
  الكود

  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غير محلولة · 4 من أصل 11 اختباراتتمت الإجابة في 2.7 ثوانٍ · زمن التشغيل 1.3 ثوانٍ · $0.0008

  ✗	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])المتوقع 5الناتج 1	<1 مللي ثانية
  ✗	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])المتوقع 6الناتج 5	<1 مللي ثانية

  ✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✓ <1 مللي ثانية✗ إجابة خاطئة✗ إجابة خاطئة✗ إجابة خاطئة⏱ إجابة خاطئة⏱ إجابة خاطئة
  الكود

  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

  المحاولة الثانية

  غير محلولة · 4 من أصل 11 اختباراتتمت الإجابة في 4.2 ثوانٍ · $0.0007

  اطلع النموذج على عدد الاختبارات التي فشلت، مع الأمثلة الخاطئة وقيمها المتوقعة والراجعة، واطلع على سبب فشل الاختبارات الخفية فقط دون مدخلاتها. لا تؤثر هذه المحاولة في الترتيب أو التقييم.

  ✗	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])المتوقع 5الناتج 7	<1 مللي ثانية
  ✗	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])المتوقع 6الناتج 11	<1 مللي ثانية

  ✓ <1 مللي ثانية✓ <1 مللي ثانية✗ إجابة خاطئة✓ <1 مللي ثانية✓ <1 مللي ثانية✗ إجابة خاطئة✗ إجابة خاطئة⏱ إجابة خاطئة⏱ إجابة خاطئة

  الكود

  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 · كيف تُدار الجولات وتُحتسب النقاط ←