Problem 44077. GJam 2017 Kickstart: Vote (Large)

Created by Richard Zapor in Community

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

80.0% Correct | 20.0% Incorrect
Last solution submitted on Dec 13, 2018