Need help to identify a test case which causes NZEC/WA in SUMTRAIN for the said algorithm

Posting a code and asking people to solve the error seemed tedious for the solution provider, so i will explain my approach and also give the code so that it becomes a little easier.
My approach to this problem is a novice one. A standard top to bottom approach. But i am getting NZEC instead of TLE so i want to know the problem, to avoid it later on.
For the testcase:

1 2
4 1 2
2 3 1 1

I’m calculating the sums by adding top elements with the bottom and bottom right ones. Then the intermediate sum is again added in the same manner with the line given below. The whole triangle is converted to:

2 3
6 3 4 5
8 9 6 4 5 5 6

Then i sort the very last array and get the max element and print it.
In code, i accept the first element(int first):


and calculate the intermediate result(ArrayList intermediate) for the second line.

2 3

After that from 3rd to last line, i receive the input and store it(ArrayList org). Then using the value from intermediate i calculate the sums and store them(ArrayList temp). Calculation is done until the size of org is reached, to avoid NullPointer, i.e., if there is no corresponding bottom or bottom-right element for the intermediate value. Then i assign temp to intermediate and clear both org and temp. This process goes on and at last i sort the final intermediate array to get the max element.
Here is the code link text

If anyone can find a test case that generates an unexpected answer or exception in my code, please provide it to me. Any help is much appreciated. Thank you in advance.

1 Like

I didn’t check the entire code but I want to understand this piece of code

if (dim == 1) {

Why do exit when dim is 1?

Did somebody said he wanted a test case?

Try this-

2 3
4 5 6
7 8 9 10
10 11 12 13
Your Output
Correct Output
33 (1+3+6+10+13)

Also, your approach is wrong - its pure brute force of storing every information about values and path. Look a little bit on dp, do some standard problems and then solve this. Your approach may work for N<1000 but is not sustainable- it will fail if we slightly raise N to perhaps N=2000 or N={10}^{4}. Its better to do things the intended way :slight_smile:

Sorry, Thanks a lot for pointing that out. It should have been ‘continue’. Thanks again. Updated the code but it still doesn’t change the NZEC. :frowning:

One way to resolve these issues is to run in Codechef IDE.
I ran your code and got this error. Hope you find the mistake.

Exception in thread “main” java.lang.NumberFormatException: For input string: "4 "
at java.lang.NumberFormatException.forInputString(
at java.lang.Integer.parseInt(
at java.lang.Integer.parseInt(
at Main.main(

Custom Input:



2 1

1 2 3



1 2

4 1 2

2 3 1 1

That was due to the unnecessary white-space after 4…u see its saying
"4 "…well solved that using trim() and got the correct answer for the testcases in codechef IDE. But now it gives WA after submission. :frowning:

Thanks a lot for your help so far.

I guess that was everything you could do to help. Thanks anyways :slight_smile: @tamiliit

@vijju123 Thanks a lot for your attention. Yes, your provided testcase fails on my approach, but correct me if i am wrong…doesn’t the problem say something like this:
“Let’s consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line, three in the third line, etc.”

But yours has 4 elements in the 5th line.

Based on this statement i designed the algorithm. I know it’s a brute one and i am trying to improvise by going through the editorials. Currently i am designing another approach but it would satisfy me getting a TLE on this one.