DIVPRO - Editorial

divpro
dynamic-programming
editorial
jan13
medium

#1

PROBLEM LINK:

Practice
Contest

Author: Vivek Hamirwasia
Tester: Anton Lunyov
Editorialist: Anton Lunyov

DIFFICULTY:

MEDIUM

PREREQUISITES:

Dynamic Programming

PROBLEM:

If positive integer N has decimal representations d1d2…dL, where n1 ≠ 0, then DIVPRO(N) = d1 / d2 * d3 / d4 * …. If at some point division by zero occurs the DIVPRO(N) is undefined (so digits at even positions should be non-zero). For the given integers 0 ≤ V < 1018 and 1 ≤ L ≤ 36 you need to find the number of positive L-digit integers N having DIVPRO(N) = V and output this number modulo 232. You should be able to answer up to 320,000 such tests in 3 seconds.

QUICK EXPLANATION:

If V = 0 then the count is 9L − X * (10X − 9X) where X = floor((L − 1) / 2).

When V > 0 the answer is non-zero only when V has the form 2n2 * 3n3 * 5n5 * 7n7.

Let dp[L][n2][n3][n5][n7] be a count of L-digit positive integers N having DIVPRO(N) = 2n2 * 3n3 * 5n5 * 7n7, where n2, n3, n5, n7 can be negative. Then values of dp[L][][][][] could be recalculated from values of dp[L-1][][][][] as follows. For all arrays (n2, n3, n5, n7) such that dp[L-1][n2][n3][n5][n7] ≠ 0 we iterate over all digits d from 1 to 9, inclusive, and add dp[L-1][n2][n3][n5][n7] to dp[L][g2[d]-n2][g3[d]-n3][g5[d]-n5][g7[d]-n7], where d = 2g2[d] * 3g3[d] * 5g5[d] * 7g7[d].

The array for dp could created as
dp[0…36][-54…54][-36…36][-18…18][-18…18].
But to avoid memory limit store dp-values only for two consecutive values of L.

To make computations modulo 232 simply use unsigned 32-bit integer type as it is.

During DP step save all non-zero answers to some array.
Then sort it and use binary search to answer each test case fast enough.

EXPLANATION:

At first we assume that V ≠ 0, then it is clear that all digits in N should be non-zero. Hence we consider only such N from now on. The key observation is that DIVPRO(N) has the form 2n2 * 3n3 * 5n5 * 7n7, where n2, n3, n5, n7 arbitrary integers (even negative). This is because each non-zero decimal digit has only 2, 3, 5, 7 as prime divisors. Hence integer V should be of the same form but with non-negative n2, n3, n5, n7, otherwise DIVPRO(N) ≠ V for any N. There are quite a few values of V of this form up to 1018 - only 66,060. This suggests to calculate answers for all possible pairs of L and V, with V of this form in advance, and answer each test almost instantly.

We now use dynamic programming to calculate dp[L][n2][n3][n5][n7] which is the count of L-digit positive integers N having DIVPRO(N) = 2n2 * 3n3 * 5n5 * 7n7. Note that n2, n3, n5, n7 can be negative here.

The most convenient initialization is to set dp[0][0][0][0][0] = 1 and dp[0][n2][n3][n5][n7] = 0 for all other arrays (n2, n3, n5, n7). It has the following meaning: the only 0-digit number is an empty number which has DIVPRO value 1 = 20 * 30 * 50 * 70 (it is math and CS convention to set empty products as 1).

It is quite clear how recalculation should be done. Let d1d2…dL is decimal representation of N. Then
DIVPRO(N) = d1 / d2 * d3 / d4 * … = d1 / (d2 / d3 * d4 / …) = d1 / DIVPRO(N’),
where N’ is the (L-1)-digit number with decimal representation d2d3…dL.
Now if DIVPRO(N’) = 2n2 * 3n3 * 5n5 * 7n7 and d1 = 2g2 * 3g3 * 5g5 * 7g7 then
DIVPRO(N) = 2g2-n2 * 3g3-n3 * 5g5-n5 * 7g7-n7.

