ToujoursAffame's blog

A Question related to Probabilities
By ToujoursAffame, history, 7 years ago, In English

I saw this question on Hackerearth in a recent college contest .Link is here.(Editorial is not available).Can someone please help me here. I think this is related to linearity of expectation values ,But How do we model this problem in that way??? Please share your approach to this problem :) Thanks in advance ...

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

I'd think you solve it like this: First note that every single coin has the same probability of being head/tails (H and 1-H). You have heads[i] which is the probability of getting heads.

heads[0]=1.0

heads[i]=heads[i-1]*probability of not choosing this coin+(1-heads[i-1])*probability of choosing this coin

The answer would simply be n*heads[k]

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks for the reply tfg but Can you elaborate about heads[i] here ??? What does it means ??

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      The probability of the coin being heads after turning a[1], a[2], ..., a[i]. So 1-heads[i] is the probability of it being tails.

      → Reply