Is there anyone who can explain the DP approach of this question! I got AC by recursive method but i wanna know about DP solution. So please explain the DP part of that one.
2 Likes
you can look at my solution : https://www.hackerrank.com/contests/w28/challenges/lucky-number-eight/submissions/code/1300062791
property of division of 8 is that it’s last 3 digits are divisible by 8.At first i have counted all 1 len and 2 length subsequences and then for 3 onwards calculated using dp.
specifically in my solution,dp1[k][i] denotes subsequences whose (last 1 digit 8 )=k,dp2[k][i] denotes subsequences whose (last 2 digits 8 )=k and same for dp3.
1 Like
Sorry your solution is complicated to understand! Can you please elaborate more! Basically from this part dp2[i][(k*10+to(s[i]))%8]
The number is formed by concatenating the non-contiguous subsequences, which implies that the number itself is a subsequence and vice-versa.
So the problem boils down to counting the ways you can make a subsequence divisible by 8. This can be done by Dynamic Programming. At any position of the sequence, you need to consider two cases:
1. Concatenate the digit at the position with your current subsequence and move to next position.
2. Leave the digit and move to next position.
The idea can be coded with states: Current position and Remainder of the subsequence modulo 8.
@bansal1232 this is the code of problem lucky number eight.
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int len;
char buf[200010];
int f[200010][8];
void add(int& a , int v)
{
a += v;
if(a >= mod)a -= mod;
}
int main()
{
scanf("%d" , &len);
scanf("%s" , buf + 1);
f[0][0] = 1;
for(int i = 1 ; i <= len ; i++)
{
for(int j = 0 ; j < 8 ; j++)
add(f[i][j] , f[i - 1][j]);
for(int j = 0 ; j < 8 ; j++)
add(f[i][(j * 10 + buf[i] - '0') % 8] , f[i - 1][j]);
}
int ans = f[len][0];
ans = (ans - 1 + mod) % mod;
printf("%d\n" , ans);
return 0;
}
The editorial for this problem is also available you can also see that. I have seen the editorial, (the code is so small of about 8-9 lines) but I don’t think I should post the editorialist’s code.
1 Like
first 2 nested for loops are just to calculate 1 length and 2 length arrays.From next it is for len>=3.
dp1[i][to(s[i])%8]+=powmod(2,i-1,MOD) denotes there are these many subsequences whose last 1 digit gives reminder (s[i]%8).
dp2[i][(k*10+to(s[i]))%8] denotes there are these many subsequences whose last 2 digits gives reminder (s[i]%8).
ex. (1234 here last two digits are 34 and it gives reminder (34%8));
dp2[i][(k10+to(s[i]))%8]+=dp1[i-1][k] is I am conacatenating s[i] with all subsequences whose last 1 digit gives reminder k and their last index <i .Now int these subsequnces,last 2 digti gives reminder k10+s[i] as string will be like …ks[i].Then I am taking cummulative sum and doing the same for 3 length subsequences. adding all 3 length subsequnces to previous answer.
Tell me one thing that how can you concatenate digits by multiplying 10 into (1,2,3,…7) ?
Let s be the given string of digits and n be the length of this string.
Consider f(i, j) as a function which is the number of subsequences upto position i (1-indexed) which when represented as a number and divided by 8 give remainder j. At each position i, we can either take the current digit into a subsequence, or ignore it.
If we ignore a digit s[i], the number of subsequences which give j modulo 8 would be simply f(i-1, j).
If we choose to take the digit s[i], the number of subsequences which give j modulo 8 are the sum of f(i-1, k), for all such k where (k \times 10+s[i]) \% 8=j. This is because when we append a digit d to an existing number S, the following holds: (S \times 10 +d) \% 8 = ((S \% 8) \times 10 + d) \% 8. This is the tricky part which took me a while to grasp.
f(i, j) = f(i-1, j) + \sum f(i-1, k) : (k \times 10 + s[i]) \% 8 = j
Our answer is then f(n, 0) - 1, because we must exclude the empty subsequence which will be considered divisble by 8.
While computing however, one can be a little clever to avoid running a loop to find the required k values for each i, j… by simply running separate loops for j and k. (Or put them the same loop, at the price of losing clarity)
m = 1000000007
dp = 2D array of size (n+1)×8
dp[0][0] = 1 // empty subsequence equivalent to 0; 0 modulo 8 is 0
for i in [1..n]:
for j in [0..7]:
dp[i][j] += dp[i-1][j] // ignore s[i]
for k in [0..7]: // working separately for each k
dp[i][(k*10+s[i])%8] += dp[i-1][k] // include s[i]
for j in [0..8]:
dp[i][j] %= m // maintain modulo 10^9 + 7
The required answer is then (dp[n][0] - 1 + m) % m.
Complexity is \mathcal{O}(8 \times n) which is \mathcal{O}(n).
Accepted code in Python3 here.
Feel free to ask if something isn’t clear 
1 Like
Please explain that tricky part in detail! I mean how did you able to deduce this with just single line formula?
@bansal1232 that particular line is just modular arithmetic. Suppose I have the input as “21533”, and consider we are at i=5 and k=1. Then by definition f(i-1, k) = f(4, 1) will the number of sequences upto position 4 which give 1 as remainder when divided by 8. These are “1”, “25”, “153” and “2153” so f(4, 1) = 4. At i=5 I find the digit 3, so s[i]=3. So if I append 3 to each of these sequences, the remainder of the new sequences would be
(1×10+3)%8 = 13%8 = 5
(25×10+3)%8 = 253%8 = 5
(153×10+3)%8 = 1533%8 = 5
(2153×10+3)%8 = 21533%8 = 5
As you can see both are the same as (k*10+s[i])%8 where the k=1 and s[i]=3. So basically the logic behind this is that appending 3 to all the sequences that give 1 modulo 8 will now give 5 modulo 8. So it’s clear that f(4, 1) is a part of f(5, 5).
Similarly f(4, 5) also contributes to f(5, 5) as (5×10+3)%8 = 5. And finally f(i-1, j) always contributes to f(i,j) so f(4,5) will again be considered into f(5,5). In the end f(5, 5) = f(4, 1) + f(4, 5) + f(4, 5).
I hope this example clarifies things somewhat!
#define MOD 1000000007
#define MAXN 200000
long long F[2][8];
char S[MAXN+10];
int main()
{
int N;
scanf("%d", &N);
scanf("%s", S);
int digit;
bool pre = 0;
bool cur = 1;
for (size_t i = 0; i < N; ++i) {
digit = S[i] - '0';
// here we do not consider S[i] so we just copy the previous value.
for (int k = 0; k < 8; ++k) {
F[cur][k] = F[pre][k];
}
// here we consider S[i], and only S[i] as a subsequence (length = 1)
++ F[cur][digit % 8];
// here we add S[i] to all the subsequence and find the new remainder(val%8) and update
// the respective remainder. So, after this step number of subsequence giving remainder
// j(from 0-8) will change.
// eg: 968
// s[i]=9. no of subsequence giving remainder 1 is 1
// s[i] 6. no of subsequence giving remainder 1 is 1, no of subsequence giving remainder
// 6 is 1, no of subsequence giving remainder 0 is 1(that is 96). and so on
for (int k = 0; k < 8; ++k) {
F[cur][(k * 10 + digit) % 8] += F[pre][k];
F[cur][(k * 10 + digit) % 8] %= MOD;
}
pre = !pre;
cur = !cur;
}
printf("%lld\n", F[pre][0] % MOD);
}
PS: JUST REMEMBER that dp[i][j] stores number of subsequence of giving the remainder j.let the subsequence be abcd and it gives a remainder x. we add e to the subsequence abcd and it becomes abcd10+e =abcde. take the modulo. (abcde)%mod or (abcd10+e)%mod or (x*10+e)%mod.
recursive method: https://www.hackerrank.com/contests/w28/challenges/lucky-number-eight/submissions/code/1300465668
long long int fun(int idx,int m)
{
if(idx>=n)
return (m==0)%MOD;
if(dp[idx][m]!=-1)
return (dp[idx][m])%MOD;
long long int ans=fun(idx+1,m)%MOD;
ans+=(fun(idx+1,(m*10+(ar[idx]-‘0’))%8))%MOD;
return dp[idx][m]=(ans)%MOD;
}