Sanzee's blog

11605 — Lights inside a 3d Grid (help needed)
By Sanzee, 10 years ago, In English

I am stuck in this problem for some time now :( :(. it will be very helpful if anyone can give me some hint.

problem link : problem

My idea :

lets consider each light individually.
Let p is the probability of selecting the light. this p can be found easily by calculating each dimension of the 3d cube separately.

Now the expectation for a light will be sum over i(1 to k) : p^i * (1-p)^(k-i). (K is the number of turns) Now we only need to add the terms where i is odd as only then the light will be ON.

calculating this for all the bulbs is obviously time out :( :( :( is there any close form? i can't find it :( :( :(

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

Edit: Fixed the formula for odd k and added the simplified version.

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

    Thank you very much :).

    need to expand the terms :D

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

      If I'm not mistaken, there is no need to expand the terms. Its just thinking about the sum as a sum through a Geometric Progression. If we set a0 = (1 - p)k, we have , therefore . It's the same as saying we have a GP with as it's ratio.

      Now you can just apply basic sum over PG formula to get the end result, using n = ⌊ K / 2⌋, but I couldn't get it right yet

      EDIT: I got it right for the test cases now, I was calculating the expected number of turned off lights..

      EDIT2: Now that UVa is back, I tested it there, but the simple fact that my solutions uses 2 "pow" calls gives TLE, while with the equation from Jacob I got AC

      EDIT3: There are some tricky corner cases for special values of p when using this geometric series approach

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

        I am not sure how you ended up with geometric progression when there must obviously be binomial coefficients somewhere.

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

          That's what I thought in first place, but couldn't go anywhere from this. But I couldn't fix my code with the geometric progression approach either...

          Can you explain how you ended up with this formula?

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

            Probability to observe exactly i toggles after k turns for given light is actually Cki·pi·pk - i (binomial distribution).

            Now a bit about where my formula came from:

            • ((1 - p) + p)k = Ck0(1 - p)k + Ck1(1 - p)k - 1p1 + Ck2(1 - p)k - 2p2 + Ck3(1 - p)k - 3p3 + ...
            • ((1 - p) - p)k = Ck0(1 - p)k - Ck1(1 - p)k - 1p1 + Ck2(1 - p)k - 2p2 - Ck3(1 - p)k - 3p3 + ...

            Subtracting one from another you will get:

            ((1 - p) + p)k - ((1 - p) - p)k = 2·Ck1(1 - p)k - 1p1 + 2·Ck3(1 - p)k - 3p3 + ...

            → Reply