need guidance in sums in triangle problem

hi i have been working on sums in triangle problem


i don’t want to see the solutions
i just want to know the basic approach behind it so that i can solve it myself
please tell me how should i approach this problem

This should help you

It is said you need to start at the top of the triangle (where there is only one number) and keep moving to the number directly below or to the right until you reach the last row…

Take as an example the triangle:

1
1 2
9 2 3

If you want to maximize the sum by only moving right or down, is it clear to you that you should follow the path 1 -> 1 -> 9?

Note that 1 is not the maximum number you can choose on the 2nd row, but, it is the number that will “give you acess” to the number 9 on the third row, number which you will need to use if you want to reach the maximum sum…

This idea probably could lead us to use some sort of depth-first search and/or recursion… It turns out that for a triangle with as many rows as 100, there are 2^99 routes altogether… That would take you some billion years to check all of them if you could check one trillion of routes per second!!

So, we already know it would be good if we somehow knew in advance that we need to use number 9 on our solution without checking all possible routes… That can be done by using a bottom up approach instead of a top down one…

Let’s list all the possible sums we can make with the last 2 rows (I am starting from right to left here):

using the 3 and 2 on last row we can have:

3+2 or 2+2 (summing them with the 2 on 2nd row, as it directly above or one place to the right);

Using the 9 and the 2 we get:

2+1 or 9+1

So, as you see two interesting things happened:

We used the same number (2) twice (one time for each of the 2 neighbouring numbers on the same row) and we also managed to obtain all 4 results:

5 or 4 for the 1st pair
3 or 10 for the 2nd pair

This suggests that as we are using some values to repeat calculations, we can use recursion with memoization to solve the problem fast, and that’s what we will do up to a point, let’s see:

We now know that the 2 maximum values we can obtain from the last rows are 5 and 10, so we replace these values on second row, and eliminate the third one completely, to get the new triangle:

1
10 5

From here, it’s easy to see that the maximum sum is 11.

This approach works because we actually follow a down or to the right approach as required… Instead of starting at the top and waste all the time computing useless sums, by starting at the bottom and storing the maximum values we are “implicitly” removing lots of unnecessary values…

Hope I could help,

Bruno

25 Likes

thanks alot @kuruma for giving so much time for this problem and helping me with such a nice and simple illustration
i now managed to solve it successfully
thanks alot
:slight_smile:

1 Like

can anyone help pls. ideone accepts my answer; however, i am getting TLE answer from codechef for my c++ solution: http://ideone.com/AhNRnV

#include <iostream>
using namespace std;

int main() {
 // your code goes here
 int a, b, arr[98][98]={0}, i, j, count=0, i_temp, j_temp, max, max1, max2;
 cin>>a;
 while(a--) {
  arr[98][98]=0;
  cin>>b;
  count=0;
  for(i=0; i<b; i++) {
   if(count<b) count++;
   for(j=0; j<count; j++) {
    cin>>arr[i][j];
   }
  }
  i_temp=i, j_temp=j;
  for(; i>0; i--) {
  	j=j_temp;
  	for(; j>0; j--) {
  		max1=arr[i][j-1]+arr[i-1][j-1], max2=arr[i][j]+arr[i-1][j-1];
  		if(max1>max2) max=max1; else max=max2;
  		arr[i-1][j-1]=max;
  	}
  	j_temp=j_temp-1;
  }
  cout<<arr[0][0]<<endl;
  //arr[100][100]=0;
 }
 return 0;
}

@kuruma,
@garakchy,
@bugkiller, @junior94, @vineetpaliwal, @anton_lunyov, @betlista, @cyberax

i have implemented a top-bottom approach , verified may test cases but still i get wa

