SUMTRIAN - "Sums in a triangle" Explanation(trivial)

editorial
, , , , , ,
1

warning: at the time this post was shared, contest was being held. if you spot any similarity between live contest questions and this post, feel free to remove it, though author of this post has not intended any cheating, yet.

Codechef SUMTRIAN - Sums in a triangle: http://www.codechef.com/problems/SUMTRIAN

Codechef SUMTRIAN - Sums in a triangle editorial: http://discuss.codechef.com/questions/4557/need-guidance-in-sums-in-triangle-problem#4561

Codechef SUMTRIAN - Sums in a triangle solution: http://ideone.com/1Qb7Ce

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

long long int a[105][105]={0};

int main() {
    int n, m;
    scanf("%d", &n);
    while(n--) {
        scanf("%d", &m);
        for(int i=0; i<m; i++) for(int j=0; j<=i; j++) scanf("%lld", &a[i][j]);
        for(int i=m-2; i>=0; i--) for(int j=i; j>=0; j--) {
            if(a[i+1][j+1]>a[i+1][j]) a[i][j]+=a[i+1][j+1];
            else a[i][j]+=a[i+1][j];
        }
        printf("%lld\n", a[0][0]);
        for(int i=0; i<105; i++) for(int j=0; j<105; j++) a[i][j]=0;
    }
    return 0;
}

note: use dp(dynamic programming), start from the right bottom of the triangle, and the loop from right to left. for each specific cell(a[i][j]), try to find which cell, directly below(a[i+1][j]) or directly below and one place to the right(a[i+1][j+1]), is bigger to add to current one(a[i][j]). when all looping and summing up finishes just print the value of top cell(a[0][0]), because that cell will represent the maximum possible sum of triangle.

1 Like
2

Editorial is not available but a small tutorial has posted already by Kuruma :

http://discuss.codechef.com/questions/4557/need-guidance-in-sums-in-triangle-problem#4561

2 Likes
3

use this recursion for your dp:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+arr[i][j];
if(i==n-1)sol=max(sol,dp[i][j]);

print sol at the end. This will do.