CareerCup

Logic used is similar but put into a more compact recursive relation:

C(n) = C(n-1) + C(n-2) + F(n+2)

where F(n) is the nth term in the Fibonacci sequence.
C(n) has base cases C(1) = 3, C(2) = 7.

Reasoning:
-can append "c" to any n-1 length sequence to make an n length sequence.
-can append "b" to any n-1 length sequence that has no b in it already.
-can append "ca" to any n-2 length sequence
-can append "ba" to any n-2 length sequence that has no b in it already.

This "has no b in it already" is a sequence consisting of only "a" and "c" which is very easily found with relation f(n) = f(n-1) + f(n-2) which has an offset of 2 from the Fibonacci sequence.

This problem can be solved by recursive/DP with O(n) time and O(1) space.

My way of thinking is following. Given that we already know everything for length (n-1), to compute for length n string, we need to know: if n-th position is "A" (or "B" or "C"), what must be the previous position?

For this problem, we define 6 variables:

A0 = number of strings with (n-1)-th position is "A" and have zero "B" so far.
A1 = number of strings with (n-1)-th position is "A" and have 1 "B" so far.
B0 = number of strings with (n-1)-th position is "B" and have zero "B" so far. // always none! Ignore it!
B1 = number of strings with (n-1)-th position is "B" and have 1 "B" so far.
C0 = number of strings with (n-1)-th position is "C" and have zero "B" so far.
C1 = number of strings with (n-1)-th position is "C" and have 1 "B" so far.

According to the rules, the n-th position is constructed by following table:

--	"A"	"B"	"C"
A0	x	B1	C0
A1	x	x	C1
B1	A1	x	C1
C0	A0	B1	C0
C1	A1	x	C1

Thus, the values of these variables at n-th position is (read from the table):

Recursive formulas for next position:
A0 = C0;
A1 = B1 + C1;
B1 = A0 + C0;
C0 = A0 + C0;
C1 = A1 + B1 + C1;

Initial values at first position

n = 1:
A0 = 1; "A"
A1 = 0; (no such)
B1 = 1; "B"
C0 = 1; "C"
C1 = 0; (no such)

n = 2:
A0 = C0 = 1; // "CA"
A1 = B1 + C1 = 1; // "BA"

B1 = A0 + C0 = 2; // "AB" "CB"

C0 = A0 + C0 = 2; // "AC" "CC"
C1 = A1 + B1 + C1 = 1; // "BC"

The result will be

res = A0 + A1 + B1 + C0 + C1;

This formulation can be implemented in O(n) time and O(1) space.
(Note, the values increase exponentially)

As explained by Booley, it boils down to compute C(n) given by the recurrence

F(n) = F(n - 1) + F(n - 2);
C(n) = C(n - 1) + C(n - 2) + F(n).

with C(-1) = 0, C(0) = 1, F(-1) = 1, F(0) = 1. One can show by induction that

/          \   /         \^n /   \
| C(n)     |   | 1 1 1 0 |   | 1 |
| C(n - 1) | = | 1 0 0 0 |   | 0 |
| F(n + 1) |   | 0 0 1 1 |   | 2 |
| F(n)     |   | 0 0 1 0 |   | 1 |
\          /   \         /   \   /

Therefore, to get C(n), it suffices to compute the right hand side above and retrieve the first coordinate.

Notice that dimensions of matrices and vectors involved do not depend on n. Matrix exponentiation can be done in O(lg n), in time and space, through exponentiation by squaring. So the total complexity is O(lg n).

This method is good to get a single C(n). If one needs to compute C(n) for n = 1, ..., N, then the bottom up dynamic programming algorithm suggested by others would be preferable.

I believe that, similarly to F(N), an algorithm to get C(n) in O(1) is mathematically possible but it requires working with floating point numbers. This might introduce small rounding errors that can propagate and yield a wrong result.

Maybe this could be made shorter, but it seems straightforward. O(n).


$ ./ternary.py 1
3
$ ./ternary.py 2
7
$ ./ternary.py 3
15
$ ./ternary.py 4
30

#!/usr/bin/env python

import sys


def num_ternary(previous_letter, b_used, length):
    if length == 1:
        # can place either a, b, or c
        if previous_letter == 'a':
            return 1 if b_used else 2
        else:
            return 2 if b_used else 3
    if b_used:
        if previous_letter == 'a':
            # can only place 'c'
            return num_ternary('c', True, length - 1)
        else:
            # can place 'a' or 'c'
            return  num_ternary('a', True, length - 1) + num_ternary('c', True, length - 1)
    else:
        if previous_letter == 'a':
            # can place 'b' or 'c'
            return  num_ternary('b', True, length - 1) + num_ternary('c', False, length - 1)
        else:
            # 'a', 'b', or 'c'
            return  num_ternary('a', False, length - 1) + num_ternary('b', True, length - 1) + num_ternary('c', False, length - 1)


if __name__ == '__main__':
    # assume one interger arg, length N
    print num_ternary(None, False, int(sys.argv[1]))

def effecient_num_ternary(n):
    a = [[0, 0] for _ in xrange(n+1)]
    a[0][0] = 1
    a[0][1] = 1
    a[1][0] = 2
    a[1][1] = 3
    for i in xrange(2, n + 1):
        for k in xrange(2):
            a[i][k] = a[i-2][k] + a[i-1][k] + (a[i-2][k-1] + a[i-1][k-1] if k > 0 else 0)

    return a[n][1]

This obviously works in O(n) (where n is length of string). Thanks to Dan, one can check that it's correct.

Why it works: let's take any valid string of length n and see what it's made of:
- If the last symbol is b, then previous (n-1) symbols are any valid combinations of a's and c's
- If the last symbol is c, then previous (n-1) symbols are any valid combinations of a's and b
- If the last symbol is a, then (n-1)th symbol is either c or b (if we can put any) and the previous (n-2) symbols are any valid string

This gives us formula for string of length n containing k b's (may work wrong with b != {0,1})

l(n, k) = l(n-1, k) // if it was c
      + (k > 0 ? l(n-1, k-1) : 0) // if it was b
      + l(n-2, k) // if it was ac
      + (k > 0 ? l(n-2, k-1) : 0) // if it was ab

Algo Steps:

1) Calculate the number of possible entries of length (N-1) with 'a' and 'c' given the constraint.Here, we are reserving 1 slot for 'b', which is being allowed only once.Let the total number of entries be p.

2) For each of the p entries calculated in Step 1, we have effectively N slots in each entry where
we can place 'b'.

3) Hence, the solution turns out to be (p*N).

n=int(raw_input())
f=[2,3]
c=[3,7]
for i in range(2,n):
	f.append(f[i-1]+f[i-2])
	c.append(c[i-1]+c[i-2]+f[i])
print c[n-1]

A0 = 1; 
A1 = 0; 
B1 = 1; 
C0 = 1;
C1 = 0; 

n=int(raw_input())
for i in range(1,n):
	(A0,A1,B1,C0,C1) = (C0,B1+C1,A0+C0,A0+C0,A1+B1+C1);
res = A0 + A1 + B1 + C0 + C1;
print res