Блог пользователя niklasb

Dynamic Programming on Integers
Автор niklasb, 11 лет назад, По-английски

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.

Теги dp
  • Проголосовать: нравится
  • +30
  • Проголосовать: не нравится

»
11 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Here is another good post

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 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...

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 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);
}
      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
        ← 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.

        → Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

This Google query for "spoj" "numbers between" A and B gives quite many SPOJ problems of this type.

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

There is lecture of Petr on Kharkov winter camps. But on Russian.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you give link, please?

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      link, page 262

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +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?

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          I think you can split needed pages from this pdf file

          → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          I am also looking for same(English version of problems) too, let me know if u find the way out.

          → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Google was able to translate the entire document, however lost the formatting. It is hard to read the formulas without proper formatting.

          → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

could you please help me in solving : http://www.spoj.com/problems/COOLNUMS/

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 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.

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +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.

        → Ответить
        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          thanks mate :)

          → Ответить
        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          if possible can you please help me in optimizing this : https://ideone.com/PAVdOT

          prob : http://www.spoj.com/problems/NUMTSN/

          → Ответить
          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 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.

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится 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.

              → Ответить