UVA 11762
Suppose we want to calculate E(N) where N is a number,k is the number of it’s distinct prime factors and p is the number of primes < n
Normal rule, E(N)=(1/p)*(1 + E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak)) + ((p-k)/p)*(1 + E(N))
What is the wrong about this logic?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 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 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
The problem statement also counts "blanks" as a move. Even if you whiff, get an invalid prime, and remain at D, it still adds 1 to the tally because it still counts as a move.
it still adds 1 to the tally because it still counts as a move. don't understand this part.....
the first 1 is for blank move? so, why not another 1 for invalid prime?
Let's look at a simpler problem. How many coins do you have to flip on average to get 2 Heads in a row?
For this we define E(n) being "expected number of flips if I already have n heads". Obviously E(2) = 0 and we just want E(0).
How do we compute E(0)? There is a 50% chance that we get tails, so that is still E(0) but + 1 because we still flipped the coin. There is a 50% chance that we get heads, so that is E(1) and also + 1 because we also flipped the coin. So that is
, and notice if you distribute the fractions everything becomes +1 in the end.
So to answer your question, yes you put the +1 for invalid prime AND for valid prime. But you put the +1 inside the parenthesis, and the
gets multiplied and distributed. The +1 is outside the parenthesis.
Understand Perfectly...Can you give some resource to learn Expected Value effectively?
Sorry, I didn't learn Expected Value from one particular source :((
I just picked it up after doing enough Math and Programming problems. You can probably search Codeforces for the Probability tag.
E(1) = 1/2( E(0) + 1) + 1/2( E(2) + 1) am i correct for previous assumption...?
How many coins do you have to flip on average to get 2 Heads in a row?
ans: 6 ?
Correct :)
Auto comment: topic has been updated by Upgrading..... (previous revision, new revision, compare).
Auto comment: topic has been updated by Upgrading..... (previous revision, new revision, compare).
Auto comment: topic has been updated by Upgrading..... (previous revision, new revision, compare).