You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

rishivikram's gravatar image

5★rishivikram
492110
accept rate: 14%


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 :)

link

answered 27 Sep '15, 05:33

limyude's gravatar image

5★limyude
471
accept rate: 100%

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

link

answered 15 Nov '16, 16:36

hokagenaruto's gravatar image

5★hokagenaruto
103
accept rate: 0%

edited 15 Nov '16, 16:41

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!!

link

answered 15 Nov '16, 18:55

chilling's gravatar image

2★chilling
212
accept rate: 0%

edited 15 Nov '16, 19:09

Sorry but i m not asking about brute force! I want DP solution in precise way!..

Thank you!

(15 Nov '16, 21:05) bansal12325★

Can somebody provide the pseudo code or full solution to understand better in C/C++?!!

link

answered 15 Nov '16, 14:58

bansal1232's gravatar image

5★bansal1232
2.8k1419
accept rate: 16%

@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!!

link

answered 15 Nov '16, 17:30

bansal1232's gravatar image

5★bansal1232
2.8k1419
accept rate: 16%

8|1000 so you need to check only the triples of digits of n

link

answered 04 Nov '18, 01:20

iakoviid's gravatar image

0★iakoviid
1
accept rate: 0%

Very new to all this sorry https://codeforces.com/contest/550/submission/45255726 stuck at test 21 dont know why

link

answered 04 Nov '18, 01:23

iakoviid's gravatar image

0★iakoviid
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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