Can someone tell me why my solution to problem EXUND is giving TLE for one test case.
My solution’s link: CodeChef: Practical coding for everyone
Basically, I am using level order traversal to create a parent array, and storing all leaves in a separate array. Then, using leaves array and parent array I am assigning minimum k required for each node to get at least one chip.
Thanks in advance.
1 Like
TC
Extend it for a tree of height N/2
1 Like
One of the testcases from the file you got TLE on is a broom. That is a chain of N/2 nodes and the rest N/2 connected to an endpoint of the chain. It is exactly the case mentioned by @aryanc403.
Your code’s complexity is the summation of heights of the leaves which in this case is O(N^2)