https://codeforces.net/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 [submission:279326895]↵
↵
↵
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 [submission:279326895]↵
↵
