WA in Bamboo Art (ZCO16002)

Here is my code for the problem at https://www.codechef.com/ZCOPRAC/problems/ZCO16002 :

#include <bits/stdc++.h>
using namespace std;

int dp[2507][2507], n, h[2507], location[100007];

int main()
{
    memset(dp, -1, sizeof(dp));
    memset(location, -1, sizeof(location));

    cin >> n;
    for(int i=0; i<n; i++)
        cin >> h[i];
    sort(h,h+n);
    for(int i=0; i<n; i++)
        location[h[i]] = i;

    int max_len = 0;
    for(int i=1; i<n; i++)
        dp[0][i] = 2;
    for(int i=1; i<n; i++)
        dp[i][0] = 2;
    for(int i=0; i<n; i++)
        dp[i][i] = 1;

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(i == j || dp[i][j] > 0)
                continue;
            else
            {
                int diff = h[j] - h[i];
                int prev = h[i] - diff;
                if(prev >= 0)
                {
                    int index = location[prev];
                    if(index != -1)
                    {
                        if(dp[index][j] == -1)
                            dp[i][j] = 2;
                        else
                            dp[i][j] = dp[index][i] + 1;
                    }
                    else
                        dp[i][j] = 2;
                }
                else
                    dp[i][j] = 2;
            }
            max_len = max(max_len, dp[i][j]);
        }
    }

    cout << max_len << "\n";

    return 0;
}

The above code gives the correct output for the sample test case but it gives Runtime Error on submission. Also I am not sure if the above code is actually correct or it fails on some test case. Actually the editorial for this problem ZCO16002 - Editorial contains a recursive solution but since I am still not that good at recursion I tried an iterative approach but here I am stuck with a Runtime Error. Can anyone please help?

@everule1 Please help.

Why is j looping from 0? shouldn’t it loop from i+1, changing that gave me an AC.

1 Like

@everule1 Thank you so much ! :slightly_smiling_face: I got an AC !