Sunday, 23 June 2013

Digit Dynamic Programming problem

We will solve a DP problem today.

dp state is (index, tight).
where index is the position where we currently are (consider the process of constructing solution from left to right).
where tight is a variable which states the number which we have constructed up to now, is strictly less/greater or equal. Tight is false, means it has become less or greater. but true when equal.

Ex. 1. http://www.spoj.com/problems/SQAMOD/
find no of binary numbers less than a given n digit number S which have sum of squares of digits modulo 3 to be zero,
Solution:
1. dp (index, int sumModulo3, int tight):
      So let us see the transitions to different states. You can understand that by reading the code.

#include <iostream>
#include <cstdio>
#include <list>
#include <queue>
#include <cstring>
#include <algorithm>
#include <time.h>
#define maxn 100000
using namespace std;
typedef long long LL;
char s[100005];
int n;
LL mod = 1000000007;
LL memo[100005][3][2];
LL dp (int index, int modValue,int tight)
{
LL &res = memo[index][modValue][tight];
// if res is not equal to -1, then just return it.
if (res == -1)
{
res = 0;
if (index == n)
{
// we are constructing the values from left to right,
// means everytime we are taking some number for every index going from left to right,
// in this way our number is getting constructed.
// !tight means less than value of s.
// modValue should be zero. As we need the number to be 0 mod 3.
if (!tight & modValue == 0)
res = 1;
}
else
{
// if number constructed upto now is same as the number S taken upto digit index.
if (tight)
{
for (int i = 0; i <= s[index] - '0'; i++)
{
if (i == s[index] - '0')
{
// value is still equal. Hence it is stil tight.
res += dp (index + 1, (modValue + i * i) % 3, 1);
res %= mod;
}
else
{
// value becomes less so it is not tight, tight becomes false.
res += dp (index + 1, (modValue + i * i) % 3, 0);
res %= mod;
}
}
}
else
{
// if already tight is false, then you can take any number in this index, as it is already
// less.
for (int i = 0; i < 10; i++)
{
// it is already not tight, so not going to be tight again.
res += dp (index + 1, (modValue + i * i) % 3, 0);
res %= mod;
}
}
}
}
return res;
}
int main()
{
//freopen ("input.txt", "r", stdin);
//freopen ("output.txt", "w", stdout);
int T;
scanf ("%d", &T);
while (T--)
{
scanf ("%s", &s);
n = strlen (s);
memset (memo, -1, sizeof(memo));
LL ans = dp (0 , 0, 1);
printf ("%d\n", ans);
}
return 0;
}
view raw sum.cpp hosted with ❤ by GitHub

3 comments:

  1. Hi you know other problems seem like this. Tutorial about this Digit DP? Thanks.

    ReplyDelete
  2. Can you please help me out with the running time of this solution.

    ReplyDelete
    Replies
    1. It visits all the possible States (10^5 * 3 *2).

      Delete