Problem 42778. GJam March 2016 IOW: Polynesiaglot Medium

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is derived from</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://code.google.com/codejam/contest/8274486/dashboard#s=p2\"><w:r><w:t>GJam March 2016 Annual I/O for Polynesiaglot</w:t></w:r></w:hyperlink><w:r><w:t>. This is a subset of small set 2. The max Qraw is 2^50 (&lt;1.1259e15) for C[1,50], V[1,50], L[1,15].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> [C V L] , C[1,50], V[1,50], 1&lt;=L&lt;=15</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> [Q] max Qraw is 2^50 (&lt;1.1259e15); Q=mod(Qraw,1E9+7)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Examples:</w:t></w:r><w:r><w:t> [C V L] [Q]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[[1 1 4] [5] {aaaa,aaba,abaa,baaa,baba} invalid are {bbaa, aaab} \n[1 2 2] [6] {aa,ae,ba,be,ee,ea} invalid are {ab,eb,bb}]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t></w:t></w:r><w:hyperlink w:docLocation=\"http://code.google.com/codejam\"><w:r><w:rPr><w:b/></w:rPr><w:t>Google Code Jam 2016 Open Qualifier: April 8, 2016</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Theory:</w:t></w:r><w:r><w:t> 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)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[Q3 V C\nQ2 V C V\nQ1 V V V\n\n 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.]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This Challenge is derived from <a href = "http://code.google.com/codejam/contest/8274486/dashboard#s=p2">GJam March 2016 Annual I/O for Polynesiaglot</a>. This is a subset of small set 2. The max Qraw is 2^50 (&lt;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&lt;=L&lt;=15Output: [Q] max Qraw is 2^50 (&lt;1.1259e15); Q=mod(Qraw,1E9+7)Examples: [C V L] [Q]<pre class="language-matlab">[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}
</pre><a href = "http://code.google.com/codejam">Google Code Jam 2016 Open Qualifier: April 8, 2016</a>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)<pre class="language-matlab">Q3 V C
Q2 V C V
Q1 V V V
</pre><pre> This medium challenge has eps(Qraw) &lt;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.</pre>

Solve

Solution Stats

15 Solutions
6 Solvers

Last Solution submitted on Dec 11, 2018

Last 200 Solutions

Problem Recent Solvers6

Problem Tags

contest gjam probability tree

Problem 42778. GJam March 2016 IOW: Polynesiaglot Medium

Solution Stats

Last 200 Solutions

Problem Recent Solvers6

Suggested Problems

More from this Author236

Problem Tags

Problem 42778. GJam March 2016 IOW: Polynesiaglot Medium

Solution Stats

Last 200 Solutions

Problem Recent Solvers6

Suggested Problems

More from this Author236

Problem Tags

Players