https://mirror.codeforces.com/problemset/problem/1540/B
refer to the tutorial of this problem which provides a solution to the following problem using dp in o(A * B) and later on i'll provide a o(A + B) solution that works but i need your help in proving it
the problem : given two numbers A and B each second one of them is choosen with chance 1 / 2 each (equiprobable) and decreased by 1 , if one of the numbers reachs 0 the other is choosen with probability 1 until it reachs zero then we are done , find the probability that A reachs 0 before B
again for the o(A * B) solution refer to the tutorial
now the reason we cant just calculate the favourable outcome and divide it by total outcome is because not all outcomes have the same probability as the events and dependent such that whenever one of them reachs 0 the probability of choosing the other one is 1 afterwards but lets look at a different problem imagine u are going to make A + B picks and pick A or B equiprobable , find the probability that you pick A , A times before picking B , B times , we are not decreasing anything here and can pick A (A + B) times now if we think about this problem for a bit we realize that the same dp solution represented in the tutorial solves this one but instead this problem has a combinatorial solution in o(A + B) because all paths have the same probability as both events and independent and picking A however many times doesnt change the chance of picking B so now we have both problems that share a dp solution but one of them offers a combinatorial solution which we can use for the first one how do we prove that this combinatorial approach works for the first problem ?
heres the submission using the combinatorial approach 279326895
the combinatorial approach is relatively easy but if anybody wants me to explain it just comment below
Only read your short description of the problem, but this looks like you can just sum over the negative binomial distribution (how many trials needed until A'th success, sum from A to A+B-1). Should be O(A+B).
not sure if i fully understand you but its not the same problem you described because the events and dependent if one of A or B reachs zero u cant choose it anymore and the other is choosen with probability 100% i'll add this to the blog for clarifications
Auto comment: topic has been updated by Axial-Tilted (previous revision, new revision, compare).