### PROBLEM LINK:

**Author:** Priyanshu Jain

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

DP, Math etc.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

**Author:** Priyanshu Jain

MEDIUM

DP, Math etc.

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?