https://codeforces.me/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.me/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

i've read the tutorial for this problem over 30 times and looked at many codes and it still doesnt make sense , why are we using dsu ? how does adding an edge between node a and b with weight c determine all the values on the simple path from a to b ?

if somebody had solved it i would appreciate it if u write an explanation

1615D - (XO)R-ождественское дерево

given a modular equation k = ax mod b where we know k and a and b find the smallest possible integer number for x

example (15 = 8x mod 25) , here the set of x that satisfy it up to the smallest integer are [1.875 , 3.75 , 5] but the smallest integer number is 5 how do i find the smallest integer number that satisfies the equation in o(1) or o(logb) anything thats not o(b) and above

searched alot and all i was able to find is the usage of EEX but i dont think its what iam looking for also modular inverse doesnt necessarily work since b (the mod) might not coprime with a or k

i was reading the tutorial for problem E from this round https://codeforces.me/blog/entry/125943

and it says that "And as it is known, the number of edges in the compressed tree is O(k)"

i couldnt find anything about it on the internet does anyone have a proof on why we have O(k) edges in a compressed tree ?

edit : i realized how stupid i was asking this question since we can have atmost 2k — 1 vertices in a compressed tree (where k is the number of important vertices in the main tree) there can be at most 2k — 2 edges since a tree will always have n — 1 edges

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)