Yeah, exactly. Just check for the one with the least height.
so you mean just using simple intime[] and exittime[] arrays?
I also got E,If you can help with the LCM one and your logic seems correct to me for D maybe there is some problem with the implementation
Yes. Let me finish implementing to check whether it is correct.
It is
yeah looks like i have done some mistake in LCA implementation. I will look into it myself
Can you brief your logic for simple LCM ?
I looked into all 6-7 star guys who got rank from 1 to 5, almost everyone has write O(n^2) solution. I don’t know how they know that it will pass under such constraints
Thats what I am not getting , but then is there a solution better than O(n^2)?
The intended solution was O(N+QK). Look at This comment. My first approach was naively checking if some node was ancestor of the other and that was worst-case O(N+NQ) and it TLEed. So O(N^{2}) solution passing is a surprise to me.
I was asking that for the LCM problem, all solutions look like O(n^2) to me
My bad, it’s really confusing here!!
Anyway, I’ve seen two types of solutions that passed LCM problem.
- Just check the adjacent. Which is completely wrong.
- Check for only the largest 100 or so distinct elements with the rest. Which is hard to argue! This doesn’t TLE as far as I think.
But if just bruteforce has passed then it’s really sad!!
Even E and F were easier than this one
I was doing this but it got TLE, basically I after finding node with minimum height, I cleared its daughters and did bfs downward from that min height node. If all k got reached, then I printed the min height node. But it is giving TLE, i guess its worst case O(NQ), how to improve this, without using the LCA method
I want to know the approach of Problem setter of this question…what he thought before setting this problem and what us has intended solution
First make a dfs order and calculate the in time and out time for all nodes.Then for each query
sort the given list of vertices twice, once in increasing order of their in time and other on decreasing out time. if in both the cases the first element is same then output that else -1.
This works because the godfather must be an ancestor of all nodes and hence should satisfy ancestor descendant relation with all the other nodes.
Like I said, you can use In time and Out time to tell if a node is an ancestor of the other or not. What you did will TLE on bamboo-like trees.
It’s a really easy trick and takes very little implementation: Here.
Basically you take note of when you are entering and exiting any node while dfs. You’ll enter the ancestor earlier than its children and leave later.
I guess a counter example for second approach would be and array like this:
(assume array is sorted in ascending)
(211 is a prime and so is 103)
[..., 103, 1\cdot 211, 2\cdot211, ..., 100\cdot211]
In this case the LCM cannot be larger than 103\times100\times211, can it
Oh you wrote compare 100 elements with rest, my bad, I thought compare 100 among themselves.