Kumar think of the tree like this : d[node] is the minimum days required for tree rooted at 'node' to be solved. if node is a leave then the answer is zero. Otherwise suppose 'node' has k children, and values to 'node's children are like this d1 >= d2 >= ... >= dk then the answer for 'node' ( d[node] ) is max(d1 + 1, d2 + 2, ... , dk + k) I can not prove it here for you, but you can check it on an arbitrary tree.
By the way, Where did you get this problem? On Fri, Nov 8, 2013 at 8:47 AM, kumar raja <[email protected]> wrote: > I forgot to mention that the tree is n-ary tree, it need not be a binary > tree. So what is the approach ? > > > On 7 November 2013 01:04, Don <[email protected]> wrote: > >> Atul, the depth is the important factor, not the number of nodes. >> If you always pass the message to the deeper subtree first, followed by >> the other subtree, you get the minimum number of rounds. >> >> The problem is to compute the required number of rounds. This can be done >> in a way similar to computing the depth of a tree. However, be careful to >> handle the case where the subtrees take an equal number of rounds. >> >> int numRounds(TreePtr t) >> { >> int result = 0; >> if (t) >> { >> int L = numRounds(t->left); >> int R = numRounds(t->right); >> if (L == R) result = R + 2; >> else result = 1 + max(L,R); >> >> } >> return result; >> } >> >> On Friday, November 1, 2013 1:49:33 AM UTC-4, atul007 wrote: >> >>> we can first count number of nodes in a subtree below each node.Now >>> transfer message to max(count(root->left),count->root->right); >>> >>> On 11/1/13, kumar raja <[email protected]> wrote: >>> > Suppose we need to distribute a message to all the nodes in a rooted >>> tree. >>> > Initially, only the root >>> > node knows the message. In a single round, any node that knows the >>> message >>> > can forward it >>> > to at most one of its children. Design an algorithm to compute the >>> minimum >>> > number of rounds >>> > required for the message to be delivered to all nodes. >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> Groups >>> > "Algorithm Geeks" group. >>> > To unsubscribe from this group and stop receiving emails from it, send >>> an >>> > email to [email protected]. >>> > >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > -- MeHdi KaZemI -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
