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 :) asked 26 Sep '15, 19:30

First of all, note that this problem is asking about taking a nonempty 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 nonempty 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 :) answered 27 Sep '15, 05:33

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 :
` for more clarity click here answered 15 Nov '16, 16:36

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. LINKhttp://codeforces.com/contest/550/submission/22223007 first I got memory limit ,after that I optimize by adding another while loop and passed!! answered 15 Nov '16, 18:55
Sorry but i m not asking about brute force! I want DP solution in precise way!.. Thank you!
(15 Nov '16, 21:05)

Can somebody provide the pseudo code or full solution to understand better in C/C++?!! answered 15 Nov '16, 14:58

@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!! answered 15 Nov '16, 17:30

81000 so you need to check only the triples of digits of n answered 04 Nov '18, 01:20

Very new to all this sorry https://codeforces.com/contest/550/submission/45255726 stuck at test 21 dont know why answered 04 Nov '18, 01:23
