mainnahihoo's blog

By mainnahihoo, history, 16 months ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

Spoiler
  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like 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

    • »
      »
      »
      16 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Never mind that was stupid of me, my mistake. a_foolish_Oler's answer is (likely) the correct one.

  • »
    »
    16 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Actually, I writes return mem[...] = ...; when writing dp in recursive. That's not a problem.

    • »
      »
      »
      16 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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).

»
16 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

You memset the array once before each test case, for a total complexity of O(T size(dp)), which is clearly the wrong complexity.