Is there anyone who have already solved this problem?

[Problems][1]

Ikshu recently learnt to generate random numbers. He is generating stream binary numbers. Uptil now he has generated N bits of the binary number. Now, he wants to know if there is a streak of contiguous 1’s of length K.

Help him to find the probability of existence of such a streak in his binary number.

Assume that probability of generating a one and zero is equal i.e 0.5.

Input:

First and only line of input contains two space separated integers N and K as described above.

Output:

output contains one line containing probablity. output should be in n/m form where it is n/m is in its lowest fraction.

Constraints:

1<=N<=60

1<=K<=N

[1]: http://www.hackerearth.com/january-easy-challenge15/algorithm/ikshus-love-for-binary-numbers/

Sure, I solved it, what do you need?

@pkacprzak Sorry for missing. I need an algorithm to solve it

Since I really encourage you to solve it on your own, I’ll give you a few hints:

Let’s count the number of binary strings of length `n`

which don’t have a substring of `k`

consecutive 1’s. If we can do this, we can obviously solve the problem.

Let `dp[n]`

be the number of binary strings of length `n`

which don’t have a substring of `k`

consecutive 1’s and which has the `n-th`

bit set to 0.

Obviously, the base case, `dp[1] = 1`

i.e. the empty string.

Then you can compute `dp[n + 1]`

based on values of `dp[i]`

for some `i < n`

. Try to solve it on your own, but if you stuck, I’ll give you a more detailed explanation.

The answer to the problem is `dp[n + 1]`

, where `n`

is the length of desired binary string.

EDIT:

You can see my code from the contest here:

3 Likes

I’m not good at dp Can you describe it more clearly?

I solved this using a formula and managed 12 points only. I am new to dp and any furthur help would be heartfully appreciated.

#include

#include<math.h>

using namespace std;

int main()

{

int n,k;

long long int num,dem,y;

cin>>n>>k;

int z=n-k+1;

y=pow(2,z);

num=y-1;

dem=pow(2,n);

int i;

```
cout<<num<<"/"<<dem;
```

}

@leduongtuananh @subham_pasari

This problem can be solved easily using the Digit DP

I solved it and managed to get the 100 points

My Solution ideone.com/ipZyDb

For learning Digit DP, visit Praveen Dhinwa Blog, A nice explanantion is provided there

1 Like

Please check my code for a more detailed explanation (link in the post). I hope that it helps.