Problem 42777. GJam March 2016 IOW: Polynesiaglot Small

Created by Richard Zapor in Community

This Challenge is derived from GJam March 2016 Annual I/O for Polynesiaglot. This is the first very small set.

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.

Input: [C V L] , C=1, V=1, 1<=L<=15

Output: [Q]

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

Contest Theory: The small case is a warm up of only a single vowel and consonant. For L<16 this can readily be solved by brute force generation of valid sequences followed by size of array. Subsequent challenges will be a subset of small-2 with eps(Q) <0.25 and then the unbounded size case of small-2/large. For the unbounded case a solution method uses Matlab java calls. Solution sizes are on the order of (C+V)^L with the large case C=50,V=50,L=500.

Solution Stats

82.35% Correct | 17.65% Incorrect
Last solution submitted on Dec 07, 2018