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;
sprintf(cad,"%lld",x);
int len = strlen(cad);
//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
- http://www.spoj.com/problems/LUCIFER/
- http://www.spoj.com/problems/RAONE/
- http://www.spoj.com/problems/GONE/
- http://coj.uci.cu/24h/problem.xhtml?abb=2481
- http://coj.uci.cu/24h/problem.xhtml?abb=1242
and many other you can find anywhere
