Please read the new rule regarding the restriction on the use of AI tools. ×

guesshere's blog

Expected value problem E atcoder beginner contest 326
By guesshere, history, 11 months ago, In English

Hi everyone, referring to yesterday's problem E of atcoder beginner conest 326 Link Can somebody please explain the how to solve such problems? Does it always boil down to writing the answer for a few test cases and observing the pattern? Also can somebody please explain the editorial elaboratively?

  • Vote: I like it
  • -20
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Improve your problem-solving ability

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want to know about expected value you can read Errichto's blog on it. I can try to explain the editorial.

X is a random variable that denotes the total salary earned over month. Now its difficult to find the probablity that the total salary is X so Can we express the random variable X as X=x1+x2+x3......xn where xi is a random variable and xi = Ai with probabablity pi and xi=0 with probablity 1-pi. So E[xi] = Ai*pi +0*(1-pi). We know E[X+Y]=E[X]+E[Y] Now we will get the formula for expected value as given in the editorial.

How we got the formula for pi? This will be easy to explain if we use an example. Suppose N=6.Now what is the probablity that we will get A4 during the procedure.There are 4 cases in which this is posssible. Before getting 4 on dice, the value of x was 0 OR x=1 OR x=2 OR x=3.Probablity of getting 4 on dice is simply 1/6 and the probabilty that value of x was i previously is pi which is same as getting Ai (on previous turn). So p4 = 1/6*p0 + 1/6p1 + 1/6p2 +1/6p3. Generalising this we will get the formula for pi.

I am not sure if I am correct about breaking of random variable into x1,x2...xn. Correct me if I am wrong.

→ Reply