Problem 44077. GJam 2017 Kickstart: Vote (Large)
This Challenge is derived from GJam 2017 Kickstart Vote. This is the first 100 large cases with 0<=M<N<=2000.
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. GJam Kickstart solutions(C++,Python).
Solution Stats
Problem Comments
-
1 Comment
Tip: This kind of problem that seems incredibly hard usually have a formula (someone already researched this). Find the formula, and solve the problem.
Solution Comments
Show commentsProblem Recent Solvers10
Suggested Problems
-
Determine whether a vector is monotonically increasing
20890 Solvers
-
400 Solvers
-
Is my wife right? Now with even more wrong husband
1322 Solvers
-
293 Solvers
-
538 Solvers
More from this Author308
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!