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[30][2][2] 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