Nearest Common Ancestors

[kaushik_acharya]

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

[brianfry713]

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.

[kaushik_acharya]

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)