Help needed with this Dynamic Programming Question

general
, , , , ,
1

I am preparing for INOI and am stuck on this problem here: http://acm.timus.ru/problem.aspx?space=1&num=1081

I am just a beginner with DP so I am not getting any idea on how we will solve this question. Can anyone explain me the proper logic of the solution to this problem instead of just giving the code?

1 Like
2

First let us start with counting the number of binary sequences having length ‘n’ and no adjacent ones

We use the array “DP” to store the count corresponding to the length

First place in a binary sequence can be either 0 or 1

Now coming to the most interesting part,
On second place you can fill 0, irrespective of what you have filled before but if you want to fill up the 1 at this position it is necessary to fill 0 at the previous position

In simpler terms, it means that if you want to fill a position with ‘1’ it is necessary that its previous position is filled with ‘0’ and if you want to fill a position with ‘0’ its previous position can be filled by either ‘0’ or '1’

Read and try to understand the above line because it is the key to the solution

So for any length n, let us construct our binary sequence in the backward direction:

there are two possible things to fill either ‘0’ or ‘1’, if you fill ‘0’ you have to construct the ‘n-1’ length sequence in the same way, else if you fill ‘1’ it is need to be guaranteed that previous position is filled with ‘0’ so you have then to construct ‘n-2’ length sequence

So a general compute function can be given as:

def compute(n):
    if n==0:
        return 1
    elif n==1:
        return 2
    else:
        return compute(n-1)+compute(n-2)

This function looks very same as that of "Fibonacci" just the starting seed value are 1 and 2 instead of 0 and 1

In the above compute function, as you see that several sub-problems overlap and are computed repeatedly so this can be memoized and the value can be computed as:

def compute():
    DP[0] = 1
    DP[1] = 2
    for i in range(2,n+1):
        DP[i] = DP[i-1] + DP[i-2]

Now coming to the question, first thing is that if value of k is greater than DP[n] such a sequence cannot exist

Let us consider all the 2 length binary sequences having no adjacent ones, 00, 01, 10

Now considering all the 3 length binary sequences having no adjacent ones, 000, 001, 010, 100, 101

See the part in the bold in above line carefully, you see that if you fill ‘0’ then the sequence will be same as that for the n-1 length

Thus if the value of k is less than or equal to DP[n-1], you print the ‘0’ and start constructing the n-1 length sequence with the same value of k

But if the value of k is greater than DP[n-1], than you have to print the ‘10’ and start constructing the n-2 length sequence with value of k decreased by DP[n-1]

It is necessary that there are no two adjacent ones in the sequence, so if you fill ‘1’ at current position it is necessary to fill ‘0’ at next position thus we print ‘10’ in the above case

I recommend you first to solve this problem on your own, but if you are unable to solve, refer to my solution

Happy Coding :slight_smile:

8 Likes
3

@pulkitsinghal any resource from where you have learnt this(DP) and other topics…i am a beginner and have just started reading these stuff but can’t judge which resource is better than other…@ketanhwr sorry for post hijack :slight_smile:

1 Like
4

DP is just a matter of practice and i am too a newbie in this
Although Topcoder tutorials are sufficient for startup :slight_smile:

5

thanks a lot :slight_smile:

6

thanks a lot @

7

Thanks a lot! :slight_smile:

8

I wanted to ask the same @emin3m :stuck_out_tongue:

9

And that was a brilliantly written answer!

10

@ketanhwr Thanks :slight_smile: