CODEWITHSUNDEEP
algorithmoptimizationdynamic-programming
Zer0
Zer0

Reputation: 2221

USACO number triangle - Execution error

The question is as follows

Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

      7

    3   8

  8   1   0

2   7   4   4

4 5 2 6 5 In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

I had the following error

Your program had this runtime error: Bad
syscall #32000175 (RT_SIGPROCMASK) [email kolstad if you think
this is wrong]. The program ran for 0.259 CPU seconds before the
error. It used 16328 KB of memory.

The code is as follows.

int arr[1500][1500];
map < int,map < int,int> >dp;

int main()
{
    // ofstream fout ("numtri.out");
    // ifstream fin ("numtri.in");
    int n;
    // fin>>n;
    freopen ("numtri.in", "r", stdin);
    freopen ("numtri.out", "w", stdout);
    scanf ("%d", &n);
    int ct = 1;
    int gaga = -100;
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<ct; j++)
        {
            scanf ("%d", &arr[i][j]);
            if(i>0)
                dp[i][j] = maxi (dp[i-1][j-1] + arr[i][j], dp[i-1][j] + arr[i][j]);
            else
                dp[0][0]=arr[0][0];
            if (i == n-1)
            {
                if (dp[i][j] > gaga)
                    gaga=dp[i][j];
                }
        }
        ct++;
    }
    printf ("%d\n", gaga);
    return 0;
}

It works fine on my laptop. On the website it works for 8 test cases and fails for 9th one with this error.

Thanks for the help!

Upvotes: 1

Views: 803

Answers (1)

IVlad
IVlad

Reputation: 43487

 if(i>0)
     dp[i][j]=maxi(dp[i-1][j-1]+arr[i][j],dp[i-1][j]+arr[i][j]);

You check if i > 0, which will ensure you never access a negative index. You never do the same for j however, so you will access dp[i-1][-1] on the first run of the inner (j) loop. I'm pretty sure this is what causes the error.

Upvotes: 4

Related Questions