Problem 42779. GJam March 2016 IOW: Polynesiaglot Large

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 the Large input set. The max Qraw is 100^500, (V+C)^L.</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;=500</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 100^500; 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 huge 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(L-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]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>One method to succeed in this problem is to use the java capability of Matlab.</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow\"><w:r><w:t>Cody Java Challenge</w:t></w:r></w:hyperlink><w:r><w:t>. The primary reference sites are</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html\"><w:r><w:t>Java Math</w:t></w:r></w:hyperlink><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html\"><w:r><w:t>Java BigDecimal</w:t></w:r></w:hyperlink><w:r><w:t>, and</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html\"><w:r><w:t>Java BigInteger</w:t></w:r></w:hyperlink><w:r><w:t>. The Java solution by the winner Stacy is included at the bottom of the test suite.</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 the Large input set. The max Qraw is 100^500, (V+C)^L.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;=500Output: [Q] max Qraw is 100^500; 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 huge 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(L-1)<pre class="language-matlab">Q3 V C
Q2 V C V
Q1 V V V
</pre>One method to succeed in this problem is to use the java capability of Matlab. <a href = "http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow">Cody Java Challenge</a>. The primary reference sites are <a href = "http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Number.html">Java Math</a>, <a href = "http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigDecimal.html">Java BigDecimal</a>, and <a href = "http://docs.oracle.com/javase/1.5.0/docs/api/java/math/BigInteger.html">Java BigInteger</a>. The Java solution by the winner Stacy is included at the bottom of the test suite.

Solve

Solution Stats

19 Solutions
7 Solvers

Last Solution submitted on Oct 18, 2020

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Problem Tags

biginteger contest gjam java probability tree

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 42779. GJam March 2016 IOW: Polynesiaglot Large

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Suggested Problems

More from this Author247

Problem Tags

Community Treasure Hunt

Problem 42779. GJam March 2016 IOW: Polynesiaglot Large

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Suggested Problems

More from this Author247

Problem Tags

Community Treasure Hunt

Players