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
it is good
these are other similar problems http://lightoj.com/volume_showproblem.php?problem=1205 http://www.spoj.com/problems/NUMTSN/
@jlcastrillon can you please check my code what's wrong in it for http://www.spoj.com/problems/NUMTSN/ problem.... it is giving TLE
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) {
}
long long int solve(char *x) { len = strlen(x);
}
char aa[51];
char bb[51];
int check(char *x) { int a=0,b=0,c=0,i,j,k;
}
int main() { int t;
}
accepted now :)
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 :s
This is the main function of my code. Could you please help me?
i also have the same problem
You don't need 5 dimensional dp(it had given me tle when I used 4D dp). Try solving it by combinatorics.
solved! :) AC! Thanks a lot people for the valuable insights.
can you please share your accepted code?
Google Code jam 2014 Round1 B Problem B is a good problem of this kind.^_^
Indeed, I wrote about the solution here
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...
For example: Solution for Last contest 431D
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.
:)
my implementation is guided by this post
http://stackoverflow.com/questions/22394257/how-to-count-integers-between-large-a-and-b-with-a-certain-property/22394258#22394258
:)
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!
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 122
to 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.
@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 zeroes
please give some explanation as i am having lot of trouble with this ...
waiting for ur reply
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.
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!
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 a - b = 0 instead of a = b.
You're welcome.:D
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.D
Thanks a lot for this article!
Done.
what RET means in English?Can you explain other short words usually used?Thanks!
return for short
Hi....:)
I am working on the RAONE problem on spoj
link:http://www.spoj.com/problems/RAONE/
I follwed the same way....but am not getting the right answer........
heres the link to my answer:
http://ideone.com/5CemTn
pls...tell me where i am goin wrong
thnx in advance :)
did mistake on the parity check :)
have got it accepted now
thnx for this wonderful tutorial :)
A good read but can anyone make the recursive tree of the problem which led to DP solution!
http://www.spoj.com/problems/LOTGAME/
I recently added this one to SPOJ :D