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.
the fly, the train, the second train, and their Zeno's paradox
55 Solvers
Back to basics 13 - Input variables
203 Solvers
Getting the indices from a matrice
265 Solvers
357 Solvers
94 Solvers
Problem Tags