### niklasb's blog

By niklasb, 5 years ago, ,

I wrote a post about how to tackle certain problems on numbers using dynamic programming techniques over at Stack Overflow. This includes tasks like

• "Find the sum of integers X with digit sum S, where X <= Y" (Y given)
• "Find the number of palindromic integers between L and R"
• "Enumerate all integers between L and R that only have digits 4 and 7"
• "Find the probability that an integer X uniformly chosen from the range [L,R] has at least 10 common digits with a given number S"

that can all be solved with a very similar idea. Just in case somebody's interested.

• +30

 » 5 years ago, # | ← Rev. 3 →   0 Here is another good post
•  » » 5 years ago, # ^ |   0 Nice, I didn't know that one :) And you just added an image instead of an hyperlink.
•  » » » 5 years ago, # ^ |   0 Lol sorry look now!!
 » 5 years ago, # |   0 niklasb please elaborate your following statement under the heading Compute the number f(Y) of integers X with the property X ≤ Y and X is palindromic :If we can count the f(Y) with the additional restriction that all numbers X must have the same digit count as Y, then we can solve the original problem as well...
•  » » 5 years ago, # ^ |   0 You can just iterate over the number of digits, solve the arising subproblems where the number of digits is fixed and add up all the results.
•  » » » 5 years ago, # ^ |   0 @niklasb is my this implementation satisfies your explanation for O(n^4). If not, please suggest corrections. Thank you for your time.Compute the number f(Y) of integers X with the property X ≤ Y and X has the digit sum 60 int d[20][100]; bool mem[20][100]; int sum; int len; int f(int i, int sum_so_far, int lo, string cad) { if (i == len) { return (sum_so_far == sum); } if (sum_so_far > sum) { return 0; } int ret = 0; int dig; if (lo) { if (mem[i][sum_so_far]) { return d[i][sum_so_far]; } else { mem[i][sum_so_far] = 1; int r = 0; for (dig = 0; dig <= 9; ++dig) { r += f(i + 1, sum_so_far + dig, lo, cad); } d[i][sum_so_far] = r; return r; } } int limit; limit = cad[i] - '0'; for (dig = 0; dig <= limit; ++dig) { ret += f(i + 1, sum_so_far + dig, (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, cad); } 
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Your implementation is by the looks of it, but only after you add memoization to the !lo branch as well! I would recommend you not to pass around cad as a parameter of type string, because it might induce unnecessary copying. You could use const string& cad instead.
 » 5 years ago, # | ← Rev. 2 →   +4 This Google query for "spoj" "numbers between" A and B gives quite many SPOJ problems of this type.
•  » » 5 years ago, # ^ |   +6 Good observation, I added the query to my Q&A.
 » 5 years ago, # |   +3 There is lecture of Petr on Kharkov winter camps. But on Russian.
•  » » 5 years ago, # ^ |   0 Can you give link, please?
•  » » » 5 years ago, # ^ |   +3 link, page 262
•  » » » » 4 years ago, # ^ |   +4 Even though it's been a long time since this post was active, can someone help me find an english translation of the document?Google translate rejects the document as being too huge, and Yandex translate also only translates the first 30 pages. Where can I find the document in English? Or maybe, a translating service capable of translation?
•  » » » » » 4 years ago, # ^ |   0 I think you can split needed pages from this pdf file
•  » » » » » 4 years ago, # ^ |   +3 I am also looking for same(English version of problems) too, let me know if u find the way out.
•  » » » » » 4 years ago, # ^ |   0 Google was able to translate the entire document, however lost the formatting. It is hard to read the formulas without proper formatting.
 » 17 months ago, # |   0 could you please help me in solving : http://www.spoj.com/problems/COOLNUMS/
•  » » 17 months ago, # ^ |   0 Here is my solution which takes 0.35 secs only: https://ideone.com/wHAL6j There are < 1e5 valid digit sequences(at most 10 digits < 4e9). Generate them all. Then simply use concept of digit dp. dp(p,c,w) denotes number of valid numbers whose first upto p digits are generated, c denotes whether the number has become smaller or not than given number N and w denotes digit sequence till now.
•  » » » 17 months ago, # ^ |   0 can you please explain what did you mean by : "There are < 1e5 valid digit sequences"?I know this is a stupid ques but please don't mind.
•  » » » » 17 months ago, # ^ |   +1 It means given a number x when you sort its non-zero digits you get a sequence of digits. Only this sequence is enough to deduce if digits can be partitioned in 2 subsets or not using subset DP. If you see code I generate all digit sequences at start in 'a' whose size is about 93,000.
•  » » » » » 17 months ago, # ^ |   0 thanks mate :)
•  » » » » » 17 months ago, # ^ |   0 if possible can you please help me in optimizing this : https://ideone.com/PAVdOT
•  » » » » » » 17 months ago, # ^ |   0 https://ideone.com/27hw2y Instead of recalculating the DP each time, you can redefine it as dp(p,c3,c6,c9) = number of p-digit numbers having c3,c6,c9 respective counts of 3,6,9. Then you can preprocess the dp once, and calculate each answer in O(50*17*10) for a single case by just iterating on number of 369's and on the number. Works in 0.03 secs on SPOJ.
•  » » » » » » » 17 months ago, # ^ |   0 "calculate each answer in O(50*17*10) for a single case by just iterating on number of 369's and on the number" can you please explain it a little? I have seen your code but didn't understand the count function.