Problem Link: contest, practice Difficulty: Easy Prerequisites: DP, Implementation Problem: We need to count the number of 01strings of N chars, such that any continuous section of ones of them have a length which is a multiple of K. I.e, if K = 2, then string 00011001111 is good, while 0011100 is not. Explanation: This problem is a dynamic programming(DP) problem. As far as it's so, we need to think about the parameters we should use for DP. Let's consider the following function F[i], denoting the number of 01strings of i chars, such that any continuous section of ones of them have a length which is a multiple of K. It's a quite obvious observation, that the answer for the problem is F[N]. Let's consider some border cases. F[0] = 1. It is quite obvious, since there is an empty string which fully satisfies to our conditions. F[1] = 2, in case K = 1, otherwise 1. If K = 1, then strings 0 and 1 both satisfy to out conditions, otherwise string 1 doesn't satisfy. Well, it's time to present the recurrent formula. F[i] = F[i  1] + F[i  K  1] + ... + F[i  c * K  1] (i  c * K  1 is nonnegative, while i  (c + 1) * K  1 is negative). Also, in case i is a multiple of K, we should increase F[i] by 1. The logic of the formula is the following: Let's consider the continuous section of ones, which ends in the position i. It may have a length equal to 0, K, 2 * K and so on. For better understanding, let's assume that it's length equals to 3 * K. Then, all the positions from the range [i  3 * K + 1 ... i] are ones and (i  3 * k)'th position is a zero. We know how do the positions [i  3 * k ... i] look, but we don't know what's going on before them. That's why we need to add summand F[i  3 * k  1] to F[i]. In case, when i is a multiple of K, we add 1, because we can't use the logic described above. So, here is a pseudocode, which shows the implementation of this DP:
Well, we have a working polynomial solution, which runs in O(N ^ 2 / K) time. In case K is a quite big number, this solution works fast, but for smaller values of K it's getting TLE. Let's improve it! The key observation is, that the loop for counting current F[] is needless. Formally, F[i] = G[(i  1) modulo K], where G[(i  1) modulo K] is the sum of all previous F[x], such that (i  x  1) is a multiple of K. We should maintain G[] while counting F[]. As before, in case i is a multiple of K, we should increase F[i] by 1. Here is a pseudocode, which shows the implementation of the lineartime algorithm:
Setter's Solution: link Tester's Solution: link
This question is marked "community wiki".
asked 23 Feb '14, 15:05

I reached the answer by splitting the last digit into two cases. If the last digit is a 1, then all last k digits need to be 1's otherwise this array is not good. Now if the last digit is a 0, then we have the same cases at the n1'th position. Hence ans[n]=ans[nk]+ans[n1] Also I handle the case where n less than k and n equal to k separately, with n less than k the answer being 1 and n equal to k the answer being 2. This is also linear time. Link to solution. answered 23 Feb '14, 16:41

I reached the answer by thinking of when will the array be good. The array is good only when 1s occur in groups of k. So this is the answer I got: summation i=0 to n/k C(n((k1)i),i). Calculating this is easy but it becomes a little difficult when you start crossing 10^9+7. Though this can also be done, for calculating a/b mod p, I used a(b)^1 mod p . As p is prime inverse of b will always exist. Offcourse you will need to preprocess factorial%p values.
link
This answer is marked "community wiki".
answered 23 Feb '14, 15:12
