Three ones (Editorial)

Let $f(n)$ denote the number of valid sequences of length $n$. consisting of $0$s and $1$s. Consider constructing such a sequence based on its first element.

If the first element is $0$, then the remaining part of the sequence can be any valid sequence of length n - 1. Therefore, there are f(n - 1) such sequences.

If the first element is $1$, consider the possible continuations:

• If the second element is $0$, then the remaining n - 2 positions can form any valid sequence of length n - 2, giving f(n - 2) possibilities;

• If the second element is $1$, then to avoid having three consecutive $1$s, the third element must be $0$. The remaining n - 3 positions can then form any valid sequence of length n - 3, giving f(n - 3) possibilities.

Thus, we obtain the following recurrence relation:

It remains to determine the base cases:

• f(1) = 2, since there are two sequences of length $1$: $0$ and $1$.

• f(2) = 4, since there are four sequences of length $2$: $00,01,10$ and $11$.

• f(3) = 7, since there are seven sequences of length $3$: 000, 001, 010, 011, 100, 101 and $110$.

Example

Algorithm implementation

Declare an array $f$ to store the values f(1), f(2), ..., f(n).

int f[100010];

Read the input value $n$.

scanf("%d",&n);

Initialize the base values of the array.

f[1] = 2; f[2] = 4; f[3] = 7;

Compute the values $f(i)$ using the recurrence relation. Perform all calculations modulo $12345$.

for(i = 4; i <= n; i++)
  f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;

Print the answer.

printf("%d\n",f[n]);

Algorithm implementation – recursion + memorization

Declare an array $dp$ to store intermediate results:

• $dp[i]$ will store the value $f(i)$

int dp[100001];

Implement the function $f(n)$, which returns the number of valid sequences of $0$s and $1$s of length $n$. Use memoization.

int f(int n)
{
  if (n == 1) return 2;
  if (n == 2) return 4;
  if (n == 3) return 7;
  if (dp[n] != -1) return dp[n];
  return dp[n] = (f(n-1) + f(n-2) + f(n-3)) % 12345;
}

The main part of the program. Read the input value $n$.

scanf("%d",&n);

Initialize the $dp$ array.

memset(dp,-1,sizeof(dp));

Compute and print the value $f(n)$.

printf("%d\n",f(n));

Java implementation

import java.util.*;

public class Main
{
  public static int MAX = 100010;
  static int f[] = new int[MAX];

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    f[1] = 2; f[2] = 4; f[3] = 7;
    for(int i = 4; i <= n; i++)
      f[i] = (f[i-1] + f[i-2] + f[i-3]) % 12345;
    System.out.println(f[n]);
    con.close();
  }
}

Python implementation

Read the input value $n$.

n = int(input())

Initialize the $dp$ array. Store the values f(1), f(2) and $f(3)$ in the corresponding entries.

dp = [0] * (n + 4)
dp[1], dp[2], dp[3] = 2, 4, 7

Compute the values $f(i)$ using the recurrence relation. Perform all calculations modulo $12345$.

for i in range(4, n + 1):
  dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % 12345;

Print the answer.

print(dp[n])

Python implementation – recursion with memoization

Increase the recursion stack size.

import sys
sys.setrecursionlimit(10000)

Implement the function $f(n)$, which returns the number of valid sequences of $0$s and $1$s of length $n$. Use memoization.

def f(n):
  if n == 1: return 2
  if n == 2: return 4
  if n == 3: return 7
  if dp[n] != -1: return dp[n]

  dp[n] = (f(n - 1) + f(n - 2) + f(n - 3)) % 12345
  return dp[n]

The main part of the program. Read the input value $n$.

n = int(input())

Initialize the $dp$ list.

dp = [-1] * 100001

Compute and print the value $f(n)$.

print(f(n))