## Sums in a triangle

*March 12, 2009 at 11:34 am* *narinderberi* *
2 comments *

http://www.codechef.com/problems/SUMTRIAN/

This involves a bit of logic and trick. I liked it, perhaps because I solved it ðŸ˜‰

Entry filed under: Uncategorized.

1.narinderberi | March 12, 2009 at 11:41 amIf you figure out the total of path for n rows, it would be 2^(n-1). So for 100 rows, it would amount to 2^99. Obviously, if one were to track so much data, one is gone. To solve such problems, one needs to be insightful and check if some pruning can be done to (of course) prune those paths which are irrelevant, or known to be less fertile than others which should keep on flourishing.

Here the logic is to maintain the max sum so far from each column in a row. So consider:

1

1 2

4 1 2

2 3 1 1

After scanning row:

1, we know that the max sum vector till now is: 1

2, we know that the max sum vector till now is: 2 3

3, we know that the max sum vector till now is: 6 4 5

4, we know that the max sum vector till now is: 8 9 6 6

So, in the end, we know that the max sum is 9. Extra memory needed would be 2*numRows to store prevRow and curRow.

Here is the code:

#include

#include

void sumsInATriangle()

{

int numTestCases;

scanf(“%d”, &numTestCases);

for(int iTestCase = 0; iTestCase < numTestCases; ++iTestCase)

{

int numRows;

scanf(“%d”, &numRows);

int *prevRow = new int[numRows];

memset(prevRow, 0, numRows * sizeof(int));

int *curRow = new int[numRows];

memset(curRow, 0, numRows * sizeof(int));

for(int iRow = 0; iRow < numRows; ++iRow)

{

//read curRow from input

for(int iCurCol = 0; iCurCol <= iRow; ++iCurCol)

scanf(“%d”, &curRow[iCurCol]);

//update curRow from prevRow

//curRow has iRow elements, prevRow has iRow – 1 elements

for(int iCurCol = 0; iCurCol prevRow[iCurCol – 1])

curRow[iCurCol] += prevRow[iCurCol];

else

curRow[iCurCol] += prevRow[iCurCol – 1];

}

}

//updated curRow now becomes prevRow for next iteration

for(int iCurCol = 0; iCurCol <= iRow; ++iCurCol)

prevRow[iCurCol] = curRow[iCurCol];

}

//curRow and prevRow are same here

int maxSum = 0;

for(int iCol = 0; iCol maxSum)

maxSum = curRow[iCol];

delete []prevRow; prevRow = NULL;

delete []curRow; curRow = NULL;

//print the max Sum for this test case

printf(“%d\n”, maxSum);

}

}

int main()

{

sumsInATriangle();

return 0;

}

2.livingstone | December 21, 2009 at 7:26 pmHi

I’am not able to understand the pruning step that you have employed here.

1 — level 0

/ \

2 3 — level 1

/ \ / \

6 3 4 5 — level 2

In the example that you have illustrated, you have said

after scanning row 3 the max sum vector is 6 4 5

Why have you pruned the tree which will be formed from 3 in level 2