This observation shows that values of dp[L][][][][] could be recalculated from values of dp[L-1][][][][] as follows. For all arrays (n2, n3, n5, n7) such that dp[L-1][n2][n3][n5][n7] ≠ 0 we iterate over all digits d from 1 to 9, inclusive, and add dp[L-1][n2][n3][n5][n7] to dp[L][g2[d]-n2][g3[d]-n3][g5[d]-n5][g7[d]-n7], where d = 2g2[d] * 3g3[d] * 5g5[d] * 7g7[d]. For example, g2[6] = 1, g3[6] = 1, g5[6] = 0, g7[6] = 0. See tester’s solution if you have doubts regarding how values g2[d], g3[d], g5[d], g7[d] are calculated for other digits.

So the problem seems like solved but there are several pitfalls wait for us. At first we should decide the sizes of the array we will use for DP. Let’s estimate for the given L in what range could vary each of n2, n3, n5, n7 so that dp[L][n2][n3][n5][n7] is non-zero. Let L1 = [(L+1)/2] and L2 = L − L1, where [x] denotes an integer part of x. So L1 is the number of digits at odd positions in the decimal representation of any L-digit number and L2 is the same thing for even positions. At first let’s find bound on n2. It is clear that the maximal value of g2[d] is 3 (for d = 8). Hence if N is L-digit number and DIVPRO(N) = 2n2 * 3n3 * 5n5 * 7n7 then -3 * L2 ≤ n2 ≤ 3 * L1. Indeed, the maximum possible value of n2 will be when we have all digits at odd positions of N equal to 8 while all digits at even positions are odd. Similarly, the minimum possible value of n2 will be when we have all digits at even positions of N equal to 8 while all digits at odd positions are odd. Since maximum value of g3[d] is 2 (for d = 9) then for n3 we have -2 * L2 ≤ n2 ≤ 2 * L1. Similarly for n5 and n7 we have -L2 ≤ n5 ≤ L1 and -L2 ≤ n7 ≤ L1. At first note that these inequalities should be used in order to bound the range of arrays (n2, n3, n5, n7) for which we will iterate at the dp-recalculation step. We could simply use 4 nested loops like:

for n2 from -3 * L2 to 3 * L1 do
    for n3 from -2 * L2 to 2 * L1 do
        for n5 from -L2 to L1 do
            for n7 from -L2 to L1 do
                do dp recalculation

These inequalities shows that in order to handle all values of L up to some maxL we should create an array of the form
dp[0 … maxL][-3 * maxL2 … 3 * maxL1][-2 * maxL2 … 2 * maxL1][-maxL2 … maxL1][-maxL2 … maxL1],
using Pascal notation, where maxL1 = [(maxL+1)/2] and maxL2 = maxL − maxL1. We have maxL = 36 so maxL1 = maxL2 = 18 and explicit form of the array is
dp[0…36][-54…54][-36…36][-18…18][-18…18].
The total number of elements in this array is 37 * 109 * 73 * 37 * 37 = 403,045,921. Since we should use 32-bit integer type to deal with dp-values, this array will require more than 1.6GB of memory. Though it seems enormous number, Codechef modern server Cube almost allows this. Namely, the memory limit is 1536MB. One could think of some hacky way how to fix this memory issue like do manual precalc for L = 1 and store in this array only dp-values for L ≤ 2 but we explain how to reduce memory in more than 18 times keeping solution clear and elegant.

Note that in our DP we calculate all values of dp[L][][][][] from values of dp[L-1][][][][], hence let’s store in memory only dp-values for two consecutive values of L each time. We could, for example, create an array of the form
dp[0…1][-54…54][-36…36][-18…18][-18…18]
and create the variable p that will be switched from 0 to 1 and vice versa each time. Its meaning is that dp[p][][][][] is the dp-values for L that we want to calculate at this step, while dp-values for L-1 are stored in dp[1-p][][][][]. See tester’s solution as a reference for this trick.

