Link: https://www.hackerrank.com/challenges/tree-pruning
This question has been solved using DP by most of the users, but I was wondering if this could be solved using Greedy. I came up with an approach using Greedy, which failed most of the test cases. But I couldn't come up with a small counter case where Greedy won't work.
My Greedy Approach:
- Find $$$sum$$$ for all nodes, where $$$sum$$$ for a node denotes the sum of values of all its children.
($$$sum$$$ for nodes written in brackets)
2. Now get the subtree with minimum {sum, val}, where $$$val$$$ denotes value of node, and $$$sum$$$ is defined above. ({a, b} denotes a pair in C++).
3. if sum is positive break, without removing, else remove that subtree.
4. Go back to Step 1.
Above loop is run at most k times.
Any help in finding a small counter case, and why it won't work will be helpful.
Smallest Test Case for which the above approach failed on Hackerrank:
20 5
773581246 -348306003 -788117784 629111611 -142726426 241605607 418519531 -291199082 -453706450 -850635818 -641575760 453047217 -874946563 -257858612 927125122 860575225 -162713554 61368550 -262466871 361084678
2 1
3 2
4 2
5 1
6 3
7 2
8 1
9 6
10 7
11 8
12 1
13 7
14 10
15 3
16 14
17 14
18 15
19 17
20 3
Here's the case I found:
Your program outputs 1 but other AC Codes outputs 2. I'll update you more when I'm clear about why this is so.
Update: if you look at the subtree rooted at 2, it's sum is (-2 + -2 + -2 + 3) = -3, which is the most negative among all subtrees. If you remove it, you're left with node 1, hence your code's answer is 1.
However, you can instead spend 2 operations to remove nodes 3 and 5, which gives you the remaining nodes 1, 2, 4. The sum of weights in this case is 2.
Thank You very much, Got it.
Thank you sir, have been struggle with this for several days