javacoder1's blog

By javacoder1, history, 8 years ago, In English

This is one of the problems of mathematical expectation. As explained in the editorial we have to calculate the answer based on the number of the inversions of the permutation.

THe first two points in the editorial are clear

1. it is clear that after a Jeff's step inversions will become lower by 1 2. it is clear that after a Furik's step inversions will be on 1 lower with porbability of 0.5, and on 1 greater with probability of 0.5 .

but for the third point i am finding it difficult to comprehend.Generally for finding the total expectation we multiply the thing like some value associated with the object and the probabilty of its occurence and then take the summation over all the cases.(Correct if i am wrong) So how did the third point make sense

3. we have the formula for an answer ansI = 1 + 1 + ansI - 1 - 1 × 0.5 + ansI - 1 + 1 × 0.5

Please explain.

link to problem http://codeforces.com/contest/351/problem/B

any links to similar problems are highly appreciated

  • Vote: I like it
  • 0
  • Vote: I do not like it