 # Digit Dynamic Programming

I have been solving

I cross checked my answers for various inputs with the accepted solutions & all were correct even for N=10^17. Till now mine solution isn’t accepted & I’m unable to catch the bug,where it went wrong .Any help would be appreciated.
I used the approach as mentioned in the editorial but for storing states I used -
dp{Max_Length_of N}[number_is_zero/not][required_number_found/not]
//dp as I’ve matched the answers with many accepted solutions but still mine wasn’t accepted.

http://www.codechef.com/viewsolution/4136822

``````ll F(int size,bool zero,bool found,char dig){//constructing numbers

if(size==1){
if(found)return 1;//if the required number found
else return 0;
}

if(mem[size][zero][found])return dp[size][zero][found];

mem[size][zero][found]=1;
ll res=0;
ll ans;
for(char i='0';i<='9';i++){
ans=F(size-1,zero||i!='0',found||i==dig,dig);//constructing number recursively
res+=ans;
}

dp[size][zero][found]=res;

return res;
}

ll solve(char dig){

ll ret=0;
int qued=len;

bool zero=0,found=0;ll sum;

for(int pos=0;pos<len;pos++){
char check=arr[pos];
zero=0;
for(char val='0';val<check;val++){//construct number
sum=F(qued,zero||val!='0',found||val==dig,dig);
ret+=sum;
}
found=found||check==dig;zero=zero||arr[pos];
qued--;
}
if(found)ret++;//adding the numbers itself if contains the required digit

return ret;
}

ll zr(){//gives numbers such as 0-,00-,000- upto length of N
ll res=0,cur=1;
for(int i=1;i<len;i++){
cur*=9;
res+=cur;
}
return res;
}

//solution
for(char i='0';i<='9';i++){//calculating numbers for each digit
sum=solve(i);
ans+=sum;
}
ans=ans-zr()-1;//subtracting numbers formed from 0-,00-,000-,....& 0 itself
//for dig=0 ans would also contain numbers like 0{1-9}*,00{1-9}*... & need to be subtracted``````