Project Euler/158

We consider strings of n <= 26 diff chars from the alphabet.

For every n, p(n) is the number of strings of length n for which exactly one character comes lexicographically AFTER its neighbour to the left.

What is the maximum value of p(n)?

Overview of approach

For a string of length n, we can compute p(n) using the number of positions in which we can substitute characters, which we denote C, for a given string of length n:

$ C_{n} = C_{n-1} + 2^{n-1} - 1 $

plus the base case,

$ C_{2} = 1 $

(This means that when we have a string of length 2, there is only 1 position in which the one character in question, that's lexicographically out of order, can possibly occupy.)

Now the number of choices for these letters depends on the length of the string via the binomial term $ \binom{26}{n} $:

$ P(n) = \binom{26}{n} C_{n} $

The recurrence for $ C_n $ suggests a recursive or dynamic approach might work.

Code

Code: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round5_150-160/158

$ cat Problem158.java
public class Problem158 {
	public static void main(String[] args) {
		System.out.println(solve());
	}

	public static int pow(int b, int p) {
		int result = b;
		for(int i=2; i<=p; i++) {
			result *= b;
		}
		return result;
	}

	public static String solve() {
		int m = 26;
		BinomialDP b = new BinomialDP(m);

		long p = 0;
		long priorconfigs = 1;
		for(int n=3; n<=26; n++) {

			long binom = (long)( b.binomial(26,n) );
			long configs = (long)(priorconfigs + (pow(2,n-1)-1));
			long pnew = binom*configs;

			//System.out.printf("%12d\t%12d\t%12d\t%12d\n",n,binom,configs,pnew);

			p = Math.max(p,pnew);
			priorconfigs = configs;
		}
		return Long.toString(p);
	}
}