11605 - Lights inside a 3d Grid

All about problems in Volume 116. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sanzeee
New poster
Posts: 6
Joined: Tue Oct 19, 2010 9:56 pm

Re: 11605 - Lights inside a 3d Grid

Post by sanzeee » Thu Oct 30, 2014 5:39 pm

to solve this problem i derived the following equation for a single light bulb:
Let p is the probability of selecting the light.
So the expectation for the light will be sum over i(1 to k) : p^i * (1-p)^(k-i). 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 bulb is obviously time out :( :( :(
is there any close form? i can't find it :( :( :(

thanks in advance.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11605 - Lights inside a 3d Grid

Post by brianfry713 » Thu Oct 30, 2014 11:48 pm

You can solve each test case in O(N * M * P)
Check input and AC output for thousands of problems on uDebug!

sanzeee
New poster
Posts: 6
Joined: Tue Oct 19, 2010 9:56 pm

Re: 11605 - Lights inside a 3d Grid

Post by sanzeee » Wed Nov 05, 2014 7:23 am

I got the idea of the closed form. thanks to Jacob from codeforces

thanks anyways.

Post Reply

Return to “Volume 116 (11600-11699)”