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))


Comments

There are no comments at the moment.