I recently gave a contest a contest hosted by MNIT on codechef. There was a question -- (https://www.codechef.com/INSQ2016/problems/INSQ16C)
It basically gives a complete binary tree and q queries and in the worst case you would have to traverse the complete binary tree q times.
My question is what is the time complexity to traverse a complete binary tree with n nodes, is it O(n) ( because there are n nodes to visit) or is it O(logn) because the height of that tree is logn.
The constraint on number of nodes is 10^5 and number of queries is 10^5 as well.
My solution which is basically( queries * time for tree traversal) passes in the given time.But I want to ask, is it because of weak test cases(which I suspect, is really the case!) or was it really correct?
My solution — (https://www.codechef.com/viewsolution/11367435)
Can anybody clear this up for me?Thanks
Good day to you!
If I understand your code well, then you are traversing whole "subtree".
This kind of traversal costs O(N).
Even thought, there are some "breaks":
A) If the answer is false, it will "break" sooner
B) Each "next" depth the query target makes the traversal lesser than half (meaning if the target of query would be "random node" with equal/semi-equal probability, the task WILL NOT TLE)
So in mine opinion (and I might be wrong), your solution works fine for average test-case BUT in worst case it shall TLE (and in my opinion the WC shall have been there)
So my verdict is Weak Test-cases
Here is generator which shall TLE your solution (I hope it is correct) — I took random solution from AC, and it run 0.35s in locale! (your solution ran too long so I killed it)
Good Luck & Have Nice day
Thanks for the help!
(vishal mode)aeeeeeeeeeeeee TLE....hunhhhhhh