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
-
5911 Solvers
-
1365 Solvers
-
167 Solvers
-
Project Euler: Problem 2, Sum of even Fibonacci
2310 Solvers
-
184 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!