SUMTRIAN, Passing tests on my machine, but Codechef. Please Help !

Problem - Easy , Code - [SUMTRIAN] ( http://www.codechef.com/problems/SUMTRIAN/ )

I tried a lot on this problem but failed to find the mistake. My code is working fine with the example test cases (given in the problem page) on my machine, but showing “WRONG ANSWER” on Codechef. Please someone have a look at my submission:
( http://www.codechef.com/viewsolution/1895830 )

Hi !

Check out this test case : I think its giving a wrong answer for this

1
3
1
2 1
5 4 3

Answer should be 8 = 5+2+1 . But, your code gives 11 .

1 Like

Hello,

(Note @all, links are now both redirecting properly)

@rajrishav,

Notice the problem description carefully:

“on each path the next number is located on the row below, more precisely either directly below or below and one place to the right;”

The highlighted statement should be fully understood in order you can understand problem.

Looking at the example that it was provided to you:

1
3
1
2 1
5 4 3

On the 1st row you obviously choose 1, as it’s the only possible number.

Now, on 2nd row you can choose a number that it’s either below or to the right of 1 (on this case, we can choose either number 2 or number 1 as we have only two numbers.)

Two things can happen:

  • We choose number 2:

    If this is the case, then on row 3, we can only choose numbers 5 or 4 as they are respectively below, or one place to the right of number 2 located on previous row;

Same procedure applied on number 1 of row 2, leads to only being able to choose elements 4 or 3 on row 3.

By following this rules we see max sum that is possible is actually 8 and not 11.

Best regards,

Bruno

Hi, everyone… I am also facing same problem. My code works for the test case given in this discussion also. Also tried for couple of other test cases too… everything works… Can anyone please test my solution too ? here is the link http://www.codechef.com/viewsolution/1928532

The link you gave to your solution is invalid.

Remove the ) at the end. I think the link needs to be changed .

I think I haven’t understood the problem correctly. Can you please explain the problem and this test case in more detail as to why the answer should be 8 and not 11 ?

@kuruma ,Nice explanation. I guess you are the best person to explain the question. I learnt how to solve this question in a simple way from the hints you posted couple of months back. Carry on the good job !

1 Like

ya…its giving 8… that too in correct format

I tried around 15 cases on https://ideone.com/L1Cgfm. It seems to satisfy all the cases. I’ll try finding the bug. But, one thing you can assume the all constraints will be satisfied. You need not check if they are satisfied or not .
You can debug your code on ideone.com

Thank you very much ani94, such comments keep me motivated :smiley:

I am only sorry I am a bit weak when it comes to Discrete Maths and some algorithms used in these problems/contests… If only I had more time I would also have a lot more fun :smiley: Although Im learning little by little :slight_smile:
It’s a pleasure to help others with what I can :wink:
Regards, Bruno

Link’s fixed now :wink:

anyone ?? ne new ideas or test cases ??