atom0410's blog

By atom0410, history, 4 years ago, In English

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:

  1. Find $$$sum$$$ for all nodes, where $$$sum$$$ for a node denotes the sum of values of all its children.

Tree
($$$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.

Code

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
  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Here's the case I found:

5 2
1 -2 -2 3 -2
1 2
2 3
2 4
2 5

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.