Project Euler/158 - Revision history

Admin: /* Overview of approach */

2019-03-24T06:04:30Z

Overview of approach

← Older revision		Revision as of 06:04, 24 March 2019
Line 7:		Line 7:
	==Overview of approach==		==Overview of approach==

	For a string of length n, we can compute p(n) ~~via~~		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:

	<math>		<math>
	C_{n} = C_{n-1} + 2^{n-1} - 1		C_{n} = C_{n-1} + 2^{n-1} - 1
	</math>		</math>

			plus the base case,

			<math>
			C_{2} = 1
			</math>

			(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 <math>\binom{26}{n}</math>:

	<math>		<math>
Line 17:		Line 27:
	</math>		</math>

	The recurrence suggests a recursive or dynamic approach might work.		The recurrence for <math>C_n</math> suggests a recursive or dynamic approach might work.

			==Code==

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

Admin: /* Overview of approach */

2019-03-24T05:56:53Z

Overview of approach

← Older revision		Revision as of 05:56, 24 March 2019
Line 11:		Line 11:
	<math>		<math>
	C_{n} = C_{n-1} + 2^{n-1} - 1		C_{n} = C_{n-1} + 2^{n-1} - 1
			</math>

			<math>
	P(n) = \binom{26}{n} C_{n}		P(n) = \binom{26}{n} C_{n}
	</math>		</math>
Line 54:		Line 57:
	}		}
	</pre>		</pre>


	=Flags=		=Flags=

Admin at 05:56, 24 March 2019

2019-03-24T05:56:39Z

← Older revision		Revision as of 05:56, 24 March 2019
Line 1:		Line 1:
			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) via

			<math>
			C_{n} = C_{n-1} + 2^{n-1} - 1
			P(n) = \binom{26}{n} C_{n}
			</math>

			The recurrence suggests a recursive or dynamic approach might work.

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

Line 42:		Line 59:

	{{ProjectEulerFlag}}		{{ProjectEulerFlag}}

			{{CombinatoricsFlag}}

			[[Category:Combinatorics]]
			[[Category:Permutations]]

Admin at 05:49, 24 March 2019

2019-03-24T05:49:20Z

← Older revision		Revision as of 05:49, 24 March 2019
Line 1:		Line 1:
	Code: https://charlesreid1.com~~:3000~~/cs/euler/src/master/scratch/Round5_150-160/158		Code: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round5_150-160/158

	<pre>		<pre>

Admin at 09:46, 5 January 2018

2018-01-05T09:46:52Z

← Older revision		Revision as of 09:46, 5 January 2018
Line 1:		Line 1:
			Code: https://charlesreid1.com:3000/cs/euler/src/master/scratch/Round5_150-160/158

	<pre>		<pre>
	$ cat Problem158.java		$ cat Problem158.java

Admin at 09:44, 5 January 2018

2018-01-05T09:44:02Z

← Older revision		Revision as of 09:44, 5 January 2018
Line 35:		Line 35:
	}		}
	</pre>		</pre>


			=Flags=

			{{ProjectEulerFlag}}

Admin: Created page with "

 $ 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..."

2018-01-05T09:41:29Z

Created page with "<pre> $ 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..."

New page

<pre>
$ 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);
}
}
</pre>