But now in the end we will have dp-values only for L = 35 and L = 36. In order to handle this issue we should iterate over dp[p][][][][] after we calculate all values in it and save all non-zero dp-values with the corresponding values of V to some array. Namely for each L we have array of pairs of the form (V, dp_val). The value of V could be easily restored from the array (n2, n3, n5, n7). To do this faster one could precompute all powers of 2, 3, 5, 7 that are less than 1018 in advance and restore V in O(1) time. See tester’s solution as a reference.

After DP step we sort the corresponding array of pairs for each L and then use binary search to answer each test in O(log X) where X ≤ 66060 is the number of values of V for which we have some non-zero dp-value.

Do we solve the problem? Actually, no - we forget the case V = 0. But it is quite simple. It is clear that DIVPRO(N) = 0 if and only if all digits at even positions are non-zero (in order to avoid division by zero) while at least one digit at odd position is zero. Also not to forget about the first digit that could not be zero. Hence the count of such values of L-digit integers N could be found using basic combinatorics. Recall that we have L1 = [(L+1)/2] digits at odd positions and L2 = L − L1 digits at even positions. For each of the digit at even position as well as for the first digit we have 9 independent choices (each digit from 1 to 9, inclusive). It leads to the factor 9L2 + 1 in the answer. For digits at odd positions (except the first digits) we count as follows. The total number of choices is 10L1 − 1 but we should subtract those choices where all digits are non-zero which is 9L1 − 1.
Hence the final answer for V = 0 is 9L2 + 1 * (10L1 − 1 − 9L1 − 1).
To keep solution clear we could add these pairs to the corresponding array of results for each L.

The final remark. To create dp-array above in language that does not support such indexation we could create it as
unsigned dp[2][2 * 54 + 1][2 * 36 + 1][2 * 18 + 1][2 * 18 + 1]
and denote dp[p][n2][n3][n5][n7] above as dp[p][54 + n2][36 + n3][18 + n5][18 + n7].

The very final remark. To do calculations modulo 232 you actually do not need to do any special. Just do all calculations using 32-bit integer type (signed and unsigned). Overflow that will occur during calculation behaves exactly as modulo 232 operation. Only when you print the answer you need ensure that you print unsigned value.

The final ever remark. The complexity of the described solution is O(maxL5 * B + T * log maxL4), where B = 9 is the number of non-zero decimal digits. Indeed, we have outer loop over L from 1 to maxL and inner nested 4 loops over (n2, n3, n4, n5) where each loop is over O(L) range. Finally, the most inner loop is over digits. But the constant hidden in this asymptotic is very small since we do the most inner loop over digits only for non-zero dp-values. maxL4 is an upper bound for the number of values of V for which we have some non-zero dp-value. We use binary search for T tests over arrays of size with upper bound O(maxL4), hence the final term in complexity.

ALTERNATIVE SOLUTION:

You will find something very different in author’s solution. Since this solution is not faster than described above but a bit complicated please follow comments there to understand it.

The fastest solution to this problem, of course, should use some incredibly fast I/O (which was discussed several time at codechef). But the main thing that will make it really fast is some neat precalc that based on the fact that digits other than 5 and 7 contains only 2 and 3 as a prime factors. This allows to do similar precalc as above but considering separately numbers without 5 and 7 and numbers having only 5 and 7 as digits. Then the answer for each L and V can be calculated in O(L) time using some easy combinatorial reasoning that involves binomial coefficients and precalcuted tables. Refer to ACRush solution or m1sterzer0 solution.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

SPOJ - 3314. Umnozak - UMNOZAK


#2

Can u please tell me where my code failed,
http://www.codechef.com/viewsolution/1723814


#3

Like as described above as an Alternative Solution, I used two tables. One deals with the factors of 2 and 3. The other deals with digits 1,5,7. Both tables are further divided by the number of multiplications and the number of divisions.

So we have:
table1[divs][muls][twos][threes] and table2[divs][muls][fives][sevens]

First, calculate the table for all multiplications, keeping divs = 0. Then, you take care of the divisions. Performing the calculation in this order takes care of the need to deal with negative values.

Now, choose two strings M1 and D1 which only contain the digits 2,3,4,6,8, and 9, and choose two strings M2 and D2 which only contain the digits 1,5, and 7. For an L length value, the lengths of M1 and M2 add up to floor((L + 1) / 2), and the lengths of D1 and D2 add up to floor(L/2).

