Help me in solving SPCP6 problem (Memoization)

help
1

My issue

Getting wrong answer while putting memset outside of testcase loop in Tetris Problem.
getting ans 3 in every testcase while we caching dp array once.

My code

#include<bits/stdc++.h>
using namespace std;
define int long long
define endl ‘\n’
define m1 1000000007
define m2 998244353
define inf LLONG_MAX/2
define inf2 1e18
define vi vector
define pi pair<int,int>
define mi map<int,int>
define mpi map<pair<int,int>,int>
define vpi vector<pair<int,int>>
define vvi vector<vector>
define vvc vector<vector>
define mc map<char,int>
define st stack
define qu queue
define si set
define sc set
define stp stack<pair<int,int>>
define qup queue<pair<int,int>>
define spi set<pair<int,int>>
define so(a) sort(a.begin(),a.end())
define rso(a) sort(a.rbegin(),a.rend())
define sumall(a) accumulate(a.begin(),a.end(),0LL)
define rev(a) reverse(a.begin(),a.end())
define mx(a) *max_element(a.begin(),a.end())
define mn(a) *min_element(a.begin(),a.end())
define yes cout<<“YES”<<endl
define no cout<<“NO”<<endl
define fi first
define se second
define pb push_back
define fo(n) for(int i=0;i<n;i++)
define rfo(n) for(int i=n-1;i>=0;i–)
define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);

int dp[100007][2];

int modexp(int x,int y,int m){
int ans=1;
while(y>0){
if(y&1) ans=(ansx)%m;
y>>=1;
x=(xx)%m;
}
return (ans%m);
}
vector calculateLPS(const string& pattern) {
vectorlps(pattern.size(),0);
int len=0,i=1;
while(i<pattern.size()) {
if(pattern[i]==pattern[len]) len++,lps[i]=len,i++;
else {
if (len!=0) len=lps[len-1];
else lps[i]=0,i++;
}
}
return lps;
}
vector kmpSearch(const string& text, const string& pattern) {
vectorlps=calculateLPS(pattern);
vectorres;
int i=0,j=0;
while (i<text.size()) {
if(pattern[j]==text[i]) i++,j++;
if(j==pattern.size()) res.push_back(i-j),j=lps[j-1];
else if (i<text.size() && pattern[j]!=text[i]) {
if (j!=0) j=lps[j-1];
else i++;
}
}
return res;
}
int sol(int i,int n,int turn){
if(i>=n && turn==1) return 0;
if(i>=n && turn==0) return 1;
if(dp[i][turn]!=-1) return dp[i][turn];
int ans=0;
if((n-i)==1) ans=(ans+sol(i+4,n,turn))%m1;
else if((n-i)==2) ans=(ans+sol(i+1,n,(turn+1)%2)+sol(i+4,n,turn))%m1;
else if((n-i)==3) ans=(ans+sol(i+1,n,(turn+1)%2)+sol(i+2,n,turn)+sol(i+4,n,turn))%m1;
else ans=(ans+sol(i+1,n,(turn+1)%2)+sol(i+2,n,turn)+sol(i+3,n,turn)+sol(i+4,n,turn))%m1;
return dp[i][turn]=ans%m1;
}
signed main(){
memset(dp,-1,sizeof(dp));
fastio
int t;
cin>>t;
while(t–){
int n;
cin>>n;
cout<<sol(0,n,0)<<endl;
}
}

2

plz reply @dpcoder_007

3

I think you should put memset inside while loop for test cases because if you put outside then only initially it is set to -1 and for every test case it will be already filled by the memoization and not reset to -1. So to reset it to -1 for every test case move this into while loop

4

@asof_770192
have resolved the issue for wa in your code but its showing tle now.
i think that only tabular dp will work in this problem .
So convert in into tabular dp .
rest of your code and logic is absolutely correct

#include<bits/stdc++.h>
using namespace std;
# define m1 1000000007
int dp[100001][2];
 int sol(int i,int n,int turn){
    if(i>=n && turn==1) return 0;
    if(i>=n && turn==0) return 1;
    if(dp[i][turn]!=-1) return dp[i][turn];
     long long int ans=0;
    if((n-i)==1) ans=(ans+sol(i+4,n,turn))%m1;
    else if((n-i)==2) ans=(ans+sol(i+1,n,(turn+1)%2)%m1+sol(i+4,n,turn)%m1)%m1;
    else if((n-i)==3) ans=(ans+sol(i+1,n,(turn+1)%2)%m1+sol(i+2,n,turn)%m1+sol(i+4,n,turn)%m1)%m1;
    else ans=(ans+sol(i+1,n,(turn+1)%2)%m1+sol(i+2,n,turn)%m1+sol(i+3,n,turn)%m1+sol(i+4,n,turn)%m1)%m1;
    return dp[i][turn]=ans%m1;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
    ios_base::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
        memset(dp,-1,sizeof(dp));
        int l;
        cin>>l;
        cout<<sol(0,l,0)<<"\n";
    }
}
5 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int mod = 1e9 + 7;

// vector<vector<int>> dp;
int dp[100004][2];

int fun(int n, int last) {
    if (n<=0) 
        return 0;
    
    if (dp[n][last] != -1) 
        return dp[n][last];
    
    int ans = 0;
    ans = (ans % mod + fun(n-1, last==0) % mod) % mod;
    ans = (ans % mod + fun(n-2,last!=0) % mod) % mod;
    ans = (ans % mod + fun(n-3,last!=0) % mod) % mod;
    ans = (ans % mod + fun(n-4,last!=0) % mod) % mod;
    if(n<=4 && last==1)    ans = (ans % mod +(fun(n-4,last!=0)+1) % mod) % mod;
    
    return dp[n][last] = ans % mod;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(dp,-1,sizeof(dp));
        // dp = vector<vector<int>>(100005 , vector<int>(2,  -1));
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;

        int ans = fun(n, 1);
        cout << ans << endl;
    }
    return 0;
}

this code get accepted
as in this approach you have to use memset just 1 time and in recursive function you have to go from n to 0 (incase of moving from 0 to n then memset require every time (t))

6

just change the code such that travel in the recursive funtion will be from n to 0 then you can use memset just once