Editorial for JDCC '16 Contest 3 P5 - CPT Elections

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: atarw

This problem is almost identical to Bertrand's Ballot Problem, and is solved in a similar way.

The answer to the problem is given by the formula $$\frac{N - KM}{N + M} {N + M \choose K}$$, where $$N$$ represents the votes that André received, $$M$$ represents the votes that Bertrand received and $$K$$ is the minimum difference between their votes. Note that $${N \choose K} = \frac{N\,!}{(N - K)\,!K\,!}$$ is the choose function. Here is a detailed proof of the formula.

To calculate the answer$$\bmod 10^9 + 7$$, use the property $$(A \times B) \bmod M \equiv ((A \bmod M) \times (B \bmod M)) \bmod M$$ when calculating the choose function.

For the division, use the property $$(A \div B) \bmod M \equiv ((A \bmod M) \times (B^{-1} \bmod M)) \bmod M$$, where $$B^{-1}$$ is the modular inverse of $$B \bmod M$$.

Time Complexity: $$\mathcal{O}(\min(N, M))$$, due to the fact that the complexity of the choose function $$N \choose K$$ is $$\mathcal{O}(\min(K, N - K))$$