The Hackerearth January Easy Challenge

general
, , ,
1

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/

2

Sure, I solved it, what do you need?

3

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

4

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
5

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

6

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;

}

7

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

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