LONVIJJU - EDITORIAL

PROBLEM LINK:

Practice
Contest

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. :slight_smile:

But what if game X requires game Y to be bought and game Yrequires game Z to be bought and game Z requires game X to be bought ?
How is the graph a tree then?

//