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 :( :( :(

Edit: Fixed the formula for odd

kand added the simplified version.Thank you very much :).

need to expand the terms :D

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

a_{0}= (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 yetEDIT: 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

pwhen using this geometric series approachI 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

itoggles afterkturns for given light is actuallyC_{k}^{i}·p^{i}·p^{k - i}(binomial distribution).Now a bit about where my formula came from:

p) +p)^{k}=C_{k}^{0}(1 -p)^{k}+C_{k}^{1}(1 -p)^{k - 1}p^{1}+C_{k}^{2}(1 -p)^{k - 2}p^{2}+C_{k}^{3}(1 -p)^{k - 3}p^{3}+ ...p) -p)^{k}=C_{k}^{0}(1 -p)^{k}-C_{k}^{1}(1 -p)^{k - 1}p^{1}+C_{k}^{2}(1 -p)^{k - 2}p^{2}-C_{k}^{3}(1 -p)^{k - 3}p^{3}+ ...Subtracting one from another you will get:

((1 -p) +p)^{k}- ((1 -p) -p)^{k}= 2·C_{k}^{1}(1 -p)^{k - 1}p^{1}+ 2·C_{k}^{3}(1 -p)^{k - 3}p^{3}+ ...