Editorial for JDCC '16 Contest 3 P5 - CPT Elections
Submitting an official solution before solving the problem yourself is a bannable offence.
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 , where represents the votes that André received, represents the votes that Bertrand received and is the minimum difference between their votes. Note that is the choose function. Here is a detailed proof of the formula.
To calculate the answer, use the property when calculating the choose function.
For the division, use the property , where is the modular inverse of .
Time Complexity: , due to the fact that the complexity of the choose function is