### Sanzee's blog

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

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 :( :( :(  Comments (6)
 » 7 years ago, # | ← Rev. 4 → Edit: Fixed the formula for odd k and added the simplified version.
•  » » 7 years ago, # ^ | ← Rev. 4 →   Thank you very much :). need to expand the terms :D
•  » » » 7 years ago, # ^ | ← Rev. 4 →   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
•  » » » » I am not sure how you ended up with geometric progression when there must obviously be binomial coefficients somewhere.
•  » » » » » 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?
•  » » » » » » 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 + ...