jlcastrillon's blog

By jlcastrillon, 11 years ago, In English

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

and many other you can find anywhere

  • Vote: I like it
  • +9
  • Vote: I do not like it

| Write comment?
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

it is good

»
11 years ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @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   Vote: I like it 0 Vote: I do not like it

    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;
    limit = cad[i] - '0';
    
    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   Vote: I like it 0 Vote: I do not like it

    accepted now :)

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      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   Vote: I like it 0 Vote: I do not like it

        i also have the same problem

      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        solved! :) AC! Thanks a lot people for the valuable insights.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you please share your accepted code?

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Google Code jam 2014 Round1 B Problem B is a good problem of this kind.^_^

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    :)

    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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

@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

  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

what RET means in English?Can you explain other short words usually used?Thanks!

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    did mistake on the parity check :)

    have got it accepted now

    thnx for this wonderful tutorial :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A good read but can anyone make the recursive tree of the problem which led to DP solution!

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://www.spoj.com/problems/LOTGAME/

I recently added this one to SPOJ :D