gjam march 2016 iow: polynesiaglot medium -凯发k8网页登录

created by richard zapor

{"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 (<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<=l<=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 (<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 (<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<=15output: [q] max qraw is 2^50 (<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) <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>

this challenge is derived from <http://code.google.com/codejam/contest/8274486/dashboard#s=p2 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}
 
*<http://code.google.com/codejam google code jam 2016 open qualifier: april 8, 2016>*
*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

last submitted on apr 25, 2023

last 200 solutions

problem comments

solution comments

problem recent solvers

problem tags

community treasure hunt

find the treasures in matlab central and discover how the community can help you!

start hunting!

gjam march 2016 iow: polynesiaglot medium -凯发k8网页登录

solution stats

last 200 solutions

problem comments

solution comments

problem recent solvers

suggested problems

more from this author

problem tags

community treasure hunt

gjam march 2016 iow: polynesiaglot medium -凯发k8网页登录

solution stats

last 200 solutions

problem comments

solution comments

problem recent solvers

suggested problems

more from this author

problem tags

community treasure hunt

players

wechat