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

×

CROWD - Editorial

12
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Simple Math, Repeated Squaring

PROBLEM

How many sequences of 0s and 1s of length N are there such that there are at least 3 consecutive 1s.

QUICK EXPLANATION

You can see that the original problem statement is equivalent to the the above by saying that among N houses, you invite only those houses for which you put a 1 in the sequence.

Now, the number of ways you can make a sequence of 0s and 1s of length N, such that there are no more than two consecutive 1s is
f(N) = f(N-1) + f(N-2) + f(N-3)

This is known as the Tribonacci Numbers.

The answer to the problem statement would then be 2N - f(N).

Since N can be very large, 2N can be calculated by repeated squaring and f(N) can be calculated by matrix exponentiation.

EXPLANATION

First, let us see what insights are used to derive the formula.

The number of sequences of N digits where each digit is either 0 or 1 is 2N.

We wish to find the number of sequences such that there are no more than 2 consecutive 1s.

Lemma:

The entire world of such sequences can be constructed by concatenating strings taken from the following prefix-free set
S = { 0, 10, 110 }

Proof:

Let us call a sequence that contains no more than two consecutive 1s as a valid string.

(1) ... All strings with less than or equal to 2 letters are valid.
(2) ... Any substring of a valid string is also a valid string.
(3) ... From (2), any suffix of a valid string is also a valid string.
(4) ... For a string T, constructed by taking strings from S, T should also partition into S.
(5) ... If T cannot partition into S, it cannot be constructed by taking strings from S.
(6) ... Since S is prefix-free, every string has a unique partitioning into S, or none at all.

For example,
0101100100010110 can be partitioned into S as
0 10 110 0 10 0 0 10 110
And this is the only valid partitioning into S.

(7) ... For a valid string A, A always has a prefix that matches a string in S.

Let us consider all possible 3 letter prefixes of a string

000x.. matches 0 from S (remaining string 00x..)
001x.. matches 0 from S (remaining string 01x..)
010x.. matches 0 from S (remaining string 10x..)
011x.. matches 0 from S (remaining string 11x..)
100x.. matches 10 from S (remaining string 0x..)
101x.. matches 10 from S (remaining string 1x..)
110x.. matches 110 from S (remaining string x..)
111x.. Does not match any string in S

But, if A contains the prefix 111 then A is not a valid string.

Hence, for any valid string A, some prefix of A will always be one of the strings in S.

(8) ... From (3) and (7), a valid string A will always have a partitioning into S.
(9) ... We can see that concatenating strings from S will always generate a valid string.

From (8) and (9) we can say that taking strings from S will generate all possible valid strings.

Now, the number of valid strings of length N will be f(N), which is equal to

  • f(N-1), after choosing "0" from S as prefix, all possible valid strings of length N-1 can be used
  • f(N-2), after choosing "10" from S as prefix, all possible valid strings of length N-2 can be used
  • f(N-3), after choosing "110" from S as prefix, all possible valid strings of length N-3 can be used

Thus,
f(N) = f(N-1) + f(N-2) + f(N-3)

We have to find the result modulo 1000000007.

Now, since N can be quite large, we cannot even iterate for O(N) complexity and find the result. We can build the following matrix representation from the above formula

                                              |1 1 0|
[f(N+1) f(N) f(N-1)] = [f(N) f(N-1) f(N-2)] * |1 0 1|
                                              |1 0 0|

Now we see that multiplying the 3x3 matrix above (let us call it M) k times will give us f(N+k).

We can consider the base case [f(2) f(1) f(0)] = [4, 2, 1] and find MN-2. Once we have MN-2, we can find the answer by multiplying MN-2 to [4, 2, 1], and taking the first value.

You can find MN-2 by repeated squaring on the matrix. Repeated Squaring (and similarly Matrix Exponentiation) is a very useful technique that you should add to your problem solving arsenal.

RELATED PROBLEMS

CSUMD
Go through the Related Problems section of the above as well for more problems :-)

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here

This question is marked "community wiki".

asked 11 Sep '12, 15:15

gamabunta's gravatar image

1★gamabunta
2.4k128183169
accept rate: 14%

edited 25 Dec '12, 14:55

admin's gravatar image

0★admin ♦♦
19.8k350498541

1

I was a bit focused on deriving some recursive relationship involving only 2 terms for most of the time... After a while, I realized that maybe 3 terms should try to be used instead but couldn't do anything about it... This editorial just makes everything very clear and it is, as usual, very well written :D

Great work, Bruno

