This Challenge is derived from GJam March 2016 Annual I/O for Polynesiaglot. This is the Large input set. The max Qraw is 100^500, (V+C)^L.
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<=500
Output: [Q] max Qraw is 100^500; 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 huge 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(L-1)
Q3 V C Q2 V C V Q1 V V V
One method to succeed in this problem is to use the java capability of Matlab. Cody Java Challenge. The primary reference sites are Java Math, Java BigDecimal, and Java BigInteger. The Java solution by the winner Stacy is included at the bottom of the test suite.
329 Solvers
238 Solvers
Multiples of a Number in a Given Range
151 Solvers
Sum the elements in either diagonal of a square matrix
145 Solvers
179 Solvers
Problem Tags