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.
