@Piyush: Yes, I got it now that you defined your terminology.
Dave
On Nov 5, 12:32 am, Piyush <piyushra...@gmail.com> wrote:
> sorry children of index i at level l should be
>
> a[i+l] and a[i+l+1] ( it is 0 index array and the level starts from 1 , 0
> level signifies no elements)
>
> lets take a simple example
> a[0]=1 has two children and (0+1) and (0+1 +1) i.e a[1] and a[2]
> for a[1] the children are at ( 1+2) and (1+2 +1) i.e. at a[3] and a[4]
> for a[3] the children are at (2+2) and (2+ 2 +1) i.e. at a[4] and a[5]
>
> I hope you got it now.
>
>
>
> On Fri, Nov 5, 2010 at 10:01 AM, Dave <dave_and_da...@juno.com> wrote:
> > @Piyush: Hmmm. Children of i = 0, l = 0 are a[0+0+1] and a[0+0+2].
> > Check.
> > Children of i = 0, l = 1 are not a[0+1+1] and a[0+1+2]; they are a[3]
> > and a[4].
> > Am I missing something?
>
> > Dave
>
> > On Nov 4, 11:00 pm, piyush rai <piyushra...@gmail.com> wrote:
> > > there is a better way to get a child of node at index i and level l
> > > The child will always be @ index (i+l+1) and (i+l+2) then solve
> > recursively
> > > keeping and array of length of level, top-down approach OR do a bottom up
> > > approach without using any extra memory.
>
> > > On Fri, Nov 5, 2010 at 9:01 AM, Dave <dave_and_da...@juno.com> wrote:
> > > > @juver++: Oops. Right you are! A corrected solution is just a little
> > > > more complicated. If the data is presented in an array as in the
> > > > previous posting, a[]={1,2,3,4,5,6,7,8,9,10} corresponding to the
> > > > triangle
> > > > 1
> > > > 2 3
> > > > 4 5 6
> > > > 7 8 9 10
> > > > then we let A(i,j) be the jth entry in the ith row, both 0-based, so
> > > > that in this example, A(2,1) = 5Then the array can be treated as an
> > > > implicit DAG (directed acyclic graph) where the children of A(i,j) are
> > > > A(i+1,j) and A(i+1,j+1). Using the correspondence that A(i,j) = a[i*(i
> > > > +1)/2+j)], you can traverse the DAG the same way I described
> > > > traversing the binary tree.
>
> > > > Dave
>
> > > > On Nov 4, 3:19 pm, "juver++" <avpostni...@gmail.com> wrote:
> > > > > You are wrong. It's not a binary tree. Cause multiple elements have
> > > > > adjacent childs.
> > > > > Right solution is to apply DP:
> > > > > dp[i][j] - maximum sum that is ends into i-th row and j-th column.
> > > > > Then make only 2 transitions to the (i+1)-th row.
> > > > > Complexity is n^2.
>
> > > > > On Nov 4, 7:50 pm, Dave <dave_and_da...@juno.com> wrote:
>
> > > > > > @Piyush: Treat the data as an implicit binary tree, with the
> > children
> > > > > > of a[i] being a[2*i] and a[2i+1] if a[] is a 1-based array, or
> > a[2*i
> > > > > > +1] and a[2*i+2] if a[] is a 0-based array. Traverse the tree and
> > > > > > accumulate the sum as you descend. When you reach the leaves, keep
> > > > > > track of the maximum sum and its path. When the traversal is
> > finished,
> > > > > > you will have your answer.
>
> > > > > > Dave
>
> > > > > > On Nov 4, 4:47 am, Piyush <piyushra...@gmail.com> wrote:
>
> > > > > > > Given an array of integers. Imagine it as a pyramid as below:
> > > > > > > a[]={1,2,3,4,5,6,7,8,9,10}
> > > > > > > 1
> > > > > > > 2 3
> > > > > > > 4 5 6
> > > > > > > 7 8 9 10
> > > > > > > find a path from level 1 to last level such that the sum is
> > maximum.
> > > > > > > The path is such that its children should be reachable.
> > > > > > > Eg:
> > > > > > > 1,2,5,9 is a path
> > > > > > > 1,2,6,10 is not a path since 6 is not reachable from 2.
> > > > > > > The array is not sorted and numbers are random.- 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 algoge...@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > <algogeeks%2bunsubscr...@googlegroups.com>
> > > > .
> > > > For more options, visit this group at
> > > >http://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 algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://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 algoge...@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.
