### niklasb's blog

By niklasb, 6 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

 » 6 years ago, # | ← Rev. 3 →   0 Here is another good post
•  » » 6 years ago, # ^ |   0 Nice, I didn't know that one :) And you just added an image instead of an hyperlink.
•  » » » 6 years ago, # ^ |   0 Lol sorry look now!!
 » 6 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...
•  » » 6 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.
•  » » » 6 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); } 
•  » » » » 6 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.
 » 6 years ago, # | ← Rev. 2 →   +4 This Google query for "spoj" "numbers between" A and B gives quite many SPOJ problems of this type.
•  » » 6 years ago, # ^ |   +6 Good observation, I added the query to my Q&A.
 » 6 years ago, # |   +3 There is lecture of Petr on Kharkov winter camps. But on Russian.
•  » » 6 years ago, # ^ |   0 Can you give link, please?
•  » » » 6 years ago, # ^ |   +3 link, page 262
•  » » » » 5 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?
•  » » » » » 5 years ago, # ^ |   0 I think you can split needed pages from this pdf file
•  » » » » » 5 years ago, # ^ |   +3 I am also looking for same(English version of problems) too, let me know if u find the way out.
•  » » » » » 5 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.