Re: [algogeeks] Puzzle
one option cud be reverse the digits...i.e (bt the first n d last do not satisfy d pattern howeva) 93 , 14,34,54,94,15,35,35,55 an increment is applied to the last 4th no each tme... not very sure if its crckt... Regards, PAYAL GUPTA On Tue, Feb 28, 2012 at 12:48 PM, Kartik Sachan kartik.sac...@gmail.comwrote: I think logic is the difference is 2 2 4 2 2 2 8 so next will be 2 2 2 2 2 16 so ans will be 66 68 70 but first number 3 making some problem -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Puzzle
{39,41,43,45}incremented by 2 {49,51,53,55}incremented by 2 {64,?,?,?} first number in each set is considered as base number. 3 is for the number of numbers in each set other than base number. so in final set base number is 64 and other 3 numbers are incremented by 2. On Tue, Feb 28, 2012 at 1:48 PM, payal gupta gpt.pa...@gmail.com wrote: one option cud be reverse the digits...i.e (bt the first n d last do not satisfy d pattern howeva) 93 , 14,34,54,94,15,35,35,55 an increment is applied to the last 4th no each tme... not very sure if its crckt... Regards, PAYAL GUPTA On Tue, Feb 28, 2012 at 12:48 PM, Kartik Sachan kartik.sac...@gmail.com wrote: I think logic is the difference is 2 2 4 2 2 2 8 so next will be 2 2 2 2 2 16 so ans will be 66 68 70 but first number 3 making some problem -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Srikanth Reddy M (M.Sc Tech.) Information Systems BITS-PILANI -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: google question
0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h - 1, i+1) ) i am not clear why the parents of a cup in upper row are consecutive? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 10:43 AM, Gene gene.ress...@gmail.com wrote: G is just a helper function. You can in line this function and eliminate it. When you do this, you'll end up with F(h, i) = 0.5 * (l + r) where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else 0 and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0 Here l is the left parent's outflow and r is the right parent's. So you are always computing the h'th row in terms of the (h-1)'th. For many DPs this means you'll need 2 row buffers. In this one you only need 1 element back in the current row. You can save this element in a single variable and get by with one buffer. I.e. note l for a given value of i is always the previous value of r. And for i=0, l is always 0 because there is no left parent. So you end up with f[0] = L; // fill in the first row for (ih = 1; ih = h; ih++) { // loop thru rest of rows double l = 0; // left parent outflow at ii=0 is always 0. for (ii = 0; ii = ih; ii++) { // loop thru columns // new right parent outflow double r = (ii ih f[ii] C) ? f[ii] - C : 0; f[ii] = 0.5 * (l + r); l = r; // right parent is left of next row entry } } return (0 = i i = h) ? f[i] : 0; This is doing the same as Dave's code for all practical purposes. It's untested but ought to work. On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote: Gene, your DP is what i was thinking of but in code i could not coreleate G(h - 1, i - 1) + G(h - 1, i) part (: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote: G(h - 1, i - 1) + G(h - 1, i) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Pbm with rand() function
Use Mersenne Twister to generate 32-bit integers and do something like this: long long x = MT.gen(); x = (x32) + MT.gen(); Don On Feb 27, 5:58 pm, Prakash D cegprak...@gmail.com wrote: i've another doubt. what to do when I need to generate a random long long? On Mon, Feb 27, 2012 at 9:07 PM, Don dondod...@gmail.com wrote: For instance, if RANDMAX= 32768, then x = rand() % 2; is twice as likely to result in the value 10,000 as the value 15,000. This is because there are two output values from rand() which result in x=1 (1 and 3), but only one output value from rand() resulting in x=15000 (15000). For any case where the statistical quality of the pseudo-random stream is important, such as simulation, using the built-in rand() function is not a good idea. Use a pseudo-random algorithm with much longer period and better properties, such as Mersenne Twister. But if you are using rand, it is usually recommended to use the high order bits rather than the low order bits. Many implementations of rand() have cycles in the low bits which are much shorter than the period of the generator. He is one way to generate unbiased values of quality as good as the generator can provide: // Return pseudo-random integer in the range 0..n-1 int randRange(int n) { int result, div = RANDMAX / n; do { result = rand() / div; } while(result = n); return result; } Don On Feb 26, 10:10 am, karthikeya s karthikeya.a...@gmail.com wrote: RAND() func returns value between 1 to INTMAX, as we know. But when smone tries to find out value between 1 to N he takes remainder of o/p of RAND() with N and adds one..but isn't it wrong coz RAND() will generate numbers with equal probability between 1 and INTMAX but taking remainder can alter the prob. of generating numbers. e.g. INTMAX=50 N=30 RAND(50) gives numbers 1 to 30, then prob. will remain same but if it gives numbers 31 to 50, they'll be mapped to the numbers 1 to 20, which means probability of getting numbers 1 to 20 is more than the probability for 21 to 30. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group athttp://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Buying candy
Little Bob likes candy, and he wants to buy all the candy he can get for the smallest price. At the store there is a big table with candy arranged in an NxN grid. Each candy has a price, Pij where i is the row and j is the column in which the candy is located. The store owner gives Bob N tags numbered 1..N. Bob can place one tag at the top of each column indicating the piece of candy he will buy from that column. Bob is smart enough to realize that he should not always buy the least expensive candy. For example, consider this price grid: 1 20 5 50 In this case, buying the candy priced 1 would force him to buy the candy priced 50, for a total cost of 51. He is better off buying the second candy in the first column, allowing him to buy the first candy in the second column for a total price of 25. For a 2x2 case, considering all the possibilities is easy enough. There are only two choices. But as N increases, the number of ways to select N candies increases as N!, and Bob doesn't have time for an algorithm which requires more than polynomial time to execute. What algorithm should Bob use to buy N pieces of candy for the smallest cost? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Buying candy
@Don: Based on your example, there seems to be an unstated requirement that Bob can and must buy exactly one candy from each row and each column. This is an assignment problem (see en.wikipedia.org/wiki/ Assignment_problem), and can be solved in O(N^3) by the Hungarian Algorithm (see en.wikipedia.org/wiki/Hungarian_algorithm). Dave On Feb 28, 9:27 am, Don dondod...@gmail.com wrote: Little Bob likes candy, and he wants to buy all the candy he can get for the smallest price. At the store there is a big table with candy arranged in an NxN grid. Each candy has a price, Pij where i is the row and j is the column in which the candy is located. The store owner gives Bob N tags numbered 1..N. Bob can place one tag at the top of each column indicating the piece of candy he will buy from that column. Bob is smart enough to realize that he should not always buy the least expensive candy. For example, consider this price grid: 1 20 5 50 In this case, buying the candy priced 1 would force him to buy the candy priced 50, for a total cost of 51. He is better off buying the second candy in the first column, allowing him to buy the first candy in the second column for a total price of 25. For a 2x2 case, considering all the possibilities is easy enough. There are only two choices. But as N increases, the number of ways to select N candies increases as N!, and Bob doesn't have time for an algorithm which requires more than polynomial time to execute. What algorithm should Bob use to buy N pieces of candy for the smallest cost? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Buying candy
Yes, the tags constrain him to buy exactly one candy from each row and each column. There is a slightly better algorithm than Hungarian. Don On Feb 28, 11:33 am, Dave dave_and_da...@juno.com wrote: @Don: Based on your example, there seems to be an unstated requirement that Bob can and must buy exactly one candy from each row and each column. This is an assignment problem (see en.wikipedia.org/wiki/ Assignment_problem), and can be solved in O(N^3) by the Hungarian Algorithm (see en.wikipedia.org/wiki/Hungarian_algorithm). Dave On Feb 28, 9:27 am, Don dondod...@gmail.com wrote: Little Bob likes candy, and he wants to buy all the candy he can get for the smallest price. At the store there is a big table with candy arranged in an NxN grid. Each candy has a price, Pij where i is the row and j is the column in which the candy is located. The store owner gives Bob N tags numbered 1..N. Bob can place one tag at the top of each column indicating the piece of candy he will buy from that column. Bob is smart enough to realize that he should not always buy the least expensive candy. For example, consider this price grid: 1 20 5 50 In this case, buying the candy priced 1 would force him to buy the candy priced 50, for a total cost of 51. He is better off buying the second candy in the first column, allowing him to buy the first candy in the second column for a total price of 25. For a 2x2 case, considering all the possibilities is easy enough. There are only two choices. But as N increases, the number of ways to select N candies increases as N!, and Bob doesn't have time for an algorithm which requires more than polynomial time to execute. What algorithm should Bob use to buy N pieces of candy for the smallest cost?- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Buying candy
Dave's answer, the Hungarian Algorithm, is correct because it does meet the requirements of the problem. There is another algorithm called Jonker-Volgenant-Castanon (JVC) which can be proven to be faster both on average and in worst case, than the Hungarian Algorithm. Both solutions are sure to find the best solution, which is not true of any ad hoc or greedy algorithm. For years, the Munkres algorithm was the best known solution, but JVC is significantly faster than Munkres. Don On Feb 28, 11:39 am, Don dondod...@gmail.com wrote: Yes, the tags constrain him to buy exactly one candy from each row and each column. There is a slightly better algorithm than Hungarian. Don On Feb 28, 11:33 am, Dave dave_and_da...@juno.com wrote: @Don: Based on your example, there seems to be an unstated requirement that Bob can and must buy exactly one candy from each row and each column. This is an assignment problem (see en.wikipedia.org/wiki/ Assignment_problem), and can be solved in O(N^3) by the Hungarian Algorithm (see en.wikipedia.org/wiki/Hungarian_algorithm). Dave On Feb 28, 9:27 am, Don dondod...@gmail.com wrote: Little Bob likes candy, and he wants to buy all the candy he can get for the smallest price. At the store there is a big table with candy arranged in an NxN grid. Each candy has a price, Pij where i is the row and j is the column in which the candy is located. The store owner gives Bob N tags numbered 1..N. Bob can place one tag at the top of each column indicating the piece of candy he will buy from that column. Bob is smart enough to realize that he should not always buy the least expensive candy. For example, consider this price grid: 1 20 5 50 In this case, buying the candy priced 1 would force him to buy the candy priced 50, for a total cost of 51. He is better off buying the second candy in the first column, allowing him to buy the first candy in the second column for a total price of 25. For a 2x2 case, considering all the possibilities is easy enough. There are only two choices. But as N increases, the number of ways to select N candies increases as N!, and Bob doesn't have time for an algorithm which requires more than polynomial time to execute. What algorithm should Bob use to buy N pieces of candy for the smallest cost?- Hide quoted text - - Show quoted text -- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] thanx to all
hey Geeks thanx a lot .. for the valuable information in the discussions i got selected in Yatra.com (R n D profile) thanx a lot for the algorithms explained by to guys THANX A LOT :D:D:D:D -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] thanx to all
cool On Tue, Feb 28, 2012 at 9:22 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: hey Geeks thanx a lot .. for the valuable information in the discussions i got selected in Yatra.com (R n D profile) thanx a lot for the algorithms explained by to guys THANX A LOT :D:D:D:D -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] thanx to all
congo :) On Wed, Feb 29, 2012 at 5:30 AM, Varun Nagpal varun.nagp...@gmail.comwrote: cool On Tue, Feb 28, 2012 at 9:22 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: hey Geeks thanx a lot .. for the valuable information in the discussions i got selected in Yatra.com (R n D profile) thanx a lot for the algorithms explained by to guys THANX A LOT :D:D:D:D -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] thanx to all
congrats :) keep participating and keep learning. On Wed, Feb 29, 2012 at 9:19 AM, atul anand atul.87fri...@gmail.com wrote: congo :) On Wed, Feb 29, 2012 at 5:30 AM, Varun Nagpal varun.nagp...@gmail.comwrote: cool On Tue, Feb 28, 2012 at 9:22 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: hey Geeks thanx a lot .. for the valuable information in the discussions i got selected in Yatra.com (R n D profile) thanx a lot for the algorithms explained by to guys THANX A LOT :D:D:D:D -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] thanx to all
congrats :-) On Wed, Feb 29, 2012 at 10:56 AM, shady sinv...@gmail.com wrote: congrats :) keep participating and keep learning. On Wed, Feb 29, 2012 at 9:19 AM, atul anand atul.87fri...@gmail.comwrote: congo :) On Wed, Feb 29, 2012 at 5:30 AM, Varun Nagpal varun.nagp...@gmail.comwrote: cool On Tue, Feb 28, 2012 at 9:22 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: hey Geeks thanx a lot .. for the valuable information in the discussions i got selected in Yatra.com (R n D profile) thanx a lot for the algorithms explained by to guys THANX A LOT :D:D:D:D -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] puzzle
Ntn else is provided..?? On Feb 28, 2012 12:51 PM, Gaurav Popli abeygau...@gmail.com wrote: Given a sequance of natural numbers. Find N'th term of this sequence. a1=2, a2=4, a3=11, a4=36, a5=147, a6=778 ... ... ... ... aN. this is a coding quesn and O(n) soln is also welcome... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: [Combinatorics] count possible number of binary search trees, given number of nodes
@WgpShashank ++1 :) Thanks Ashu CSE , IITD On Tuesday, February 14, 2012 9:33:46 PM UTC+5:30, WgpShashank wrote: HI , consider that each value could be the root. Recursively find the size of the left and right subtrees. thats it . lets try for n=2 e.g. 1,2 there ways to select the root wither 1 or 2 , if u choose one , size of left subtree will be 0 size of right subtree will be 1 so , similarly if u choose 2 as root , size of left subtree will be 1 and size of right subtree will be 0 , so tottal no of BST will 2 . dats what * **( combinatorics says , either select one or leave it , try to next element ) ** *now try for n=3 e.g. 1,2,3 values how many bst can created then try to implement this algorithm , fell free to drop me message . if i missed something or any clarification *Thanks Shashank Mani Narayan Computer Science Engineering Birla Institute of Technology,Mesra ** Founder Cracking The Code Lab http://shashank7s.blogspot.com/; FB Page http://www.facebook.com/pages/Cracking-The-Code/148241881919895 Google+ http://gplus.to/wgpshashank Twitter https://twitter.com/wgpshashankhttps://twitter.com/#%21/wgpshashank Puzzled Guy @ http://ashutosh7s.blogspot.com** **FB Page http://www.facebook.com/Puzzles.For.Puzzled.Minds* . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/_PFiV3QvPIEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: google question
Well the OP is not clear. You could be right. I solved this problem once before, and there the glasses were arranged in a pyramid like they do at weddings in my country (this will only look right if you set the fixed-width font in Groups: U U U U U U U U U U U U U U U --- You pour in the wine at the top and each glass trickles down to the 2 below it. So in this version I assumed the OP meant the children were the ones below and to the right. I could be wrong. On Feb 28, 8:46 am, Ashish Goel ashg...@gmail.com wrote: 0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h - 1, i+1) ) i am not clear why the parents of a cup in upper row are consecutive? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 10:43 AM, Gene gene.ress...@gmail.com wrote: G is just a helper function. You can in line this function and eliminate it. When you do this, you'll end up with F(h, i) = 0.5 * (l + r) where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else 0 and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0 Here l is the left parent's outflow and r is the right parent's. So you are always computing the h'th row in terms of the (h-1)'th. For many DPs this means you'll need 2 row buffers. In this one you only need 1 element back in the current row. You can save this element in a single variable and get by with one buffer. I.e. note l for a given value of i is always the previous value of r. And for i=0, l is always 0 because there is no left parent. So you end up with f[0] = L; // fill in the first row for (ih = 1; ih = h; ih++) { // loop thru rest of rows double l = 0; // left parent outflow at ii=0 is always 0. for (ii = 0; ii = ih; ii++) { // loop thru columns // new right parent outflow double r = (ii ih f[ii] C) ? f[ii] - C : 0; f[ii] = 0.5 * (l + r); l = r; // right parent is left of next row entry } } return (0 = i i = h) ? f[i] : 0; This is doing the same as Dave's code for all practical purposes. It's untested but ought to work. On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote: Gene, your DP is what i was thinking of but in code i could not coreleate G(h - 1, i - 1) + G(h - 1, i) part (: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote: G(h - 1, i - 1) + G(h - 1, i) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.