ACM/ICPC CS UI

The problem wants you to determine the number of n-bit sequences which contain no adjacent ones. For example, the sequence 10100 doesn’t contain any adjacent ones, but the sequence 101101110 does.

EDT: Solution

When n = 0, there is one possibility: the empty sequence.

When n = 1, there are two possibilities: 0, 1.

When n = 2, there are three possibilities: 00, 01, 10. 11 contains adjacent ones, so it is excluded from the set. This can be verified by hand.

When n = 3, there are five possibilities: 000, 001, 010, 100, 101.

When n = 4, there are eight possibilities: 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010.

When n = 5, there are thirteen possibilities: 00000, 00001, 00010, 00100, 00101, 01000, 01001, 01010, 10000, 10001, 10010, 10100, 10101.

1, 2, 3, 5, 8, 13, and so on; doesn’t this seem familiar? It happens to be some sort of Fibonacci sequence, but how?

How do we form a sequence of length n+1 from shorter sequences so that all sequences do not have any adjacent ones?

We can append 0 to any sequence which ends with 0, or append 1 to a sequence which ends with 0, or append 0 to a sequence which ends with 1. All sequences do not have adjacent ones.

Let x n be the number of n-bit sequences which do not contain adjacent ones.

How many n-bit sequences end with 0 and do not have adjacent ones?

e(n,0) = x(n-1)

How many n-bit sequences end with 1 and do not have adjacent ones?

e(n,1) = x(n) - e(n,0)

e(n,0) + e(n,1) = x(n)
x(n+1) = e(n,0) + e(n,0) + e(n,1)
x(n+1) = e(n,0) + x(n)
x(n+1) = x(n-1) + x(n)
x(n) = x(n-1) + x(n-2)
x(0) := 1
x(1) := 2
x(n) = 1,2,3,5,8,13,21,34,55,89 ... (n from 0)

Indeed it is a sequence which has the same relation as the Fibonacci sequence, but different initial conditions.

Since the input space is small (input is limited so that it is always less than 45), we can precompute the answers first to generate a table of answers.

Angloid.

L = array 1 2
for i from 2 to 45 exclusive
   L[i] := L[i-1] + L[i-2]
read integer n
for i from 1 to n
   write-line 'Scenario #' i ':'
   write-line L[i]
   write-line

C.

#include <stdio.h>
#define N 45
int main () {
     int i;
     int n;
     int j;
     int L[N];
     L[0] = 1;
     L[1] = 2;
     for (i = 2; i < N; ++i) {
          L[i] = L[i-1] + L[i-2];
     }
     scanf ("%d", &n);
     for (i=1; i <= n; ++i) {
          scanf ("%d", &j);
          printf ("Scenario #%d:\n%d\n\n", i, L[j]);
     }
     return 0;
}

FD: Solution

Find the recurrence relation which describes the number of the two or more consecutive ones in n-bits. Since 0 and 1-bit can’t have two or more consecutive ones, we set array[0] and array[1] to 0.
The recurrence relation is:

f(n) = f(n-1) + f(n-2) + pow(2,n-2)

The number of n-bit sequences which contain no adjacent ones is pow(2,n) - f(n).

This problem isn’t solveable with recursion; you’ll get TLE (Time Limit Exceeded). So, we use Dynamic programming here to save the value we have counted before.

This is the solution with Java.

import java.util.*;

class Main{
	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int i=1;
		long rek[] = new long[46];
		rek[0] = rek[1] = 0;
		int batas = 2;
		while(n-->0){
			int m = in.nextInt();
			for(int ii=batas ; ii<=m ; ii++){
				rek[ii] = rek[ii-2]+rek[ii-1]+(long)Math.pow(2,ii-2);	
			}
			System.out.println("Scenario #"+i+":");
			System.out.println((long)Math.pow(2,m)-rek[m]);
			i++;
			batas = m+1;
		}
	}
}