Problem 42779. GJam March 2016 IOW: Polynesiaglot Large
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.
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers7
Suggested Problems
-
359 Solvers
-
Return elements unique to either input
767 Solvers
-
Check if number exists in vector
11645 Solvers
-
474 Solvers
-
98 Solvers
More from this Author308
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!