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
-
What is the distance from point P(x,y) to the line Ax + By + C = 0?
365 Solvers
-
Find best placement for ordered dominoes (harder)
309 Solvers
-
Cody Computer Part 2 - Get the license number of Cody Computer
65 Solvers
-
Getting the absolute index from a matrix
243 Solvers
-
151 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!