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 Solvers7
Suggested Problems
-
Project Euler: Problem 9, Pythagorean numbers
1130 Solvers
-
115 Solvers
-
Generate a string like abbcccddddeeeee
259 Solvers
-
Square Digits Number Chain Terminal Value (Inspired by Project Euler Problem 92)
216 Solvers
-
Possible Outcomes of American Roulette
118 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!