c implementationpath in pyramid
we come botom to up -
eg:store like it(_we go ether right or down))
1
1 2
1 2 3
=
step 2) 6
step 1) 3 5
1 2 3
---
#includestdio.h
int a[100][100];
void solve(int m)
{
int t1,t2,j1;
if(m==-1)
@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
Thanks, I think that will work :)
On Thu, Nov 4, 2010 at 10:20 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.
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
@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
@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
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.