We need to combine M1 and M2 to create the string M, so for each digit of M, we can choose either a digit from M1 or M2, preserving the relative order of the digits from M1 and M2. The number of ways of creating string M from strings M1 and M2 is m choose m1 where m is the length of M, and m1 is the length of M1.

One way to see this is to suppose we number the digits of M as 1,2,3…m. Then we choose m1 of these numbers as the positions in which we fill with a digit from M1. The other positions are filled by digits from M2. For example, let m = 5 and m1 = 3; if we chose 1,3,4, then the string M will be M1[1], M2[1], M1[2], M1[3], M2[2].

The same is done for the string D. Then M and D are combined by taking one digit at a time from M and D to produce the final string.

Binomial coefficients are precalculated in an additional table as choose[n][k] .

Then, the answer for length L with DIVPRO value of 2^twos * 3^threes * 5^fives * 7^sevens is:

   nmuls = floor((L + 1) / 2)
   ndivs = L - nmuls
   result = sum { d = 0 .. ndivs }
                sum { m = 0 .. nmuls }
                    table1[d][m][twos][threes] * 
                    table2[ndivs - d][nmuls - m][fives][sevens] *
                    choose[nmuls][m] * choose[ndivs][d]

This final calculation is fast enough to be performed for each test case.


#4

@dr0b3rts I had a solution quite similar to the one you posted, but I made one key difference in dividing up the tables which allowed me to compute that final sum in O(L) time instead of having the two nested loops.

  • Let us start with some terminology. I divided up the digits into “numerator digits” and “denominator digits”. If I am understanding your solution, that is very similar to your “divs” and “muls”.

  • Similar to you, I precomputed two tables with some DP. For my first table (ds23), I considered all of the numbers in {1,2,3,4,6,8,9}. For my second table (ds57), I considered only the numbers in {5,7}. This is an important distinction, as I believed that your solution places the ‘1’ in the other table. This difference seems to enable a significant reduction at the end. For me, my tables were indexed like this:

