problem atcoder problem
int dp[(1<<20)];
// int cnt=0;
int rec(int mask,string &s,int n){
// cout<<"call for "<<mask<<endl;
if(mask==(1<<n)-1)return 1;
if(dp[mask]!=-1)return dp[mask];
int x=0;
for(int i=0;i<n;i++){
if(!(mask&(1<<i)) && s[mask|(1<<i)]=='0'){
x|=rec(mask|(1<<i),s,n);
}
}
// cnt++;
return dp[mask]=x;
}
void solve() {
// executing code from here
int t;
cin >> t;
while (t--) {
int n;cin >> n;string s;cin>>s;
memset(dp,-1,sizeof(dp));
s='0'+s;
if(rec(0,s,n))cy;
else cn;
}
}
I am getting TLE why after dp time complexity should be 2^n*n not n!*n
Auto comment: topic has been updated by mainnahihoo (previous revision, new revision, compare).
the issue is likely that you have return dp[mask]=x;, that should be a double equals sign.
Also, minor spoilers for the problem but
DP is too advanced for a ABC problem C, you are over complicating it
sir really is it work like dp[x]==x will be a conditional and always give false i am just returning the value , and saving it in the array to make 2^n time complexity , can you sir please explain . and sir due to this fact abc and even in most case d is not having DP , i was not able to think any other thing in the contest and just solved two , but when see code of other then they used dp i also shock
Never mind that was stupid of me, my mistake. a_foolish_Oler's answer is (likely) the correct one.
Actually, I writes
return mem[...] = ...;when writing dp in recursive. That's not a problem.Yeah, that's my bad, I've personally never done that and I thought that (y=x) would equal 1 for some reason (in retrospect, idk why I thought that).
You memset the array once before each test case, for a total complexity of O(T size(dp)), which is clearly the wrong complexity.
but then how it will work like if i make memset to the outer while loop how it will get compute for all test case
memset One-shot complexity O(size)
You can use vector
okay let me check i used this because array are preferrable over vector but i have to assign vector for each test case
Don't use memset because it will set -1 to whole dp array which is of 1e6 size(approx) for every testcase which is around 4000 or something, change memset() to for loop of size 2^n