This Challenge is derived from GJam March 2016 Annual I/O for Polynesiaglot. This is a subset of small set 2. The max Qraw is 2^50 (<1.1259e15) for C[1,50], V[1,50], L[1,15].
The GJam story goes that words are such that consonants are always followed by a vowel. Determine the number of possible words of length L using C consonants and V vowels. The final Q is to be modulo of the prime 1E9+7.
Input: [C V L] , C[1,50], V[1,50], 1<=L<=15
Output: [Q] max Qraw is 2^50 (<1.1259e15); Q=mod(Qraw,1E9+7)
Examples: [C V L] [Q]
[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba} invalid are {bbaa, aaab} [1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}
Google Code Jam 2016 Open Qualifier: April 8, 2016
Theory: This is a large value problem, on the order of (C+V)^L, thus brute force will not work. This is also a probability tree type problem. Tree calculations can be reduced to a linear in L evaluation. Inspection shows Q(1)=V, Q(2)=V^2, L=3 Q(3)=V^3+V*C*V+C*V^2 = V*Q(L-1)+V*C*Q(L-2)+C*Q(L-1). There are no Cs at the Q1 level since can not end in a C. Qnext=f(Q(-1),Q(-2)). Qfinal=Q+C*Q(-1)
Q3 V C Q2 V C V Q1 V V V
This medium challenge has eps(Qraw) <0.25 so normal matlab doubles work. For the unbounded case a solution method is to convert this Challenge algorithm to Matlab BigInteger java calls. Solution sizes are on the order of (C+V)^L with the large case being C=50,V=50,L=500.
It dseon't mettar waht oedrr the lrettes in a wrod are.
494 Solvers
Make an N-dimensional Multiplication Table
106 Solvers
121 Solvers
Calculate the area of a triangle between three points
281 Solvers
329 Solvers
Problem Tags