taklo's blog

[SOLVED] help in digit dp problem
By taklo, history, 5 years ago, In English

Hi all I am trying this problem using digit dp approach though I have not applied memoization yet but my recursive backtrack is not working appropriately . please help me to figure out where is the problem

Problem
#include<iostream>
#define ll long long 
using namespace std;
ll n;
ll x=0;
ll solve(ll index, ll small, ll last){
	if(index==x)
		return 0;
	ll ans=0;	
	if(small){
		ll ans1=solve(index+1,small,0);
		ll ans2=solve(index+1,small,1);
		if(last==1) ans2++;
		ans=ans1+ans2;
	}
	else{
		if((n&(1<<(x-index-1)))!=0){
			ll ans1=solve(index+1, 1, 0);
			ll ans2=solve(index+1, 0, 1);
			if(last==1) ans2++;
			ans=ans1+ans2;			
		}
		else{
			ans=solve(index+1, 0, 0);
		}		
	}
	return ans;
}
int main(){			
	ll t;
	cin>>t;
	while(t--){
				
		cin>>n;
		ll cpy	= n;
		x=0;
		while(cpy>0){
			x++;
			cpy/=2;
		}		
		cout<<solve(0,0,0)<<"\n";
	}
	return 0;
}
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Suppose n = 15 and you are in the state solve(1, 0, 1), i.e. you have this number 1???, then if you put in the current index a 1 (11??) you get a new adjacent bit for all the following possibilities, it means that you need to add to all the remaining valid possibilities this new adjacent bit, that in this case is 2^2 and not just one. The code working will be:

ll solve(ll index, ll small, ll last, ll acc){
	if(index==x)
		return acc;
	ll ans=0;	
	if(small){
		ll ans1=solve(index+1,small,0, acc);
		ll ans2=solve(index+1,small,1, acc + last);
		ans=ans1+ans2;
	}
	else{
		if((n&(1<<(x-index-1)))!=0){
			ll ans1=solve(index+1, 1, 0, acc);
			ll ans2=solve(index+1, 0, 1, acc + last);
			ans=ans1+ans2;			
		}
		else{
			ans=solve(index+1, 0, 0, acc);
		}		
	}
	return ans;
}

I recommend adding another parameter that is accumulative of adjacent bits in the current number, and when the index is equal to x instead to return 0 return the accumulator.

→ Reply