Problem 42778. GJam March 2016 IOW: Polynesiaglot Medium
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}
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.
Solution Stats
Problem Comments
-
1 Comment
Shikhar
on 18 Jul 2023
Very interesting
Solution Comments
Show commentsProblem Recent Solvers8
Suggested Problems
-
Replace NaNs with the number that appears to its left in the row.
2969 Solvers
-
52 Solvers
-
Back to basics 22 - Rotate a matrix
898 Solvers
-
66 Solvers
-
Test if two numbers have the same digits
241 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!