Nearest Common Ancestors

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
kaushik_acharya
New poster
Posts: 17
Joined: Thu Jul 28, 2005 3:05 pm
Location: Bangalore, India

Nearest Common Ancestors

Post by kaushik_acharya » Sat Jun 29, 2013 10:36 pm

Problem: http://poj.org/problem?id=1330
My solution got Time Limit Exceeded.
I am not able to figure out what I can do to imporve the solution.

My solution:
First read all the edges and keep making the tree i.e. after reading each input line assign the parent,child pointer.
Then for each of the two nodes for which we have to find out the nearest common ancestor:

Keep putting into vector its ancestor one by one till we reach the root.

Then to find out the nearest common ancestor, keep iterating the two vectors in a reverse iteration till the corresponding elements are same.
This should be O(n) time complexity.
Since we would be given only two nodes in the tree to compute nearest common ancestor, I didn't tried http://community.topcoder.com/tc?module ... onAncestor

Can anyone suggest what I can improve for my solution to get accepted?

Regards,
Kaushik
My experience with Fraudster khari

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Nearest Common Ancestors

Post by brianfry713 » Tue Jul 02, 2013 2:10 am

I'd have to see your code to know for sure where you are taking too much time.

What I did to get AC in 32MS was to mark a bool array of the nodes visited between the first integer whose nearest common ancestor is to be computed and the root. The iterate from the second integer toward the root until you find a node that has already been visited by the first integer.
Check input and AC output for thousands of problems on uDebug!

kaushik_acharya
New poster
Posts: 17
Joined: Thu Jul 28, 2005 3:05 pm
Location: Bangalore, India

Re: Nearest Common Ancestors

Post by kaushik_acharya » Wed Jul 03, 2013 6:16 pm

Thanks Brian for the reply. I got AC with 266MS
I misunderstood the reason for Time Limit Exceeded.
Even when we iterate back, it will be done in O(n) (for search of nearest common ancestor after the tree is created). So the solution shouldn't get rejected. And that's true as I got my solution accepted now.

The problem was in tree creation:

Code: Select all

template<typename T>
class TreeNode
{
	T elem_;
	TreeNode<T>* parent_;
	std::vector<TreeNode<T>* > vecChild_;
}

Code: Select all

template<typename T>
class Tree
{
	std::vector<TreeNode<T>* > vecTreeNode_; // This stores the nodes of the tree
}
For every input line i.e. intA, intB, I search for the nodeA, nodeB in vecTreeNode_ and inserting if not found. This cost me O(n^2).

Then I changed to:

Code: Select all

template<typename T>
class Tree
{
	typedef std::set<TreeNode<T>*,Comp<TreeNode<T>* > > SetTreeNode;
	SetTreeNode setTreeNode_;
}
Now it reduced to O(nlogn)
My experience with Fraudster khari

Post Reply

Return to “Algorithms”