Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### taklo's blog

By taklo, history, 2 months ago, ,

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;
}


• +1

 » 2 months ago, # |   0 Auto comment: topic has been updated by taklo (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 2 →   +5 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.
•  » » 2 months ago, # ^ |   0 Thanks sir got my mistake
 » 2 months ago, # |   0 Auto comment: topic has been updated by taklo (previous revision, new revision, compare).