# include <iostream>
# include <stdio.h>
# include <math.h>
# include <list>
# include <algorithm>
typedef long long int  LL;
using namespace std;
LL arr[99][99], val_arr[99][99]={0};
LL value (int x,int y){
	if((!arr[x-1][y])&&(!arr[x-1][y-1])){
		return arr[x][y];
	}
	else if ((!arr[x-1][y])){
		return (arr[x][y]+val_arr[x-1][y-1]);
	}
	else if ((!arr[x-1][y-1])){
		return (arr[x][y]+val_arr[x-1][y]);
	}
	else{
		return ( val_arr[x-1][y-1]>=val_arr[x-1][y]? (arr[x][y]+val_arr[x-1][y-1]):(arr[x][y]+val_arr[x-1][y]) );
	}
}
int main(){
	int t;
	scanf("%d",&t);
	for(int i=0; i<t; i++){
		int n;
		scanf("%d",&n);
		for(int j=0; j<n; j++){
			for(int k=0; k<=j; k++){
				scanf("%lld",&arr[j][k]);
				val_arr[j][k]=value(j,k);
			}
		}
		LL ans=-1;  
		for(int j=0; j<n; j++){
			if(val_arr[n-1][j]>ans){
				ans=val_arr[n-1][j];
			}
		}
		printf("%lld\n", ans);

	}
}

http://ideone.com/dLlJKE

Those looking for Top Bottom approach (not the fast one).


I solved this problem using top-bottom approach first. Got TLE. Didn’t want it to go waste, thus sharing it.

#include<iostream>
#include<cmath>
using namespace std;

int t,n,i;
short inp[5050] = {};

int sum_trian(int row,int column,int parent) {
int index = ( (row-1)*row ) / 2 + column - 1;
if( row==n )
	return (parent+inp[index]);
parent += inp[index];
return max(sum_trian(row+1,column,parent), sum_trian(row+1,column+1,parent));
}

int main() {
cin >> t;
while(t>0) {
	cin >> n;
	for(i=0;i<(n*(n+1)/2);i++)
	cin>>inp[i];
	cout << sum_trian(1,1,0) << endl;
	t--;
}
return 0;
}
1 Like

#include <stdio.h>

int sumtria(int a[][100],int n,int p,int q);

int max(int a,int b);

int main()
{
int n,t,a[100][100],cost,i,j;

scanf("%d",&t);

while(t--)
{
   scanf("%d",&n);

   for(i=0;i<n;i++)

   for(j=0;j<=i;j++)

   scanf("%d",&a[i][j]);

   cost=sumtria(a,n,0,0);

   printf("%d",cost);

   printf("\n");
}
return 0;

}
int sumtria(int a[][100],int n,int p,int q)
{
int cost;

if(p==n-1)

return a[p][q];

else

cost=a[p][q]+(max((sumtria(a,n,p+1,q)),(sumtria(a,n,p+1,q+1))));

return cost;

}

int max(int d,int b)

{
if(d>b)

return d;

else

return b;

}

its a recursive approach still i get TLE error plz help me to modify my code so to get it AC

1 Like

i have the same problem in understanding the logic as mentioned by dabbcomputers
i guess it will not work correctly in that case

Hello @nishant_25,

It is my pleasure to help anyone who needs some help :slight_smile: This community has given me much more than I could have ever asked for, including new friends, new problem-solving skills and even the chance to set my own problems so that the best coders in the world can solve them :))

So, stick around, it’s worth so, so much :wink:

PS: If you want to know, after seeing your submission, I was able to understand how I could build an array to store the triangle in C++, so THANK YOU as well

3 Likes

ha ha
so i also helped you
its kinda funny
:slight_smile:

2 Likes

Very nicely explained. Thanks a ton! Dynamic Programming is proving tricky to master. I must’ve read a dozen tutorials already.

1 Like

Hello @niharika1k29_9,

It’s a pleasure to help!! I am glad you liked my post and I’m also learning it myself!! The more tutorials and/or editorials you read, the more you’ll learn :smiley:

I wish you the best of luck :wink:

One of the best explained analogy . Very easy to understand .Nice work ! Thanks a lot

1 Like

Thank you very much!!! :slight_smile:
Your acknowledgement means a lot to me :smiley:

Best regards,
Bruno

@kuruma thanks for your guidance. can i have your array c++ to store triangle pls. tnx

you can avoid initializing arr[98][98] to 0 apart from that i think everything is Ok

@infinitum still getting TLE. tnx anyway

Awesome :)…But i had to look up at your solution too also for implementation of your algorithm.:stuck_out_tongue:

Thank you very much! Very good explanation :slight_smile: