SRTX16E - Editorials

PROBLEM LINK:

Practice
Contest

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?

//