Trees, Dynamic Programming
Given N games n form of tree where ith game can be bought if ans only if it’s parent game is bought, calculate for each 1 \leq i \leq N the number of friends our lonely vijju can gain by buying i games. A game cannot be a requirement for more than three games.
SUPER QUICK EXPLANATION
Notice anything strange about constraints, it's the constraint on outdegree of every vertex.
Use Dynamic Programming programming to compute Maximum number of friends Vijju can gain, by buying K games in subtree of node X.
For DP transition, we can rely on the constraint on outdegree and check every combination (i,j,k) which sums to K-1, so that we choose i games in subtree of first child, j games in subtree of second child and (K-i-j-1) games in third child's subtree and take the maximum of all.
Let DP[X][j] represent the maximum number of friends Vijju can get if he can buy j game sin subtree of X. Clearly, the answer to our problem is DP[i] \forall 1 \leq i \leq N.
Now, How to compute DP[X][i] If you have computed DP[u][j] \forall 0\leq j \leq N for every child u of node X?
Turns out, there is a simple way, by checking each combination of number of games given to each child, we can take the maximum of all those.
Formally, If Node U is leaf or we have to select only 1 node, return number of friends Vijju can make by buying current game.
Otherwise, If Node U is a leaf, return Friends gained by this game+ Maximum number of friends Vijju can make in subtree of child of U, with K-1 games.
When Node has 2 children, we can check each combination (i,j) such that i+j equals K-1 and return Friends gained by current game + max friends Vijju make by u games in first subtree and j games in second child’s subtree.
I would like if you figure out the case where node has 3 children, though it is given below.
Click to view
Check every combination of (i,j,k) such that i+j+k equals K-1 and return friends gained by current game + max friends gained by i games in subtree of first child, j games in subtree of second child, and k games in subtree of third child.
All these combinations can be checked brutely and then
Just print the answer, what are you waiting for!!
Time complexity: O(N*K^3) in worst case, though It gets amortized to a much lower value. If anyone can find a stricter upper bound , pleas share.
Check a simpler version of this problem: HPOWER, which inspired me to write this problem.
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to share your solution or ask any doubts.