ds23[numerator digits][denominator digits][#2s in prime factorization of V][#3s in prime factorization of V]
ds57[numerator digits][denominator digits][#5s in prime factorization of V][#7s in prime factorization of V]

  • The real ‘crux’ here is that there is something special here about the 5’s and 7’s. We know that the numerator digits must at least contain enough 5’s and 7’s to satisfy the 5’s and 7’s in the prime factorization of V. Furthermore, any extra 5’s and 7’s in the numerator over and above what are required by the prime factorization of V must be paired exactly with that same combination of extra 5’s and 7’s in the denominator.

  • The way that we get to take advantage of this is that in computing the final sum, we don’t need to do a nested loop, we only need to do a 1-d loop. Perhaps this is more clearly seen with an example. Let us consider L=20 and V=5*7*7. Since L is 20, we must have 10 numerator digits and 10 denominator digits. We know that we must devote at least 3 numerator digits to 5’s & 7’s, and any additional numerator digits we devote to 5’s and 7’s must also be accounted for in the denominator. Thus, we end up with:

      ans = ds57[3][0][2][1] * ds23[7][10][0][0] * comb(10,3) * comb(10,0) +
            ds57[4][1][2][1] * ds23[6][9][0][0] * comb(10,4) * comb(10,1) +
            ds57[5][2][2][1] * ds23[5][8][0][0] * comb(10,5) * comb(10,2) +
            ds57[6][3][2][1] * ds23[4][7][0][0] * comb(10,6) * comb(10,3) +
            ds57[7][4][2][1] * ds23[3][6][0][0] * comb(10,7) * comb(10,4) +
            ds57[8][5][2][1] * ds23[2][5][0][0] * comb(10,8) * comb(10,5) +
            ds57[9][6][2][1] * ds23[1][4][0][0] * comb(10,9) * comb(10,6) +
            ds57[10][7][2][1] * ds23[0][3][0][0] * comb(10,10) * comb(10,7)

We don’t end up having to consider cases like ds57[6][1][2][1], because we know that those cases cannot result in a valid combination.

Other than this one key difference, I think our solutions are for the most part the same. Like you, I was able to avoid keeping track of negative numbers in the matrix indices by always doing the numerator digits first in the DP traversal before we starting to add any denominator digits.

I did make some optimizations in bounds checking on loop limits to really try to limit the number of terms in the sum of the O(L) loop. Ironically, I invested in these seemingly minor optimizations in order to try to get my Python solution to get accepted. When I couldn’t find any more algorithmic theory to exploit, I then decided to do the C++ port and ended up with a reasonably fast solution.


#5

I did as told in the editorial still my code is too slow to make the dp entries and store them in time. It takes around 12 secs to complete the procedure. Is there something more needed to be done to do it faster. Please help…


#6

@anton_lunyov My code was constantly giving SIGSEGV error. http://www.codechef.com/viewsolution/5254144
But, in the last line on including a check for bounds, the solution got expected. http://www.codechef.com/viewsolution/5254205
Can you please explain why this was happening. Also it would be great if you can provide me the test case where the 1st solution failed. Thanks in advance.


#7

Feeling robbed! :confused: I had everything in place except the n2 n3 n5 n7 taking negative values… wasted 10 days just because of this :frowning:


#8

very good editorial :slight_smile:


#9

@shahbaz I can’t say for sure, but it seems that your array for DP is too small. You are using the same approach as described in the editorial but left only 10 positions for negative powers of 5 and 7, while they could have 18 positions. But if you will try to enlarge the array you will get MLE. So try to follow editorial on how to handle all properly.


#10

@anton i am ignoring those powers that cannot be balanced at some later stages to make resultant an integer. I am using a check so as to maintain no seg fault occurs, and since those powers cannot be balanced later it wont have affect on the ans.


#11

@shahbaz Very nice trick to reduce memory.

Actually, your answers for V=0 are wrong.


#12

@anton thnx i corrected it still WA
http://www.codechef.com/viewsolution/1728113


#13

Still wrong answer for V=0.
Answer for L=35 and V=0 is 532793383.
You can read in editorial how to calculate it if you can’t get it work.


#14

thnx a ton finally submitted.


#15

You should write

if (dp[0][two][three][five][seven] == 0) continue;

after the line 44 of yours solution.
This will make your solution 9 times faster since the number of quadruples (two, three, five, seven) for which DP value is non-zero very small comparing with the product TWO * THREE * FIVE * SEVEN.

Also you are doing DP traversal wrong. You should write something like:


dp[1][TWO-1-two][THREE-1-three][FIVE-1-five][SEVEN-1-seven]+=dp[0][two][three][five][seven];

for the digit 1 and similar stuff for other digits.

Please, read editorial carefully.


#16

But I now see that it is quite hard to follow editorial at some places. I will edit to be easier to read.


#17

thanks for spotting that out. I sorted that out and managed to pre calculate dp table faster but still my solution getting TLE . http://www.codechef.com/viewsolution/1731305
Now am pre computing powers and using binary search too along with buffer read. Still not able to make it fast enough.
Please help…


#18
  1. You should calculate powers of 2, 3, 5, 7 in long long since they used to recover V which could be up to 10^18.

  2. It seems that your binary search could fall into infinite cycle. Consider the case when b=a+1 and sols[l-1][a][V] < value < sols[l-1][a+1][V] then any of your escape checks does not work, mid always = a so you will never escape from this loop.

  3. Why do so ugly copy-pasted thing in fill_table()? See how it is implemented in tester’s solution. Note when you find the bug in this step you should fix it twice only because you simply copy and paste this piece.


#19

@anton_lunyov thanks for pointing out that errors but i am still getting WA. Can you help please http://www.codechef.com/viewsolution/1746089


#20

sols should be long long since sols[l-1]*[0] is the value of V which could be up to 10^18.
And you should fix also comparator (replace UL by ULL I guess).

BTW, why don’t store sols[l-1]* as pair<long long,unsigned>
and use simply sort(sols[t],sols[t]+sols_counter[t]) like in tester’s solution.