Author: Kshitij Bhatla
Tester: Swapnil Saxena
Editorialist: Swapnil Saxena
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Dynamic Programming, Tree Linearization
PROBLEM:
From a tree consist of N nodes with each node containing an item. Select at most K items from the tree such that
-
The profit of an item decreases with each new unit of item purchased.
-
For any two selected items present at nodes ‘i’ and ‘j’, one should not be an ancestor of other in the tree.
QUICK EXPLANATION:
The problem can be thought of as a Knapsack problem with additional constraints. It can be solved by using Dynamic Programming once the tree is suitably represented. Also since the profit of the element decreases with each unit of item purchased, the number of units of a certain item is restricted. The problem can be solved by first linearizing the tree followed by using dynamic programming.
EXPLANATION:
The problem can be thought of a variant of Knapsack problem with two additional constraints.
-
The profit of an item decreases with each new unit of item purchased.
-
Once an item is selected, a certain set of items cannot be selected. More precisely, once an item is selected any item belonging to the subtree rooted at node, containing the item, cannot be selected.
The first constraint implies that the number of item of a single type that can be purchased is restricted to ceil(a/(b^2)) before the profit drops below negative.
The second constraint may prove to be a difficulty for formulating a dp solution but it can be solved using a suitable representation of the tree. Let’s linearize the tree, such that for any node u, all the nodes v in the subtree of u forms a contiguous subarray. This can be done using a preorder traversal of the tree starting the dfs at the root of tree.
Now the rest formulation is easy. For each item i, either one chooses not to purchase any unit of item i for the final set. Else one can select q units of item i, increasing the elements in the final set by q.
Let f(i, k) denotes the maximum profit achieved using items from [i, n] with less than or equal to k items. Clearly, using the above formulation
f(i, k) = max(f(i+1, k), f(i+childCount(i), k-q) + profit(i, q) for 1 <= q <= k) where profit(i, q) denotes cost of q units of item i.