Upgrading.....'s blog

UVA 11762
By Upgrading....., history, 6 years ago, In English

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?

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

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it still adds 1 to the tally because it still counts as a move. don't understand this part.....

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the first 1 is for blank move? so, why not another 1 for invalid prime?

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

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Understand Perfectly...Can you give some resource to learn Expected Value effectively?

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

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            E(1) = 1/2( E(0) + 1) + 1/2( E(2) + 1) am i correct for previous assumption...?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              How many coins do you have to flip on average to get 2 Heads in a row?

              ans: 6 ?

              → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Upgrading..... (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Upgrading..... (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Upgrading..... (previous revision, new revision, compare).

→ Reply