Problem with Sums in a triangle - C solution

general
,
1

I have solved the problem Sums in a triangle in C.

MY APPROACH:

I am using an array of 2 arrays named “row”. I am using one of them for reading in the current row and the other for previous row. Then I am adding the values from previous row to the current row according to the given rule.

PROBLEM THAT I AM FACING:

My answer is correct on my PC but not on codechef. Any corner cases that I am forgetting? Here’s my code and link to all of my submissions to this problem.

#include<stdio.h>
int main()
{
    int cases, rows, factor, factor2;
    int row[2][100];
    register int i, j, k;

    scanf("%d", &cases);
    for(i = 0; i < cases; i++)
    {
        scanf("%d", &rows);
        //Initializing both rows to 0
        for(j = 0; j < 100; j++)
            row[0][j] = row[1][j] = 0;

        for(j = 0; j < rows; j++)
        {
            factor = j % 2;
            factor2 = (j + 1) % 2;
            for(k = 0; k <= j; k++)
            {
                scanf("%d", &row[factor][k]);
                if(k == 0 )
                    row[factor][k] += row[factor2][k];
                else if(k == (j - 1))
                    row[factor][k] += row[factor2][k - 1];
                else
                {
                    if(row[factor2][k] > row[factor2][k - 1])
                        row[factor][k] += row[factor2][k];
                    else
                        row[factor][k] += row[factor2][k - 1];
                }
            }
        }
        factor = (rows + 1) % 2;
        factor2  = -1;
        for(k = 0; k < rows; k++)
            if(row[factor][k] > factor2)
                factor2 = row[factor][k];

        printf("%d\n", factor2);
    }
    return 0;
}
2

why don’t u use bottom up approach …
use simple recursive bottom up approach
//1 based indexing
suppse no of Row=N;
SCAN input in MATRIX[N+1][N+1];
for computation COMPUTE[N+1][N+1] // for processing
for Nth ROW COMPUTE[N][j]=MATRIX[N][j];
for ROW n-1 to 1
{

for j=1to ROW  
{
COMPUTE[ROW][j]=max(MATRIX[ROW][j]+COMPUTE[ROW+1][j],COMPUTE[ROW+1][j+1]+MATRIX[ROW][j]);
}
}

output = COMPUTE[1][1]

3

Before changing the approach I would like to know what is wrong in this code.

4

Your else if Condition is wrong
it shud be else if(k == j)

here is ur soln which got accepted:

link

I also added some debugging lines hope it helps :slight_smile:

1 Like
5

Thanks. This helped.

6

Now I have the working code I’ll answer your question as to why I am not using bottom up approach. Because I have no idea what that means. I am trying to follow your Pseudocode. Didn’t get it as of now. Any explanations would be helpful. I’ll comment if I understand this.