subramanian.ganapathy86
BAN USERBFS, which does a level order traversal. while inserting in the queue use std::pair< Node *, int > rather than the NODE* alone, this would give us the level of the currently de-queued node and enable us to calculate the next level for its children
- subramanian.ganapathy86 January 05, 2012Elegantly done using DP:
maintain OPT( node, k ) for each node such that OPT( node, k ) = true if some path starting from this node has the sum k. compute from Bottom up from leaf upwards
i.e. OPT( node, k ) = true if OPT( node->left, k - node->value ) = true || OPT( node->right, k - node->value ) = true. O(nk)
DFS whenever we color a node black( having visited all its children ), insert it to the tail of a linked list O(1 ) if tail ptr is available.
- subramanian.ganapathy86 January 05, 20121) Find LCA { Easy to do in O(lg n ) if you have a visited bit with each node in the tree }
2) from LCA print all nodes until we reach m.
3) Print right subtree of m.
4) From LCA print all nodes, until we reach n.
5) Print Left subtree of n.
Desginate each line by a 2-tuple {startpt, endpt}
Sort by startpt.
Sort by end pt.
Do a O(n^2) forward pass of the startpt sorted set to find if pt i intersect with any of pts 0 <= j < i. If there are intersections save them in a set.
Do a O( n^2 ) reverse pass of the end pt sorted set to find if pt i intersect with any of pts i < j <= n-1. As before save any intersections in a set
Observation a triangle is possibly formed if set 1 has members like {1,2} while set 2 has members like {2,3}. So for element in set 1 do a scan of set 2 searching for these matches and then checking if they form a valid triangle.
O(n^2) , i think we can make the last step nlg n but creating sets 1 and 2 require n^2.
Seen a similar problem before, as Eugene pointed out might be multi threading issue or might be the addition of printf changes the offsets in the text region such that the crashing instruction which might not actually be an instruction is not picked. I encountered this problem when one of the libraries was built with a different macro while my application had that macro on. But Eugene made a good point, the straight forward is that only.
- subramanian.ganapathy86 January 05, 2012