Trees and knapsack

Questions 1 to 5 of 8

1. 1. A teammate says the tree knapsack merge is O(n^2) because the tree has only n nodes. Which reason is the real one?

   Each node does a constant amount of work, so the total is O(n), and the n^2 bound is only a loose estimateAll merges happen at the root, so the root table of size n is rebuilt n timesMerging a table of size a with one of size b costs about a times b steps, and each pair of nodes is combined in exactly one merge, at their lowest common ancestor, so the pairs total at most n(n - 1) / 2The knapsack capacity is W, so the cost is n times W, which is O(n^2) only when W equals n
2. 2. You need the farthest weighted distance from every node of a tree, with n = 100000. Which method gives all the answers in O(n) total?

   Rerooting: one pass down that stores each subtree's best value, then one pass up that adds in the part of the tree above each nodeA full walk from each node, keeping the best answer, which is simple to writeSort the nodes by depth, then read each answer straight from the sorted listPick a random root and assume it is near the middle of the tree
3. 3. Binary splitting replaces a count c with 0/1 pieces of sizes 1, 2, 4 and so on, with the last piece taking what is left. How many pieces does a count of c = 37 need?

   Type a number.

4. 4. An AI tool split a count of c = 5 into the pieces 1, 2 and 4, then ran the 0/1 knapsack over them. The judge says it can take 7 copies of an item that only has 5. What is the fix?

   Use a bitset instead, because 0/1 knapsack cannot store a count of 5Run the loop upward, so that each piece can be reused in the same passUse the pieces 2, 4 and 8, which add up to 14 and cover more copiesCap the last piece at what is left, so the pieces are 1, 2 and 2, which add up to exactly 5
5. 5. Which statements about the bitset subset-sum method are true?

   Pick every answer that is true.

   It answers which totals from 0 to W can be reached exactly by some choice of itemsIt returns the largest total price that fits in the capacityEach shift and OR updates all reachable totals at once, with 64 bits in each machine wordIt can be used to find the best combination of prices, because it tracks the value of each choice