How do I solve this problem using DP? I have read the editorial and I don’t understand the DP approach. Any help would be appreciated 
First of all, note that this problem is asking about taking a non-empty subsequence of the string of digits (call it S) such that the remainder when divided by 8 is 0. This hints at using the dp state as such: dp(index, modval). Once modval is 0, you have an answer that gives remainder 0 when divided by 8.
The idea of this dp is, like most subsequence dp problems, when you are at dp state dp(i, m), and assuming S[i] = k (where 0 <= k <= 9), then you either TAKE or IGNORE the digit k. I.e. dp(i, m) can lead to state dp(i+1, (m * 10 + k) % 8) [TAKE] or dp(i+1, m) [DISCARD]. This dp terminates with an answer when modval reaches 0, or without an answer when i goes out of bounds of the string.
Note that because you need to print the string of digits for the answer, you might need to pass the string used so far to get to state dp(i, m) as a parameter as well.
Also, note that you need a non-empty subsequence, so dp(0,0) is not the answer you want. (How would you include at least one digit into the string for this dp?)
Hope this helps! Happy coding
3 Likes
Can somebody provide the pseudo code or full solution to understand better in C/C++?!!
Since u want just the sudo code , i will give a brief description of the solution and then the sudo code.
dp[i][j] = true iff its possible delete digits from a0 … ai such that we get a non zero number “num” such that num = j mod 8 else false ;
Previous[i][j] = -1 if the ai is the 1st digit of num else
Previous[i][j] = k , where ak is the previous digit
sudo code :
//A is the input and PP is our Previous array as described above
`dp[0][(A[0]-'0')%8]=1 ;PP[0][(A[0]-'0')%8]=-1;
//we built the 2 arrays as follows :
for(int i=1;i<A.size();++i)
{
int num= A[i] - '0' ;
dp[i][num%8] = 1 ;
PP[i][num%8] = -1 ;
for(int j=0;j<8;++j)
{
if(dp[i][(j*10 + num)%8]==0 && dp[i-1][j]==1) dp[i][(j*10 + num)%8]=1 , PP[i][(j*10 + num)%8]=j ;
if(dp[i][j]==0 && dp[i-1][j]==1) dp[i][j]=1 , PP[i][j]=j ;
}
}
// to check if such number exists :
for(int i=0;i<A.size();++i)
{
if(dp[i][0]==1)
{
cout<<"YES"<<endl ;
//find ans will print the required number
find_ans(i,0) ;
return 0 ;
}
}
void find_ans(int i,int j)
{
if(PP[i][j]==-1) { cout<<A[i]; return ; }
int k = PP[i][j] ;
find_ans(i-1,k) ;
if((k*10 + A[i]-'0')%8 == j) cout<<A[i] ;
}
`
for more clarity click here
1 Like
@hokagenaruto I appreciate your efforts and your way! But still i need to get more explanation about your first line "dp[i][j] = true iff its possible delete digits from a0 … ai such that we get a non zero number “num” such that num = j mod 8 else false "…
If would be nice if you clarify this more!
Thank you!!
You can use brute for also.if string has a zero ,answer will be yes and number will be 0.otherwise find all combination of two and three digits check it if it is divisible by 8.
LINK-http://codeforces.com/contest/550/submission/22223007
first I got memory limit ,after that I optimize by adding another while loop and passed!!
1 Like
Sorry but i m not asking about brute force! I want DP solution in precise way!..
Thank you!
8|1000 so you need to check only the triples of digits of n
Very new to all this sorry
https://codeforces.com/contest/550/submission/45255726
stuck at test 21 dont know why