PROBLEM LINK:Author: Vivek Hamirwasia DIFFICULTY:MEDIUM PREREQUISITES:PROBLEM:If positive integer N has decimal representations d_{1}d_{2}...d_{L}, where n_{1} ≠ 0, then DIVPRO(N) = d_{1} / d_{2} * d_{3} / d_{4} * .... If at some point division by zero occurs the DIVPRO(N) is undefined (so digits at even positions should be nonzero). For the given integers 0 ≤ V < 10^{18} and 1 ≤ L ≤ 36 you need to find the number of positive Ldigit integers N having DIVPRO(N) = V and output this number modulo 2^{32}. You should be able to answer up to 320,000 such tests in 3 seconds. QUICK EXPLANATION:If V = 0 then the count is 9^{L − X} * (10^{X} − 9^{X}) where X = floor((L − 1) / 2). When V > 0 the answer is nonzero only when V has the form 2^{n2} * 3^{n3} * 5^{n5} * 7^{n7}. Let dp[L][n2][n3][n5][n7] be a count of Ldigit positive integers N having DIVPRO(N) = 2^{n2} * 3^{n3} * 5^{n5} * 7^{n7}, where n2, n3, n5, n7 can be negative. Then values of dp[L][][][][] could be recalculated from values of dp[L1][][][][] as follows. For all arrays (n2, n3, n5, n7) such that dp[L1][n2][n3][n5][n7] ≠ 0 we iterate over all digits d from 1 to 9, inclusive, and add dp[L1][n2][n3][n5][n7] to dp[L][g2[d]n2][g3[d]n3][g5[d]n5][g7[d]n7], where d = 2^{g2[d]} * 3^{g3[d]} * 5^{g5[d]} * 7^{g7[d]}. The array for dp could created as To make computations modulo 2^{32} simply use unsigned 32bit integer type as it is. During DP step save all nonzero answers to some array. EXPLANATION:At first we assume that V ≠ 0, then it is clear that all digits in N should be nonzero. Hence we consider only such N from now on. The key observation is that DIVPRO(N) has the form 2^{n2} * 3^{n3} * 5^{n5} * 7^{n7}, where n2, n3, n5, n7 arbitrary integers (even negative). This is because each nonzero decimal digit has only 2, 3, 5, 7 as prime divisors. Hence integer V should be of the same form but with nonnegative n2, n3, n5, n7, otherwise DIVPRO(N) ≠ V for any N. There are quite a few values of V of this form up to 10^{18}  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 Ldigit positive integers N having DIVPRO(N) = 2^{n2} * 3^{n3} * 5^{n5} * 7^{n7}. 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 0digit number is an empty number which has DIVPRO value 1 = 2^{0} * 3^{0} * 5^{0} * 7^{0} (it is math and CS convention to set empty products as 1). It is quite clear how recalculation should be done. Let d_{1}d_{2}...d_{L} is decimal representation of N. Then This observation shows that values of dp[L][][][][] could be recalculated from values of dp[L1][][][][] as follows. For all arrays (n2, n3, n5, n7) such that dp[L1][n2][n3][n5][n7] ≠ 0 we iterate over all digits d from 1 to 9, inclusive, and add dp[L1][n2][n3][n5][n7] to dp[L][g2[d]n2][g3[d]n3][g5[d]n5][g7[d]n7], where d = 2^{g2[d]} * 3^{g3[d]} * 5^{g5[d]} * 7^{g7[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 nonzero. 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 Ldigit 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 Ldigit number and DIVPRO(N) = 2^{n2} * 3^{n3} * 5^{n5} * 7^{n7} 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 dprecalculation 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 Note that in our DP we calculate all values of dp[L][][][][] from values of dp[L1][][][][], hence let's store in memory only dpvalues for two consecutive values of L each time. We could, for example, create an array of the form But now in the end we will have dpvalues 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 nonzero dpvalues 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 10^{18} 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 nonzero dpvalue. 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 nonzero (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 Ldigit 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 9^{L2 + 1} in the answer. For digits at odd positions (except the first digits) we count as follows. The total number of choices is 10^{L1 − 1} but we should subtract those choices where all digits are nonzero which is 9^{L1 − 1}. The final remark. To create dparray above in language that does not support such indexation we could create it as The very final remark. To do calculations modulo 2^{32} you actually do not need to do any special. Just do all calculations using 32bit integer type (signed and unsigned). Overflow that will occur during calculation behaves exactly as modulo 2^{32} 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(maxL^{5} * B + T * log maxL^{4}), where B = 9 is the number of nonzero 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 nonzero dpvalues. maxL^{4} is an upper bound for the number of values of V for which we have some nonzero dpvalue. We use binary search for T tests over arrays of size with upper bound O(maxL^{4}), 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. RELATED PROBLEMS:
This question is marked "community wiki".
asked 15 Jan '13, 15:00

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:
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 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 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 Then, the answer for length L with DIVPRO value of 2^twos * 3^threes * 5^fives * 7^sevens is:
This final calculation is fast enough to be performed for each test case. answered 16 Jan '13, 12:22

@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.
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]
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. answered 17 Jan '13, 12:56

Can u please tell me where my code failed, http://www.codechef.com/viewsolution/1723814 answered 16 Jan '13, 12:13
@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.
(16 Jan '13, 13:40)
@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.
(17 Jan '13, 12:21)
@shahbaz Very nice trick to reduce memory. Actually, your answers for V=0 are wrong.
(17 Jan '13, 13:24)
@anton thnx i corrected it still WA http://www.codechef.com/viewsolution/1728113
(18 Jan '13, 11:10)
Still wrong answer for V=0.
(18 Jan '13, 11:23)
thnx a ton finally submitted.
(18 Jan '13, 14:06)
showing 5 of 6
show all

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.... answered 19 Jan '13, 14:44
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 nonzero very small comparing with the product TWO * THREE * FIVE * SEVEN. Also you are doing DP traversal wrong. You should write something like: dp[1][TWO1two][THREE1three][FIVE1five][SEVEN1seven]+=dp[0][two][three][five][seven];for the digit 1 and similar stuff for other digits. Please, read editorial carefully.
(19 Jan '13, 15:34)
But I now see that it is quite hard to follow editorial at some places. I will edit to be easier to read.
(19 Jan '13, 15:36)
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...
(20 Jan '13, 17:45)
(21 Jan '13, 14:30)
@anton_lunyov thanks for pointing out that errors but i am still getting WA. Can you help please http://www.codechef.com/viewsolution/1746089
(23 Jan '13, 22:21)
BTW, why don't store
(24 Jan '13, 01:44)
showing 5 of 6
show all

@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. answered 01 Nov '14, 22:44

Feeling robbed! :/ I had everything in place except the n2 n3 n5 n7 taking negative values.. wasted 10 days just because of this :(
very good editorial :)