### MDantas's blog

By MDantas, 7 years ago, ,

Hey, does anyone knows how to solve this problem ?

I'm doing some sort of Dynamic Programming on Trees, assuming that the answer when M > 2 is always the 'same'. So my DP is the follow:

• DP[ has_fruit ][ node ][ K ]: What's the minimum answer when the subtree rooted at 'node' has exactly K nodes on the first group and the 'node' K has a fruit on it or doesn't have a fruit on it.

So I go down recursively on the tree calculating it for every node from the leaves to the root. And to compute DP[ has_fruit ][ node ][ K ], I'm using another DP that is very similar to the Knapsack DP.

Well, I'm sick and tired of getting WA's, so I decided to ask if anyone of you have already solved this one. My code: http://pastie.org/private/6gl337rrzkue0cxzokda

• -4

 » 7 years ago, # |   +6 In your main method, the condition to check for impossibility is wrong, check it again. The root must always be chosen by the boss head. In the solve2() method, you should be calling solve2(), not solve().
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I'd never have found such a mistake. Thanks