Sums in a triangle

March 12, 2009 at 11:34 am 2 comments

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

This involves a bit of logic and trick. I liked it, perhaps because I solved it 😉

Advertisements

Entry filed under: Uncategorized.

Turbo Sort Enormous Input Test

2 Comments Add your own

  • 1. narinderberi  |  March 12, 2009 at 11:41 am

    If 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 pm

    Hi
    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Trackback this post  |  Subscribe to the comments via RSS Feed


Blog Stats

  • 4,036 hits

Recent Comments


%d bloggers like this: