SUMTRIAN : getting wrong answer

general
, ,
1

hii,
my code is working fine with the provided test cases and with random ones i formulated,
But its still showing Wrong answer
please check this code and inform abt my mistake CodeChef: Practical coding for everyone

2

Hello,

Below you can find an explanation I wrote for this problem a few months ago and I hope it helps you:

It is said you need to start at the top of the triangle (where there is only one number) and keep moving to the number directly below or to the right until you reach the last row…

Take as an example the triangle:

1
1 2
9 2 3

If you want to maximize the sum by only moving right or down, is it clear to you that you should follow the path 1 -> 1 -> 9?

Note that 1 is not the maximum number you can choose on the 2nd row, but, it is the number that will “give you acess” to the number 9 on the third row, number which you will need to use if you want to reach the maximum sum…

This idea probably could lead us to use some sort of depth-first search and/or recursion… It turns out that for a triangle with as many rows as 100, there are 2^99 routes altogether… That would take you some billion years to check all of them if you could check one trillion of routes per second!!

So, we already know it would be good if we somehow knew in advance that we need to use number 9 on our solution without checking all possible routes… That can be done by using a bottom up approach instead of a top down one…

Let’s list all the possible sums we can make with the last 2 rows (I am starting from right to left here):

using the 3 and 2 on last row we can have:

3+2 or 2+2 (summing them with the 2 on 2nd row, as it directly above or one place to the right);

Using the 9 and the 2 we get:

2+1 or 9+1

So, as you see two interesting things happened:

We used the same number (2) twice (one time for each of the 2 neighbouring numbers on the same row) and we also managed to obtain all 4 results:

5 or 4 for the 1st pair
3 or 10 for the 2nd pair

This suggests that as we are using some values to repeat calculations, we can use recursion with memoization to solve the problem fast, and that’s what we will do up to a point, let’s see:

We now know that the 2 maximum values we can obtain from the last rows are 5 and 10, so we replace these values on second row, and eliminate the third one completely, to get the new triangle:

1
10 5

From here, it’s easy to see that the maximum sum is 11.

This approach works because we actually follow a down or to the right approach as required… Instead of starting at the top and waste all the time computing useless sums, by starting at the bottom and storing the maximum values we are “implicitly” removing lots of unnecessary values…

Hope I could help,

Bruno

3 Likes
3

Thanks Bruno for your clever algorithm, i’ll implement this logic, but my top down version is also working fine and producing correct output for random samples… i was wondering why its not getting accepted… And where the code fails to produce the desired answer

4

and isnt this top down logic same as yours??

for(row=0;row<lines;row++){
  for(col=0;col<=row;col++){
    down=row+1;
    right=col+1;
    if(result[row][col]+matrix[down][col] > result[down][col])
      result[down][col]=result[row][col]+matrix[down][col];
    if(result[row][col]+matrix[down][right] > result[down][right])
      result[down][right]=result[row][col]+matrix[down][right];
  }
}
5

i implemented your way n got accepted CodeChef: Practical coding for everyone
Thanks

Will you please suggest , why my earlier code wasnt gettng acccepted

6

Well, I’m not sure, but, you might be having some overflow in your code… On the situation where row = lines-1 and you do down = row+1, I guess you ae going out of array bounds…

1 Like