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.