For problem B, I missed the case for n = 3 and got wrong answer. I praticed so hard, getting top 2000 on previous years round 2 virtually. Now i don't pass the round 1. Unlucky me haha. Congratulations to you.
Thanks! 1. It is known that if you stand at point A of segment from 0 to A+B, and each second you move by +1 or -1 with 50/50 probability, then the expected time before reaching 0 or A+B is A*B. 2. In this problem, if X is the random value from the problem (how many days you need to reduce your weight W -> G), then X = X_1 + ... + X_n, where n = W - G, each X_i is the random value for the number of steps to reduce your weight by 1 (no matter where you start), and all X_i are identically distributed, so the expectation E(X) = E(X_1) * n. 3. E(X_1) is the same as "you stand at point 1 on the segment between 0 and 2L+2, you need to reach any endpoint", so the expectation is 1 * (2L + 1)
@@ashishchokhani9084 for example, if we start from 5, allow ourselves to weigh at most 8, and want to reach 4. Then it's the same as if we started from 5, didn't constrain ourselves at all, and wanted to reach 4 or 12, whatever happens first. Because for every path to reach 4 or 12, we can just reflect everything > 8 and pretend that we did, say, not 8->9->10->9->8, but 8->7->6->7->8 instead. This is the brief idea
I never not set it, because the default precision can be very unreliable. For example, from now on you will always set it too, because you encountered this pitfall yourself
For problem B, I missed the case for n = 3 and got wrong answer. I praticed so hard, getting top 2000 on previous years round 2 virtually. Now i don't pass the round 1. Unlucky me haha.
Congratulations to you.
@@kimjong-un4521 yeah that sucks man
explain C . i admire how strong you are for solving it in 13 mins
Thanks!
1. It is known that if you stand at point A of segment from 0 to A+B, and each second you move by +1 or -1 with 50/50 probability, then the expected time before reaching 0 or A+B is A*B.
2. In this problem, if X is the random value from the problem (how many days you need to reduce your weight W -> G), then X = X_1 + ... + X_n, where n = W - G, each X_i is the random value for the number of steps to reduce your weight by 1 (no matter where you start), and all X_i are identically distributed, so the expectation E(X) = E(X_1) * n.
3. E(X_1) is the same as "you stand at point 1 on the segment between 0 and 2L+2, you need to reach any endpoint", so the expectation is 1 * (2L + 1)
@@Golovanov399 Can you please explain how segment range turns out to be 0 and 2L+2?
@@ashishchokhani9084 for example, if we start from 5, allow ourselves to weigh at most 8, and want to reach 4. Then it's the same as if we started from 5, didn't constrain ourselves at all, and wanted to reach 4 or 12, whatever happens first. Because for every path to reach 4 or 12, we can just reflect everything > 8 and pretend that we did, say, not 8->9->10->9->8, but 8->7->6->7->8 instead. This is the brief idea
@@Golovanov399 Understood, Thank u so much!!
@@Golovanov399 noice one 🎉🎉🎉
at 4:50 how did you know to use setprecision when already using long double, i got wrong answer due to precision error for the A prob :(
I never not set it, because the default precision can be very unreliable. For example, from now on you will always set it too, because you encountered this pitfall yourself
@@Golovanov399 lol exactly 😭😂
orz