# The Hackerearth January Easy Challenge

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

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 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;
``````

}

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

Sure, I solved it, what do you need?

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

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

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