You are not logged in. Please login at www.codechef.com to post your questions!

×

SEARRAYS - Editorial

6
2

Problem Link: contest, practice

Difficulty: Easy

Pre-requisites: DP, Implementation

Problem:

We need to count the number of 01-strings 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 01-strings 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 non-negative, 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:

F[0] = 1
for i from 1 to N do 
begin
    F[i] = 0
    if ( i is a multiple of K )
    begin
        F[i] = 1
    end
    loop_pointer = i - 1
    while ( loop_pointer is non-negative ) do
    begin
        F[i] = ( F[i] + F[ loop_pointer ] ) modulo 1000000007
        loop_pointer = loop_pointer - K
    end
end

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 linear-time algorithm:

F[0] = 1
G[0] = 1
for i from 1 to N do 
begin
    F[i] = 0
    if ( i is a multiple of K )
    begin
        F[i] = 1
    end
    F[i] = ( F[i] + G[(i - 1) modulo K] ) modulo 1000000007
    G[i modulo K] = ( G[i modulo K] + F[i] ) modulo 1000000007
end

Setter's Solution: link

Tester's Solution: link

This question is marked "community wiki".

asked 23 Feb '14, 15:05

kostya_by's gravatar image

6★kostya_by ♦♦
166143235
accept rate: 0%

edited 23 Feb '14, 15:50

bugkiller's gravatar image

3★bugkiller
8.7k194898


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 n-1'th position.

Hence ans[n]=ans[n-k]+ans[n-1]

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.

link

answered 23 Feb '14, 16:41

epsilon_0's gravatar image

4★epsilon_0
4527
accept rate: 0%

It would be a great help if u explain a bit more....

(19 May '16, 21:02) pallesai4★

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-((k-1)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 pre-process factorial%p values.

link
This answer is marked "community wiki".

answered 23 Feb '14, 15:12

deepsaggas's gravatar image

4★deepsaggas
50661118
accept rate: 10%

wikified 23 Feb '14, 20:44

Can someone explain the problem bit more ?

link

answered 26 Feb '14, 23:45

pardeep_gill's gravatar image

2★pardeep_gill
615
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,659
×3,754
×2,168
×829
×8

question asked: 23 Feb '14, 15:05

question was seen: 3,346 times

last updated: 19 May '16, 21:02