Problem 2325. GJam 2014 Rd 1c: Reordering Train Cars (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/3004486/dashboard#s=p1\"><w:r><w:t>GJam 2014 Rd 1c: Reordering Train Cars (Large)</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Determine number of sequences for set of strings under the constraint that all same characters must be contiguous. The large case could have 26! or more permutations.</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> s, string of N space separated string segments of letters [a..z]. 1&lt;=N&lt;=100. Total letters &lt;=100.</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> val, number of possible sequences, modulo 1,000,000,007</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>Example:</w:t></w:r><w:r><w:t> Small Train Case examples</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ab bbbc cd Val=1 as only abbbbccd can be created\naa aa bc c Val=4 aa gives 2 positions, aa'aa''bcc,aa''aa'bcc, bcccaa'aa'',bcccaa''aa'\nabc bcd Val=0 as c is internal and thus can not connect to c of abc]]></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>Theory:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/2324-gjam-2014-rd-1c-train-cars\"><w:r><w:t>Train Small Spoilers</w:t></w:r></w:hyperlink></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Large Case specific info. See</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>Usage of java math</w:t></w:r></w:hyperlink><w:r><w:t> for unlimited precision. Note intValue gives more precision than floatValue. No java factorial exists so a function, non-recursive, is suggested. The small solution can be converted via java BigInteger factorial, mod, multiply, and intValue to solve the large case.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Additional GJam solutions can be found at</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://go-hero.net/jam\"><w:r><w:t>Example GJam Matlab solutions</w:t></w:r></w:hyperlink><w:r><w:t>. Select Find Solutions, change Language to Matlab. The Test Suite, at the bottom, contains a full GJam Small Matlab solution. No Valid Matlab solutions were submitted during the contest.</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/3004486/dashboard#s=p1">GJam 2014 Rd 1c: Reordering Train Cars (Large)</a>.Determine number of sequences for set of strings under the constraint that all same characters must be contiguous. The large case could have 26! or more permutations.Input: s, string of N space separated string segments of letters [a..z]. 1&lt;=N&lt;=100. Total letters &lt;=100.Output: val, number of possible sequences, modulo 1,000,000,007Example: Small Train Case examples<pre class="language-matlab">ab bbbc cd Val=1 as only abbbbccd can be created
aa aa bc c Val=4 aa gives 2 positions, aa'aa''bcc,aa''aa'bcc, bcccaa'aa'',bcccaa''aa'
abc bcd Val=0 as c is internal and thus can not connect to c of abc
</pre>Theory: <a href = "http://www.mathworks.com/matlabcentral/cody/problems/2324-gjam-2014-rd-1c-train-cars">Train Small Spoilers</a>Large Case specific info. See <a href = "http://www.mathworks.com/matlabcentral/cody/problems/1833-usage-of-java-math-add-multiply-pow">Usage of java math</a> for unlimited precision. Note intValue gives more precision than floatValue. No java factorial exists so a function, non-recursive, is suggested. The small solution can be converted via java BigInteger factorial, mod, multiply, and intValue to solve the large case.Additional GJam solutions can be found at <a href = "http://go-hero.net/jam">Example GJam Matlab solutions</a>. Select Find Solutions, change Language to Matlab. The Test Suite, at the bottom, contains a full GJam Small Matlab solution. No Valid Matlab solutions were submitted during the contest.

Solve

Solution Stats

6 Solutions
2 Solvers

Last Solution submitted on Dec 15, 2018

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

mmmriva on 21 May 2014

Can you please check the test suite as test 30 is uncomplete ? Thanks.

Problem Recent Solvers2

Problem Tags

2014 biginteger factorial gjam intval java permutations

Problem 2325. GJam 2014 Rd 1c: Reordering Train Cars (Large)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers2

Suggested Problems

More from this Author236

Problem Tags

Problem 2325. GJam 2014 Rd 1c: Reordering Train Cars (Large)

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers2

Suggested Problems

More from this Author236

Problem Tags

Players