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]: Log In | HackerEarth
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;
}
@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
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.