Can anyone give a clear solution for this question.
https://www.codechef.com/EXPP2019/problems/EXUND
1 Like
Basically, this is how I saw the problem,
One clear observation is,
- If a chip is placed in a node A, it is always better to move from that node to all its children’s.
WHY?
Because if a node has children, then it is of two cases (can be seen at least for this problem),
a). Has 1 children (In this case moving from that Node A to it’s only child, we maintain that ans = 1, we are not losing anything).
b). Has more than 1 children (Now we are moving the chips to it’s children and improvising the ans from ans = 1 to ans = number of childrens for Node A.) Again we did not lose anything.
From a),b) we clearly observe, that moving the chips from node to it’s children’s is a better step.
So, At K = 1, keep all the chips in the leaf nodes. Sum of leaf nodes will be the ans for K = 1 which is height 0 for each tree branch.
So, At K = 2, nodes which are height = 1, will be the count.
lllly, keep doing for all, K’s and return the answer.
Hope you got it.
1 Like
Can you please tell me what is wrong with my code? I followed the exact same approach of ‘chipping’ the leaves first. I maintained a parent array for every node and its corresponding number of children (nch). Whenever nch becomes zero, that means it becomes a leaf node. My code got WA for most of the hidden test cases. Cannot figure out the bug. My code: CodeChef: Practical coding for everyone.
Edge is not always top to bottom .It may be bottom to top .
case:
1
7 2
1 2
1 3
2 4
2 5
3 6
7 3
I followed the same approach bro. Can you please check my code once.
https://www.codechef.com/viewsolution/27255901. I’m getting runtime error.
Also can you share your code
I had made a tester code for this problem, it tells where your code went wrong. You can find it here:
I tried swapping a and b whenever a > b i.e, I always added the larger node in the adjacency list of smaller node.Still WA!
My solution is not clear, so cant share. use dfs to fill both array instead of loop.