How to optimize my code for SUPER HASHING

CodeChef-DSA-learners
1

Here is my code SUPER HASHING problem

#include
#include <bits/stdc++.h>

using namespace std;

int numSameVal(int s, int l, int*** dp, char arr[], int n) {
if(s==0 && l==0) {
return 1;
}

if(s==0 || l==0) {
    return 0;
}

if(n==53) {
    return 0;
}
//cout << l << "		" << s << "		" << arr[n] << endl;

if(dp[l][s][n]!=-1) {
    return dp[l][s][52];
}

int ans = 0;
for(int i=n; i<53 && (i+1)<=s; i++) {
	//cout << arr[i] << endl;
    int smallAns = numSameVal(s-(i+1), l-1, dp, arr, i+1);
    dp[l][s][i] = smallAns;
    ans += smallAns;
}

dp[l][s][52] = ans;
return ans;

}

int main() {
// your code goes here
int t;
cin >> t;
while(t–) {
int l, s;
cin >> l >> s;
char arr[] = “abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ”;
int*** dp = new int**[l+1];
for(int i=0; i<l+1; i++) {
dp[i] = new int*[s+1];
for(int j=0; j<s+1; j++) {
dp[i][j] = new int[53];
for(int k=0; k<53; k++) {
dp[i][j][k] = -1;
}
}
}

    //memset(dp, -1, sizeof(dp));
    
    for(int i=0; i<53; i++) {
        dp[0][0][i] = 1;
    }
    
    for(int i=1; i<l+1; i++) {
        for(int j=0; j<53; j++) {
            dp[i][0][j] = 0;
        }
    }
    for(int i=1; i<s+1; i++) {
        for(int j=0; j<53; j++) {
            dp[0][i][j] = 0;
        }
    }
    
    //cout << "HELLO" << endl;
    int ans = numSameVal(s, l, dp, arr, 0);
    cout << ans << endl;
}
return 0;

}

The time limit for problem is 1.5 seconds.
I am using 3-d DP. Can someone suggest how do I optimize my code further ??
Thanks in advance

2

1.51 sec is not the run time , Actually Your code stopped running after 1.50 seconds , as it exceeded the Time limit.

2 Likes