×

# Codeforces Round 306 (Div 2) Problem C (550C) - Divisibility by eight

 0 Problem link 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 :) Link to Editorial asked 26 Sep '15, 19:30 492●1●10 accept rate: 14%

 4 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 :) answered 27 Sep '15, 05:33 5★limyude 47●1 accept rate: 100%
 2 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
 2 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!! answered 15 Nov '16, 18:55 2★chilling 21●2 accept rate: 0% Sorry but i m not asking about brute force! I want DP solution in precise way!.. Thank you! (15 Nov '16, 21:05)
 0 Can somebody provide the pseudo code or full solution to understand better in C/C++?!! answered 15 Nov '16, 14:58 2.8k●1●4●19 accept rate: 16%
 0 @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 2.8k●1●4●19 accept rate: 16%
 0 8|1000 so you need to check only the triples of digits of n answered 04 Nov '18, 01:20 0★iakoviid 1 accept rate: 0%
 0 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 0★iakoviid 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,212
×688

question asked: 26 Sep '15, 19:30

question was seen: 5,277 times

last updated: 04 Nov '18, 01:23