Problem 44077. GJam 2017 Kickstart: Vote (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/6304486/dashboard#s=p1\"><w:r><w:t>GJam 2017 Kickstart Vote</w:t></w:r></w:hyperlink><w:r><w:t>. This is the first 100 large cases with 0&lt;=M&lt;N&lt;=2000.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"http://code.google.com/codejam\"><w:r><w:t>Google Code Jam 2017 Qualifier</w:t></w:r></w:hyperlink><w:r><w:t> is March 7, 2017. Typically four challenges with small and large aspects with 27 hours to complete.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The GJam story is given N and M votes, where N&gt;M, determine the number of voting sequences for which N is always in the lead divided by the total number of sequences(N+M)!.</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> [N,M], the quantity of votes to N and M</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> [V], the ratio of N always leading sequences to total sequences</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> [N,M] [V]; [2,1] [0.33333333]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For the case [2,1] there are 6 sequences [N1N2M1,N2N1M1,N1M1N2,N2M1N1,M1N1N2,M1N2N1] with only the first two always having N in the lead.</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> Brute force permutations and counting will not succeed in a timely manner for 0&lt;=M&lt;N&lt;=2000 as 2000! may be a bit large. Determining the inherent mathematical pattern is usually the best way to succeed in GJam. </w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://code.google.com/codejam/contest/6304486/scoreboard#vf=1\"><w:r><w:t>GJam Kickstart solutions(C++,Python)</w:t></w:r></w:hyperlink><w:r><w:t>.</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/6304486/dashboard#s=p1">GJam 2017 Kickstart Vote</a>. This is the first 100 large cases with 0&lt;=M&lt;N&lt;=2000.<a href = "http://code.google.com/codejam">Google Code Jam 2017 Qualifier</a> is March 7, 2017. Typically four challenges with small and large aspects with 27 hours to complete.The GJam story is given N and M votes, where N&gt;M, determine the number of voting sequences for which N is always in the lead divided by the total number of sequences(N+M)!.Input: [N,M], the quantity of votes to N and MOutput: [V], the ratio of N always leading sequences to total sequencesExamples: [N,M] [V]; [2,1] [0.33333333]For the case [2,1] there are 6 sequences [N1N2M1,N2N1M1,N1M1N2,N2M1N1,M1N1N2,M1N2N1] with only the first two always having N in the lead.Theory: Brute force permutations and counting will not succeed in a timely manner for 0&lt;=M&lt;N&lt;=2000 as 2000! may be a bit large. Determining the inherent mathematical pattern is usually the best way to succeed in GJam. <a href = "http://code.google.com/codejam/contest/6304486/scoreboard#vf=1">GJam Kickstart solutions(C++,Python)</a>.

This Challenge is derived from <http://code.google.com/codejam/contest/6304486/dashboard#s=p1 GJam 2017 Kickstart Vote>. This is the first 100 large cases with 0<=M<N<=2000.

<http://code.google.com/codejam Google Code Jam 2017 Qualifier> is March 7, 2017. Typically four challenges with small and large aspects with 27 hours to complete.

The GJam story is given N and M votes, where N>M, determine the number of voting sequences for which N is always in the lead divided by the total number of sequences(N+M)!.

*Input:* [N,M], the quantity of votes to N and M

*Output:* [V], the ratio of N always leading sequences to total sequences

*Examples:* [N,M] [V]; [2,1] [0.33333333]

For the case [2,1] there are 6 sequences [N1N2M1,N2N1M1,N1M1N2,N2M1N1,M1N1N2,M1N2N1] with only the first two always having N in the lead.

*Theory:* Brute force permutations and counting will not succeed in a timely manner for 0<=M<N<=2000 as 2000! may be a bit large. Determining the inherent mathematical pattern is usually the best way to succeed in GJam. <http://code.google.com/codejam/contest/6304486/scoreboard#vf=1 GJam Kickstart solutions(C++,Python)>.

Solve

Solution Stats

12 Solutions
9 Solvers

Last Solution submitted on May 04, 2021

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Rafael S.T. Vieira on 10 Oct 2020

Tip: This kind of problem that seems incredibly hard usually have a formula (someone already researched this). Find the formula, and solve the problem.

Problem Recent Solvers9

Problem Tags

Community Treasure Hunt

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

Start Hunting!