PROBLEM LINK:
Author: Priyanshu Jain
DIFFICULTY:
MEDIUM
PREREQUISITES:
DP, Math etc.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
There is very simple solution to this question using Bertrand’s ballot theorem.
In combinatorics, Bertrand’s ballot problem is the question: “In an election where candidate A receives p votes and candidate B receives q votes with p > q, what is the probability that A will be strictly ahead of B throughout the count?” The answer is
p-q/p+q
Proof can be found here
How the DP part comes into play?