Combinatorics problem

general
, ,
1

Hello,

I have been trying for the past few days to wrap my head around Combinatorics problems and how to reason about them.

At the moment, I have this problem:

Given a binary string of length N (2 <= N <= 1000000) consisting of zeros, ones and ?, where ? stands either for a 0 or for a 1, I need to find out the number of ways in which I get to fill all the ? such that there is not allowed to have K (2<=K<=N) consecutive 1s.

Example:

K=3

1??1

The answer for this case will be 3, as we can have:

1001
1101
1011

but we can not have:

1111

as we would have 3 consecutive ones.

  • My solution ideas:

As K is very large, we can’t afford to use a brute-force solution, otherwise we could simply enumerate all the possibilites and filter the ones we didn’t need.

There are 2^(number of ?) possible configurations so possibly we are looking at some form of DP solution and or closed-formula?

I tried to come up with some DP state but, couldn’t think on any good one…

Can someone point me in the right direction? I’d really like to get better at solving these kinds of problems!

Best,

Bruno

2 Likes
2

Consider the problem from a different perspective: “if I want to put a 1 instead of this ?, how many times could I have done this before without violating the condition for sequences ending with this ?”?. There’s some k such that if we put 1 instead of ? k times (and if there were at least k+1 ?s before this one, then we’d put 0 instead of the _k+1_st) before without violating the condition, then we could also do that for any smaller k. Therefore, we could take a DP that says the number of ways to solve the problem if the sequence ended with s[i]=’?’, replaced with a 0; for each next ?, we’d just bin-search the required k (watch out for fixed zeroes in the sequence) and sum up all DP answers from these k ?s, which can be done in O(1) by converting the DP answers into their prefix sums. Due to binsearch, the complexity is O(N\log{N}) (actually, N can be just the number of zeroes in the sequence, since it can be split by fixed zeroes and consecutive ones can be compressed).

2 Likes