(11 Sep '12, 15:41) kuruma3★

can anybody explain how to find the matrix ? like i want to find the matrix for f(n)=f(n-1)+f(n-2)+2*f(n-3)-c, where c is a constant. is there a method to find it or just hit and trial?

(11 Sep '12, 17:24) never_stop2★

I figured out that it was the Tribonacci Numbers (I didn't know that's what they were called at the time), but couldn't figure out a formula to find f(N) without actually solving for F(N-1), F(N-2), and F(N-3). I see now that I needed Matrix Exponentiation to find the formula. Unfortunately, I still don't quite understand it, but hopefully with some reading and practice it will make sense.

(11 Sep '12, 18:12) dreamlane3★
1

Dealing with such a constant is a bit of an extension, but the basic strategy is: suppose we have f(n-1), f(n-2), and f(n-3), then our matrix should give us the same but with n+1 [so f(n), f(n-1) and f(n-2)]. The equations for f(n-1) and f(n-2) are trivial, but to handle adding the constant for f(n) we add another row to our matrix (and another element 1 to our column vector). So the matrix for this example would be A = [1 1 2 -c; 1 0 0 0; 0 1 0 0; 0 0 0 1] -- if we take A*[f(n-1); f(n-2); f(n-3); 1] we get [f(n); f(n-1); f(n-2); 1]

(11 Sep '12, 18:16) Sumudu5★

@dreamlane Finding the matrix for exponentiation is usually not hit and trial. All recursions can be converted to matrices with sufficiently large dimensions. For this problem, 3x3 is enough.

(11 Sep '12, 19:19) gamabunta1★

So what does one need to study to derive these kind of formulas? Combinatorics maybe and linear algebra? Any suggestions are very welcome :)

(11 Sep '12, 20:57) deathrash6672★

Although i have solved this problem,but thanks for such a beautiful proof :)

(12 Sep '12, 01:08) solve2★
2

@deathrash667 : I think a lil bit of Automata is required here.

(12 Sep '12, 01:10) solve2★
1

Not necessarily all recurrences, definitely linear ones, and also ones like never_stop mentioned which I suppose could be called "affine". For matrix powers, we are formally using linear algebra but not really any deep results (essentially the def'n of matrix multiplication, and its associativity). Finding the matrix is just mechanical with the recurrence equation. As for going from a recurrence to a formula, I found knowing differential equation techniques helpful. You may also want to look at "generating functions" as they can make manipulating recurrences much easier.

(12 Sep '12, 01:15) Sumudu5★

I didn't understand why [f(2), f(1), f(0)] should be [4,2,1] No of valid strings of length 0 should be 0 right ?

(17 Sep '12, 23:40) sudarshans2★

@sudarshans the empty string is a valid string of length 0

(29 Sep '12, 19:32) abhi922★
showing 5 of 11 show all

Maybe while explaining you forgot what the actual question asked was! The answer would instead be ( 2n - f(n) ) % (109+7) which is equal to the number of ways in which Chef can go wrong.

link

answered 12 Sep '12, 10:54

rushilpaul's gravatar image

4★rushilpaul
3501612
accept rate: 6%

edited 12 Sep '12, 10:59

the recurrence i used was f(n)=3f(n-1)-f(n-2)-f(n-3)-2f(n-4)

link

answered 11 Sep '12, 21:02

jonvonneumann's gravatar image

3★jonvonneumann
46115
accept rate: 0%

10101 is a valid string but how can it be partitioned into S?

link

answered 29 Sep '12, 19:30

abhi92's gravatar image

2★abhi92
162
accept rate: 0%

1

@abhi92 Good catch :-)

The partition into S only gives strings that have a 0 at the end.

Using arguments from the editorial one would be led to believe f(1) = 1.

But by setting f(1) = 2. We are ensuring that we calculate all the valid strings that end in 1.

(30 Sep '12, 01:25) gamabunta1★

I used the same recursion and same Matrix exponentiation technique but still now use... :( Used to get TLE. :O

link

answered 11 Sep '12, 21:39

codersrikant's gravatar image

2★codersrikant
41124
accept rate: 0%

Can someone suggest me why my code gives TLE while the problem setters code doesnt ?

link

answered 11 Sep '12, 21:47

codersrikant's gravatar image

2★codersrikant
41124
accept rate: 0%

Can you give a link to your submission?

(12 Sep '12, 10:10) rushilpaul4★

Very powerful tutorial! Big ups to Vamsi. The tutorial was well laid out. Thanks.

link

answered 13 Sep '12, 07:02

bodmas's gravatar image

5★bodmas
16127
accept rate: 0%

Hi ,

I think the problem like this out of N numbers you have to select 0 or 1 or 2 consecutive one 0 consecutive one 1 ways 1 consecutive one N ways 2 consecutive one N-1 ways

than answer is 2^N - 2N but i got wrong answer. Also i am not getting

Now, the number of ways you can make a sequence of 0s and 1s of length N, such that there are no more than two consecutive 1s is f(N) = f(N-1) + f(N-2) + f(N-3) and what is f(N) here

link

answered 14 Sep '12, 12:42

arvindpurohit's gravatar image

3★arvindpurohit
11
accept rate: 0%

@admin..my code is still giving TLE http://www.codechef.com/viewsolution/1371826 can anybody plzz help??

link
This answer is marked "community wiki".

answered 24 Sep '12, 16:18

nikhil123's gravatar image

3★nikhil123
35338
accept rate: 0%

edited 25 Sep '12, 21:12

anton_lunyov's gravatar image

6★anton_lunyov ♦
6.7k62119138

@author : how can you say f[n] = f[n-1]+f[n-2]+f[n-3] there f[0] = 0 f[1] = 0 f[2] = 0 f[3] = 1 then for n = 4 2^4 is 16 and f[4] = 1 then ans is ans = 2^4-1 ans = 15 am i right or not

link

answered 01 Jun '13, 18:23

raj_meena885's gravatar image

3★raj_meena885
1
accept rate: 0%

can anyone explain the solution for test cases 5,6,7,8,9,10....i m not getting the logic behind it... it seems that this can be solved via normal mathematics but maybe i m getting it wrong.. Thanks in advance....(y)

link

answered 29 Sep '14, 22:36

ayush22227's gravatar image

4★ayush22227
1
accept rate: 0%

link

answered 31 Jan '16, 23:45

hant6's gravatar image

2★hant6
1
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,852
×1,220
×303
×18

question asked: 11 Sep '12, 15:15

question was seen: 7,407 times

last updated: 31 Jan '16, 23:45