Solving Linear Recurrence for Programming Contest – Examples

After grasping the basic method of solving linear recurrence, let’s apply it in real problems.

SPOJ Recursive Sequence

This is a classical problem that is directly solvable using the basic method I explained in the previous post. It is expected that you solve this problem and master the basic method before solving the next problems.

SPOJ Recursive Sequence (Version II)

A slightly harder version of the previous problem. This time, instead of determining a_{n}, we have to determine a_{m} + a_{m+1} + \cdots + a_{n}.

Let’s simplify the problem first, using a well-known technique called partial sum. Define a series S, where S_{i} = a_{1} + a_{2} + \cdots + a_{i}, with S_{0} = 0. Then, the result we are looking for is exactly S_{n} - S_{m-1} (prove that). So, instead of determining (n – m + 1) terms of sequence a, it is sufficient to determine only two terms of series S.

How to compute S? The crucial observation is that S_{i} = S_{i-1} + a_{i}, i.e., S itself is a linear recurrence! So, we can adopt the matrix equation of a to incorporate S. The final matrix equation of would look like this:

\begin{bmatrix}1&1&0&0&\cdots&0\\0&0&1&0&\cdots&0\\0&0&0&1&\cdots&0\\0&0&0&0&\cdots&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&c_{k}&c_{k-1}&c_{k-2}&\cdots&c_{1}\end{bmatrix} \begin{bmatrix}S_{i-1}\\a_{i}\\a_{i+1}\\a_{i+2}\\\vdots\\a_{i+k-1}\end{bmatrix} = \begin{bmatrix}S_{i}\\a_{i+1}\\a_{i+2}\\a_{i+3}\\\vdots\\a_{i+k}\end{bmatrix},

with initial values:

\begin{bmatrix}S_{0} = 0\\b_{1}\\b_{2}\\b_{3}\\\vdots\\b_{k}\end{bmatrix}.

After finding the matrix equation, S_{n} and S_{m-1} can be computed easily: S_{n} is the first row of T^{n}F_{1}, and S_{m-1} is the first row of T^{m-1}F_{1}.

You may also want to solve SPOJ Fibonacci Sum. It uses exactly the same idea. [Read more…]


Solving Linear Recurrence for Programming Contest

One of the topics that often arises in programming contests nowadays is about solving linear recurrence. It may come as a classic “find the n-th term of Fibonacci sequence” to more complex and creative forms of problems. Usually, after being simplified, the problem is merely asking you the n-th term of a linear recurrence. It should be able to solve with dynamic programming, however, the problem is that usually n can very large.

Because this topic starts to emerge in contests, I would like to share how I usually solve problems of this topic.


First, let’s start with a definition. A linear recurrence relation is a function or a sequence such that each term is a linear combination of previous terms. Each term can be described as a function of the previous terms. A famous example is the Fibonacci sequence: f(i) = f(i-1) + f(i-2). Linear means that the previous terms in the definition are only multiplied by a constant (possibly zero) and nothing else. So, this sequence: f(i) = f(i-1) * f(i-2) is not a linear recurrence.


Now, let’s state the problem formally.

Given f, a function defined as a linear recurrence relation. Compute f(N). N may be very large.

How to Solve

Here is the method I usually use in programming contests. I break down the method into four steps. Fibonacci sequence will be used as an example. [Read more…]