Dave's code is good. Here is a more abstract way of thinking about
it. Maybe helpful?
Number the rows starting at the top with h=0, and the left i=0. Then
the parents of cup(h,i) are always cup(h-1,i-1) and cup(h-1,i). When
h<0, i<0 or i >h, the parent does not exist.
Let F(h, i) be the amount that has flowed in to cup(h,i) after L went
in at the top and let G(h, i) be the amount that has flowed out.
So note that what flowed out is either what flowed in minus C or else
nothing if less than C has flowed in. It's also zero if cup(h,i)
doesn't exist:
G(h,i) = { F(h, i) - C if 0 <= i <= h and F(h, i) > C
{ 0 otherwise
Now note that what flows in is equal to half of what flowed out of
each parent unless we have the top cup, which means L flowed in!
F(h, i) = { L if h = i = 0
{ 0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) otherwise
The answer we want is given by F. Dave's code is a nice
implementation of this DP.
On Feb 27, 5:23 pm, Dave <[email protected]> wrote:
> @Ashish: I didn't make any assumption that nothing comes from the
> left. Does my code give the wrong answer?
>
> Dave
>
> On Feb 27, 10:36 am, Ashish Goel <[email protected]> wrote:
>
>
>
>
>
>
>
> > Dave, why the assumption that nothing is coming from left side.
>
> > Every cup gets something from cup left above and right above itself when
> > they have something extra?
>
> > Best Regards
> > Ashish Goel
> > "Think positive and find fuel in failure"
> > +919985813081
> > +919966006652
>
> > On Mon, Feb 27, 2012 at 8:17 PM, Dave <[email protected]> wrote:
> > > // nothing coming in from the
> > > left
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
