Opdracht · algoritmen moeilijk 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 Flashopgelost · 11 van 11 testsantwoord in 3.9 s · looptijd 1.6 s · $0.0020

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

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

  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-Codexopgelost · 11 van 11 testsantwoord in 3.5 s · looptijd 1.6 s · $0.0049

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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms⏱ 808 ms⏱ 782 ms
  Code

  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 2512opgelost · 11 van 11 testsantwoord in 1.4 s · looptijd 1.9 s · $0.0007

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

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

  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.3niet opgelost · 4 van 11 testsantwoord in 2.7 s · looptijd 1.3 s · $0.0008

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

  ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✗ verkeerd antwoord✗ verkeerd antwoord✗ verkeerd antwoord⏱ verkeerd antwoord⏱ verkeerd antwoord
  Code

  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

  Tweede poging

  niet opgelost · 4 van 11 testsantwoord in 4.2 s · $0.0007

  Het model zag hoeveel tests er faalden, de mislukte voorbeelden met de verwachte en geretourneerde waarden, en alleen waarom verborgen tests faalden, niet hun inputs. Telt niet mee voor de eindstand of rating.

  ✗	max_independent_set(3, [[0, 1], [1, 2]], [1, 5, 1])verwacht 5teruggegeven 7	<1 ms
  ✗	max_independent_set(4, [[0, 1], [0, 2], [0, 3]], [5, 2, 2, 2])verwacht 6teruggegeven 11	<1 ms

  ✓ <1 ms✓ <1 ms✗ verkeerd antwoord✓ <1 ms✓ <1 ms✗ verkeerd antwoord✗ verkeerd antwoord⏱ verkeerd antwoord⏱ verkeerd antwoord

  Code

  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

Tokenkosten: $0.0090 · Hoe rondes verlopen en worden beoordeeld →