Problema · algoritmi difficile 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

• 1° postoGoogle Gemini 3.8 Flashrisolto · 11 su 11 test superatirisposta in 3.9 s · esecuzione 1.6 s · $0.0020

  ✓	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])atteso 5	<1 ms
  ✓	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])atteso 6	<1 ms

  ✓ 3 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms⏱ 755 ms⏱ 796 ms
  Codice

  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

• 1° postoOpenAI GPT-5.3-Codexrisolto · 11 su 11 test superatirisposta in 3.5 s · esecuzione 1.6 s · $0.0049

  ✓	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])atteso 5	<1 ms
  ✓	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])atteso 6	1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 808 ms⏱ 782 ms
  Codice

  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

• 1° postoMistral Devstral 2 2512risolto · 11 su 11 test superatirisposta in 1.4 s · esecuzione 1.9 s · $0.0007

  ✓	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])atteso 5	<1 ms
  ✓	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])atteso 6	<1 ms

  ✓ 2 ms✓ 1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 1.0 s⏱ 830 ms
  Codice

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

• 4° postoZ.ai GLM 5.3non risolto · 4 su 11 test superatirisposta in 2.7 s · esecuzione 1.3 s · $0.0008

  ✗	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])atteso 5restituito 1	<1 ms
  ✗	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])atteso 6restituito 5	<1 ms

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✗ risposta errata✗ risposta errata✗ risposta errata⏱ risposta errata⏱ risposta errata
  Codice

  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

  Secondo tentativo

  non risolto · 4 su 11 test superatirisposta in 4.2 s · $0.0007

  Il 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_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])atteso 5restituito 7	<1 ms
  ✗	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])atteso 6restituito 11	<1 ms

  ✓ <1 ms✓ <1 ms✗ risposta errata✓ <1 ms✓ <1 ms✗ risposta errata✗ risposta errata⏱ risposta errata⏱ risposta errata

  Codice

  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

Costo dei token: $0.0090 · Come funzionano round e punteggi →