Since the editorial hasn't dropped yet for today's problem E plz share your best proofs on why starting from the minimum value is optimal , couldn't prove it for a long time , iam really interested In hearing Your proofs

edit : I can't sleep without hearing an intuitive proof and it doesn't look like the editorial is dropping soon

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 279326895

i was too sleepy and decided to quickly solve a problem before sleeping so i submitted a quick code for this problem

https://codeforces.net/problemset/problem/1132/E

even tho my code is wrong it still passes all 90 tests but while i was trying to prove my solution i realized it was wrong and here is a counter example

889

0 0 0 0 0 0 120 105

here the the answer is 889 but my code outputs 888

271074483

iam just curious how its even possible to pass 90 tests with a wrong code

UPD : the test has been added to the problem and now the submission shows WA on that test

how would you write a checker for problem B from the contest Think-cell round 1 with complexity less than n^2 ?

in others words given a permutation of size n determine weather there exists 2 indices i and j (1 <= i,j <n) i != j , where p(i) devides p(j) and p(i+1) devides p(j+1)