PROBLEM LINK:
Setter: Abhishek Pandey
Tester: Taranpreet Singh
Editorialist: This person
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Trees, Dynamic Programming
PROBLEM:
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.
EXPLANATION
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[1][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!!
Complexity:
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.
Related Problem
Check a simpler version of this problem: HPOWER, which inspired me to write this problem.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Feel free to share your solution or ask any doubts. 