NEWSCH - Editorial

anton_lunyov · October 15, 2012, 3:00pm

PROBLEM LINK:

Practice
Contest

Author: Vitalij Kozhukhivskij
Tester: Anton Lunyov
Editorialist: Anton Lunyov

DIFFICULTY:

SIMPLE

PREREQUISITES:

Simple Math, Repeated Squaring

PROBLEM:

How many sequences with elements in the set {0, 1, 2, 3} of length N are there such that any two consecutive elements are different as well as the first and the last elements are different?

QUICK EXPLANATION:

The answer is 3^N + 3 * (−1)^N. See EXPLANATION for proof. 3^N can be found by repeated squaring in O(log N) time.

Alternatively the problem can be solved using dynamic programming. See ALTERNATIVE SOLUTION 2 for details.

EXPLANATION:

Denote by F(N, X, Y) the number of sequences with elements in the set {0, 1, 2, 3} of length N such that its first element equals to X, its last element equals to Y and any two consecutive elements are different. Clearly, the answer for the problem will be the sum of F(N, X, Y) for all non-equal X and Y.

It is clear that

**F(1, X, Y) = 0**, for **X ≠ Y**, and **F(1, X, X) = 1**.

Basic combinatorial reasoning yields that F(N, X, Y) for N > 1 is the sum of F(N − 1, X, Z) for all Z ≠ Y.

The main observation that is needed to get the explicit formula is to notice that F(N, X, Y) = F(N, 0, 1) if X ≠ Y and F(N, X, X) = F(N, 0, 0). It follows from the fact that if (A[1], …, A[N]) is a sequence having different consecutive elements, that is, A[i] ≠ A[i − 1] for 1 < i ≤ N, and (p[0], p[1], p[2], p[3]) is an arbitrary permutation of the sequence (0, 1, 2, 3) then (p[A[1]], …, p[A[N]]) is also a sequence having different consecutive elements. Hence instead of considering 16 sequences F(N, X, Y) for X and Y in the set {0, 1, 2, 3}, we can consider only two of them. Denote them as A(N) = F(N, 0, 1) and B(N) = F(N, 0, 0). The answer will take the form 12 * A(N).

Now we can write for N > 1:

**A(N) = F(N, 0, 1) = F(N − 1, 0, 0) + F(N − 1, 0, 2) + F(N − 1, 0, 3) = B(N − 1) + A(N − 1) + A(N − 1)**, and **B(N) = F(N, 0, 0) = F(N − 1, 0, 1) + F(N − 1, 0, 2) + F(N − 1, 0, 3) = A(N − 1) + A(N − 1) + A(N − 1)**, or **A(N) = 2 * A(N − 1) + B(N − 1)**, **B(N) = 3 * A(N − 1)**.

Having these convenient formulas we can easily calculate answers for several small values of N. The result of such calculation provided in the table below

N	1	2	3	4	5	6
A(N)	0	1	2	7	20	61
B(N)	1	0	3	6	21	60
answer	0	12	24	84	240	732
3^N	3	9	27	81	243	729
answer − 3^N	−3	3	−3	3	−3	3

Even from this small table it is easy to see that the answer is 3^N + 3 * (−1)^N. So one can stop here believing that this is true for all N without proof and apply repeated squaring to solve the problem. See tester’s solutions as a reference.

Well, once this answer is found the proof can be easily made using induction. But let’s consider a way how to come to this answer without guessing. I suggest you to read this carefully since the next part contains some very important stuff that can help you to solve many other similar problems without guessing.

The first step is to obtain the recurrent formula that involves only A(N). For N > 2 we have B(N − 1) = 3 * A(N − 2). Substituting this into formula for A(N) we get

**A(N) = 2 * A(N − 1) + 3 * A(N − 2)**.

Now we apply the basic theory of linear homogeneous recurrence relations with constant coefficients. For this we write down the characteristic polynomial:

**p(t) = t² − 2 * t − 3**.

Its roots are r₁ = −1 and r₂ = 3. Hence the general solution for this recurrence is

**A(N) = C₁ * r₁^N + C₂ * r₂^N = C₁ * (−1)^N + C₂ * 3^N**.

Constants C₁ and C₂ can be found when we know A(1) and A(2). Clearly, A(1) = 0, B(1) = 1. This implies A(2) = 1 and B(2) = 0. Now substituting N = 1 and N = 2 to the general form of A(N) we get

−C₁ + 3 * C₂ = 0; C₁ + 9 * C₂ = 1. Solving this **2 × 2** system we get **C₁ = 1 / 4** and **C₂ = 1 / 12**. Hence **A(N) = (3^N + 3 * (−1)^N) / 12**. So the answer is **12 * A(N) = 3^N + 3 * (−1)^N** and we are done.

ALTERNATIVE SOLUTION 1:

We can stop on recurrent formulas for A(N) and B(N) and solve the problem using fast matrix exponentiation for some 2 × 2 matrix. Namely, let M equals to

⌈ 2 1 ⌉
⌊ 3 0 ⌋

Denote V(N) = [A(N) B(N)]. Then recurrent relations for A(N) and B(N) take the form V(N) = V(N − 1) * M. Here ***** denotes standard multiplication of matrices. Iterating this we obtain V(N) = V(1) * M^{N − 1}, where V(1) = [A(1) B(1)] = [0 1]. Again using repeated squaring but this time for 2 × 2 matrix M we can solve the problem efficiently.

ALTERNATIVE SOLUTION 2:

This time we stop even earlier at the main solution and consider F(N, X, Y) from another point of view. Let’s fix some K such that 1 ≤ K < N. Any sequence counted by F(N, X, Y) has the form

 X ... A   B ... Y
|-------| |-------|
    K        N-K

where A and B are some different digits in {0, 1, 2, 3}. It is clear from here that F(N, X, Y) is a sum of F(K, X, A) * F(N − K, B, Y) for all non-equal A and B. Now fast solution can be obtained in the following way. We will calculate F(N, X, Y) recursively. Namely, for each N our recursive routine will return values F(N, X, Y) for all X and Y. Now how it works. If N is odd we simply choose K = N − 1 and use usual recurrent formula for F(N, X, Y). We pass to the N − 1 in the recursion in this case. If N is even then we choose K = N / 2. So N − K is also equal to N / 2 and using just obtained formula for F(N, X, Y) we pass to N / 2 in the recursion. Terminating state of the recursion is N = 1 for which it is clear what should we return. And don’t forget to do all operations modulo 10⁹ + 7. See author’s solution as a reference.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.