### jlcastrillon's blog

By jlcastrillon, 11 years ago,

Some problems ask to find how many numbers from A to B have a certain property, if the problem of finding how many numbers of k (0-9) digits have that property can be solved using a function F(k,property) in O(H) and when you update the left of a number the property can be updated in O(S) then there is a solution for the problem in O(H * S * log10^2(n)).

Let M(x) the amount of numbers less than x that have that property. Then M(B + 1) — M(A) is the solution to our problem, or M(B) — M(A) + h where (h = 1 if B have the property, else h = 0) To find M(x) we need to make a few observations. A number x less than y iff the length of x is less than the length of y or if they have equal length and there is a digit x[i] < y[i] and for all digits j < i this holds x[j] = y[j], that is ,they are equal from left to right until a digit i where x[i] < y[i], when this happens then all digits y[j] j > i can be in the range(0-9) and then F(k,property) can be used. We can use this to find all the numbers less than x having the desired property.

sol  = 0
remain = lengthof(x)
// we find the digit where they first differ x[i] < y[i] and for all digits j < i x[j] = y[j]
for each digit x[i] of x from left to right{
remain--;
// now we find all the digits that can be at y[i] and are less than x[i]
for each digit d from 0 to x[i] - 1{
property' = (property if digit d replaced digit x[i])
sol += F(remain,property')
}
update property after deletion of digit x[i]
}


Here I have a sample C++ code to solve the following problem How many integers in the interval [A, B] are there such that the sum of their digits is S

#define ll long long
bool mem[N][N];
ll D[N][N];
// this is the function F(k,property)
ll F(int dig,int sum){
if(dig == 0)
return (ll)(sum  == 0);
if(mem[dig][sum])
return D[dig][sum];
mem[dig][sum] = 1;
ll ret = 0LL;
for(int i = 0;i<=9;i++)
ret += F(dig - 1,sum - i);
D[dig][sum] = ret;
return ret;
}

// this is M(x)
ll solve(ll x){
ll ret = 0;
//sum is the desired property
int sum = s;
int qued = len;
// we find the digit where they first differ x[i] < y[i] and for all digits j < i x[j] = y[j]
for(int i = 0;i < len;i++){
qued--;
int d = cad[i] - '0';
// now we find all the digits that can be at y[i] and are less than x[i]
for(int j = 0;j <d;j++){
//sum - j = property'
if(sum - j >= 0){
ret += F(qued,sum - j);
}
}
//update property after deletion of digit x[i]
sum -= d;
}
return ret;
}

//this is the solution to the problem
sol = solve(b + 1) - solve(a);


Some problems to solve

and many other you can find anywhere

• +9

| Write comment?
 » 11 years ago, # |   +1 it is good
 » 11 years ago, # | ← Rev. 6 →   0 these are other similar problems http://lightoj.com/volume_showproblem.php?problem=1205 http://www.spoj.com/problems/NUMTSN/
•  » » 10 years ago, # ^ |   0 @jlcastrillon can you please check my code what's wrong in it for http://www.spoj.com/problems/NUMTSN/ problem.... it is giving TLE
• »
»
10 years ago, # ^ |
Rev. 6   0

# include<bits/stdc++.h>

using namespace std;

long long int mod=1000000007;

long long int d[51][51][51][51];

bool mem[51][51][51][51];

int len;

long long int f(int i, int three, int six, int nine, int lo, char *cad) {

if (i == len)
{

if(three==six && six==nine)
return 1;
else
return 0;
}

long long int ret = 0;

int dig;

if (lo) {
if (mem[i][three][six][nine]) {
return d[i][three][six][nine];
} else {
mem[i][three][six][nine] = 1;
long long int r = 0;
for (dig = 0; dig <= 9; ++dig) {
if(dig==3)
r=(r+f(i + 1,three+1, six,nine, lo, cad))%mod;
else if(dig==6)
r=(r+f(i + 1,three, six+1,nine, lo, cad))%mod;
else if(dig==9)
r=(r+f(i + 1,three, six,nine+1 , lo, cad))%mod;
else
r=(r+f(i + 1,three, six,nine, lo, cad))%mod;
}
d[i][three][six][nine] = r%mod;
return r%mod;
}
}

int limit;

for (dig = 0; dig <= limit; ++dig) {
if(dig==3)
ret=(ret+f(i + 1,three+1, six,nine, (lo || (dig < (cad[i] - '0'))), cad))%mod;
else if(dig==6)
ret=(ret+f(i + 1,three, six+1,nine, (lo || (dig < (cad[i] - '0'))), cad))%mod;
else if(dig==9)
ret=(ret+f(i + 1,three, six,nine+1 , (lo || (dig < (cad[i] - '0'))), cad))%mod;
else
ret=(ret+f(i + 1,three, six,nine, (lo || (dig < (cad[i] - '0'))), cad))%mod;
}
return ret%mod;


}

long long int solve(char *x) { len = strlen(x);

memset(d, 0, sizeof(d));

memset(mem, 0, sizeof(mem));

return f(0, 0, 0,0, 0, x);


}

char aa[51];

char bb[51];

int check(char *x) { int a=0,b=0,c=0,i,j,k;

k=strlen(x);

for(i=0;i<k;i++){

if(x[i]=='3')
a++;

else if(x[i]=='6')
b++;

else if(x[i]=='9')
c++;

}

if(a==b && b==c)
return 1;
else
return 0;

}

int main() { int t;

long long int sol;

char r;

scanf("%d",&t);

while(t--){

scanf("%s",&aa);

scanf("%c",&r);

scanf("%s",&bb);

scanf("%c",&r);

sol = (solve(bb) - solve(aa))%mod;

sol= sol + check(aa);

printf("%lld\n",sol%mod);

}
return 0;

}

•  » » 10 years ago, # ^ | ← Rev. 4 →   0 accepted now :)
•  » » » 10 years ago, # ^ | ← Rev. 2 →   0 I'm trying to solve the same problem and getting TLE. What did you improve in your code? I don't know what else to do :sThis is the main function of my code. Could you please help me? int f(int i, int tres, int seis, int nueve, bool menor) { int piv = max(tres, max(seis, nueve)); if ( piv-nueve + piv-seis + piv-tres > n-i or (piv == 0 and n-i < 3) ) return 0; if (i == n) return tres == seis and tres == nueve and tres > 0; if (dp[i][tres][seis][nueve][menor] != -1) return dp[i][tres][seis][nueve][menor]; int res = 0, end = menor ? 9 : x[i] - '0'; For(d, 0, end+1) res = ( res + f( i+1, tres + (d == 3), seis + (d == 6), nueve + (d == 9), menor | (d < x[i] - '0') ) ) % MOD; return dp[i][tres][seis][nueve][menor] = res; } 
•  » » » » 10 years ago, # ^ | ← Rev. 2 →   0 i also have the same problem
•  » » » » 10 years ago, # ^ |   0 You don't need 5 dimensional dp(it had given me tle when I used 4D dp). Try solving it by combinatorics.
•  » » » » 9 years ago, # ^ |   0 solved! :) AC! Thanks a lot people for the valuable insights.
•  » » » » » 6 years ago, # ^ |   0 can you please share your accepted code?
•  » » 10 years ago, # ^ |   0 Google Code jam 2014 Round1 B Problem B is a good problem of this kind.^_^
•  » » » 10 years ago, # ^ |   0 Indeed, I wrote about the solution here
 » 10 years ago, # |   0 Hey nice article , can you please give link to some working code of the problem . like I have lot of trouble writing the F(k, property) in different cases...
•  » » 10 years ago, # ^ |   +3 For example: Solution for Last contest 431D
 » 10 years ago, # |   0 thanks for the reply , but in the above case the sum (s) is given , so we are able to get the difference and calculate it, but in some cases , like where 1. some property of the difference b/w the sum of the even place digits and odd place digits must have some property like being prime number or diff should be 1 .Is there any tutorial which tells how to formulate 3-Dimensional dp for it.
•  » » 10 years ago, # ^ |   +2 :) int d[10][50][50]; bool mem[10][50][50]; int len; int f(int i, int sum_odd, int sum_even, int lo, const string& cad) { if (i == len) { return (sum_even - sum_odd == 1); } int ret = 0; int dig; if (lo) { if (mem[i][sum_odd][sum_even]) { return d[i][sum_odd][sum_even]; } else { mem[i][sum_odd][sum_even] = 1; int r = 0; for (dig = 0; dig <= 9; ++dig) { if ((len - i) % 2 == 0) { r += f(i + 1, sum_odd, sum_even + dig, lo, cad); } else { r += f(i + 1, sum_odd + dig, sum_even, lo, cad); } } d[i][sum_odd][sum_even] = r; return r; } } int limit; limit = cad[i] - '0'; for (dig = 0; dig <= limit; ++dig) { if ((len - i) % 2 == 0) { ret += f(i + 1, sum_odd, sum_even + dig, (lo || (dig < (cad[i] - '0'))), cad); } else { ret += f(i + 1, sum_odd + dig, sum_even, (lo || (dig < (cad[i] - '0'))), cad); } } return ret; } int solve (int x) { string cad; cad = NumtoString(x); len = cad.length(); memset(d, 0, sizeof(d)); memset(mem, 0, sizeof(mem)); return f(0, 0, 0, 0, cad); } 
•  » » » 10 years ago, # ^ |   +3 my implementation is guided by this posthttp://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property/22394258#22394258:)
 » 10 years ago, # |   0 How it is covering all the numbers less than 123 (say)? first we choose 1 and varied it from 0- 0 -> it covers 000- 099 then we choose 2 and varied it from 0- 1 -> it covers 000- 019. please give some explanation!
•  » » 10 years ago, # ^ |   0 for 123 when changing 1 it covers from 000 to 099 when changing 2 it covers from 100 to 119 when changing 3 it covers from 120 to 122to calculate how many numbers less than X have certain property iterate through all possible positions where a number Y may differ for the first time when compared with X and through all possible digits for that position. you can easily notice that the rest(all the digits to the right of that position ) may take values from 0 to 9, then then if you have a function(almost always solvable by dp) to calculate how many numbers with n(any amount) of digits have certain property(for example a sum equal to S) then your problem is solved.
 » 10 years ago, # |   0 @jlcastrillon nice article...but can you please tell me how to find count of numbers between a and b which contains 0 as their digit... i am not able to get this with above idea, it becomes very complex in case of leading zeroesplease give some explanation as i am having lot of trouble with this ...waiting for ur reply
•  » » 10 years ago, # ^ |   0 first of all find a dp solution to the problem when all digits can be form 0 to 9 and having a fixed number of digits. Then when calculating for a number X how many numbers are less than it and cantain at least one zero, don't take into account the zero digit when changing the value of the first digit this will give you as a solution all the numbers that contain at least one zero with the same number of digits than X and dont't contain leading zeros, then add to the solution how many numbers with less digits than X are there that contain at least one zero and don't contain leading zeroes. Have in mind that you need a special case dp that tells you the solution when the first digit cannot be zero for the second part of the solution.
 » 10 years ago, # | ← Rev. 2 →   0 I write a blog on my website discussing the skill to solve problems of this kind with a contest I created consisting of almost every problem mentioned in this blog or comment. It's a pity that I wrote it in Chinese. So if you are interested in it and you can read Chinese, CLICK!
•  » » 10 years ago, # ^ |   0 Thank you very much. I cant read Chinese, but i was able to find the code of the problem i was getting TLE and learned about using a - b instead of a and b and check for Unable to parse markup [type=CF_TEX] instead of a = b.
•  » » » 10 years ago, # ^ |   0 You're welcome.:D
•  » » 9 years ago, # ^ |   0 YQCMMD, plz update the link to http://yqcmmd.com/2014/06/12/%E6%95%B0%E4%BD%8Ddp%E4%B8%93%E9%A2%98/ in case of future reference.DThanks a lot for this article!
•  » » » 9 years ago, # ^ |   0 Done.
 » 10 years ago, # |   0 what RET means in English?Can you explain other short words usually used?Thanks!
•  » » 10 years ago, # ^ |   0 return for short
 » 10 years ago, # |   0 Hi....:)I am working on the RAONE problem on spojI follwed the same way....but am not getting the right answer........heres the link to my answer:http://ideone.com/5CemTnpls...tell me where i am goin wrong thnx in advance :)
•  » » 10 years ago, # ^ |   +3 did mistake on the parity check :)have got it accepted nowthnx for this wonderful tutorial :)
 » 9 years ago, # |   0 A good read but can anyone make the recursive tree of the problem which led to DP solution!
 » 9 years ago, # |   0 http://www.spoj.com/problems/LOTGAME/I recently added this one to SPOJ :D