You are not logged in. Please login at www.codechef.com to post your questions!

×

Problem with Sums in a triangle - C solution

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;
}

asked 21 Jun '13, 13:08

anshbansal's gravatar image

1★anshbansal
5191215
accept rate: 0%


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 :)

link

answered 21 Jun '13, 15:45

abbas's gravatar image

4★abbas
4118
accept rate: 28%

Thanks. This helped.

(21 Jun '13, 23:47) anshbansal1★

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]

link

answered 21 Jun '13, 13:30

selfcompiler's gravatar image

3★selfcompiler
10127
accept rate: 0%

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

(21 Jun '13, 14:07) anshbansal1★

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.

(21 Jun '13, 23:51) anshbansal1★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,490
×558

question asked: 21 Jun '13, 13:08

question was seen: 1,362 times

last updated: 21 Jun '13, 23:51