vamaddur's blog

By vamaddur, history, 7 years ago, In English

Let P(x) be a function that returns the product of digits of x. For example P(935) = 9*3*5 = 135. Now let us define another function P_repeat(x):

int P_repeat(int x){
    if(x < 10) return x
    return P_repeat(P(x))
}

For a value v, find the number of numbers x less than N such that P_repeat(x) = v.

How would I make a transition between states in a digit DP for this problem?

Please help, and thanks in advance!

UPD: The bounds are N <= 10^13.

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

»
7 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

First notice that the product of digits of x is always less than x, so that you actually have a DAG. Now the graph is defined by a single relation x->P(x), so we, in fact, have a tree (well, a forest). Why don't you explicitly build the forest for whatever your range is (I'm assuming it's small, because you asked about DP)? Maybe then you can visualize it easier.

For example, if it's a single query (N,v) it's enough to run a dfs from v. If you need a lot of queries and MAX_x < 10^5 or so then you can use sack ("dsu on tree") with an order statistic set on each node so each node knows all of its children and how many are less than N. And so on.

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

    See above for the bounds. Sorry about not posting them earlier.

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

      Oh, that's very different than what I had in mind then. It looks tricky, do you have a link? We can tell right away that most numbers satisfy P_repeat(x) = 0 (96% of all numbers in [0,1e8], 94% in [0,1e7]) but that doesn't seem enough to force enumerating them for all v != 0 to work.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 4   Vote: I like it +10 Vote: I do not like it

      You said that n ≤ 1013, though the function in the code is 32bit. Do you think about the overflow or mod 232?
      P.S. I think you should write "long long" or "long", not "int".

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

        The int is meant as a placeholder, to show that the value passed is an integer. The mod 2^32 and overflow is overcomplicating matters.

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

Auto comment: topic has been updated by vamaddur (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

You can sort the digits first and the answer doesn't change. The number of the possible sorted sequence of digits is not too big so we can enumerate them all.

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

    @anta I agree with you, but I am still interested in seeing a Digit DP solution, as that is what I am trying to practice.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Consider this pseudo code of a digit DP:

      rec(i, prod):
          if i == -1
              return 1 if P_repeat(prod) == v else 0
          result = 0
          for d in 0 .. 9:
              result += rec(i - 1, prod * d)
          return result
      

      rec(i, prod) counts number of integer x < 10i + 1 such that P_repeat(prod * P(x)) is equal to v (this is wrong if x is less than 10^i but I hope you can understand).

      The point is this function can be memorized with a hash map or similar to that. Because of the above argument, we can be sure that the number of states is not too big.

      Can you modify this to consider only integers less than N? This part is the regular routine of the digit DP technique so you can consult other articles.

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

        @anta I was able to count combinations of digits with length less than N.length() as shown below:

        (Note that maxLen = N.length()-1, freq stores the frequency of each digit in the current permutation, and choose[i][j] denotes iCj.)

        int ending, maxLen, freq [10];
        long long choose [15][15];
        map<pair<int, long long>, long long> dp;
        
        int eval(long long num){
            long long res = 1ll, temp = num;
            while(temp > 0){
                res *= temp%10;
                temp /= 10;
            }
            return res < 10 ? res : eval(res);
        }
        
        long long solve(int index, long long prod, int last, bool nonZero){
            if(index == maxLen){
                if(eval(prod) == ending && nonZero){
                    long long tot = 1ll; int temp = maxLen;
                    for(int i = 0; i < 10; i++){
                        tot *= choose[temp][freq[i]];
                        temp -= freq[i];
                    }
                    return tot;
                }
                return 0ll;
            }
            if(dp.find(make_pair(index, prod)) != dp.end()) return dp.find(make_pair(index, prod))->second;
            long long sum = 0ll;
            for(int i = last; i < 10; i++){
                bool nz = nonZero || i > 0;
                if(nz){
                    freq[i]++;
                    sum += solve(index+1, prod*i, i, nz);
                    freq[i]--;
                }
                else{
                    freq[i]++;
                    sum += solve(index+1, prod, 0, nz);
                    freq[i]--;
                }
            }
            dp.insert(make_pair(make_pair(index, prod), sum));
            return sum;
        }
        

        How can I modify this to count digits of the same length, but less than N?

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

          I don't understand your question. Also, does your code actually work? It seems like broken for me.

          Can you implement my pseudo code above?

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It is easy to understand that two numbers with the same digits (not necessarily with the same order, for example 1244, 4214) have the same answer. There are 10^13 different nums, but there are only about 700000 different sets of digits (you can calc it using this) So we can find all different sets. How to count numbers we can create from a certain set, that are <= N? Assume function f for set S (it contains pair of {digit, its count in number}) which returns count of different numbers we can create from S (not necessarily <= N), something like this:

code

It's easy to find count of numbers we can create from S, which length is less than length of N, but how we can solve case with equal length? We'll go with i for digits of N, current digit is a[i]. 1) We need to put digit x < a[i], now result number is always less than N, so we can decrease count of x and add to result f(new set), then increase count of x to get back (we need to do this with all x < a[i] we have). 2) If we have a[i] in our set, we need to put it (and decrease its count) and continue, otherwise break. Then add to ans[p_repeat(product of all digits in S)] our result. We need to make it with all different sets, and then print ans[v].

»
7 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

I have a solution without dynamic programming (though, I don't have solution with dynamic programming).

Let f(x) = Prepeat(x) (because the function name is too long), f(x) = f(P(x)) = f(P(P(x))) = ... = P(P(P(... P(x)... ))).

The main idea is, f(a) = f(b), if b is a non-leading-zero integer that scrambled a, because obviously P(a) = P(b), so f(a) = f(P(a)) = f(P(b)) = f(b). So, you can brute-force the number of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 digits.

Let's consider counting the number of x that f(x) = v, in range of 10b ≤ x ≤ n. Let ci the number of i's (0 ≤ i ≤ 9) in x, it satisfies 0 ≤ ci, and c0 + c1 + c2 + ... + c9 = b + 1. The way is C(b + 10, 9). If b = 12 (maximum), there are only 497420 ways.

Let f(c0, c1, ..., c9) the value of f(x) if x has c0 0's, c1 1's, c2 2's,... . If f(c0, c1, ..., c9) = v, you can add "the number of integers less or equal to n, which has c0 0's, c1 1's, c2 2's,..." to the answer.

And how can calculate "the number of integers less or equal to n, which has c0 0's, c1 1's, c2 2's,..."? Let's consider about the problem.

How many integers which has two 1's and two 2's and one 3, less than 22331?

In this case, if the first digit is 1, it certainly satisfies the condition, and there are 12 ways (because you can calculate the permutation of "1223"). if the first digit is 2 and second digit is 1, it certainly satisfies the condition, and there are 6 ways (because you can calculate the permutation of "123). If you repeat this, you can get the answer 12 + 6 + 1 + 1 = 20.

You can calculate the value in O(b2). Pay attention to the leading-zero values (you can't count it).

The total time complexity is . In the maximum pattern the number of calculation will be about 2 × 108, so you can calculate in time.