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

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

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
  • Проголосовать: не нравится

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

Here is another good post

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

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

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

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

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

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

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

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

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

→ Ответить