We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Ad Hoc
  4. Kundu And Bubble Wrap
  5. Discussions

Kundu And Bubble Wrap

Sort by

recency

|

6 Discussions

|

  • zweitekonto96
     + 0 comments

    Haskell

    series :: [(Double, Double)]
series = (1,1):((\(i, acc) -> (i+1, acc + 1/(i+1))) <$> series)

main = interact $ show 
  . (\[m,n] -> (fromIntegral (m*n)) * (snd $ series !! (m*n-1))) 
  . map read
  . words

  • ipergenitsa
     + 0 comments

    If we have 2 bubbles, why expected number of steps = 3? Minimum is 4:

    1. select one bubble
    2. pop it
    3. select another bubble
    4. pop it

    Seems I don't understand the problem. Can somebody explain, please?

  • arnautdaniel
     + 0 comments

    The fun part about this problem is realizing you HAVE to do it mathematically. I tried about 3 other standard methods before I realized I'd have to research the problem more.

    It's actually very fun and rather easy. I recommend pencil and paper, try to get as far as possible and then go read about the Coupon Collectors problem. After that it's trivial.

  • CKoenig
     + 1 comment

    this is really just math so sit down with pen and pencil and figure it out.

    In case you need some hints, consider this relation:

    expectedTime cntPoped cntUnpoped =
   (cntPoped / (cntPoped + cntUnpoped)) * (1 + expectedTime cntPoped cntUnpoped)
   + (cntUnpoped / (cntPoped + cntUnpoped)) * (1 + expectedTime (cntPoped + 1) (cntUnpoped - 1))

    now of course this will not work as the recursion never stops - here comes the math (solve x = a*(1+x) + y for x and compare)

    the rest should be really easy

  • paulpach
     + 0 comments

    This is known as the Coupon collector problem.