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 ...
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | maroonrk | 155 |
| 6 | nor | 154 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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]
Thanks for the reply tfg but Can you elaborate about heads[i] here ??? What does it means ??
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.
I think I have to analyse it a bit more .... Thanks for help tfg though :)