Hello everyone, I need help with approaches to a tree problem I couldn’t solve.
Any ideas on how to solve this tree problem efficiently?
Here’s my approach using binary search.
If i read the question correctly on hackerrank,
The value of n is 105
then the problem can be solved in O(n^2*log(n)).
I designed approach which uses preorder traversal pattern to identify the structure of k_subtrees. I explained my approach using sample example given on hackerrank.
My approach basically uses unordered_map for hashing preorder pattern for every vertex for particular k logn times obviously using Binary search for answer concept.
Actually in photo i wrongly calculated complexity as n^3logn but its actually n^2logn if you see carefully
Hope to listen from you as fast as possible
I’m sorry that you had to read it like that. It’s actually 10^5 and not 105; they formatted it wrong. Also, you should’ve seen my binary search solution. We want an O(n lgn) or O(n \cdot lg^2n) solution.
So are you getting TLE or WA in some cases
TLE
Yaa, you are right, I could only get
57.14 points
with my approach
If you find any better solution, plz let me know