given a series of n bulbs initially all switched off.Now you also have m switches each of which controls some continous range of light bulbs L to R(both inclusive) Now you have to determine if it is possible to switch on all bulbs using any of the M switches any number of times. Note:Using a switch flips the status of all bulbs it controls i.e from on to off or vice versa input format: T number of test case The next line of the input contains two spaced integer N and M the no of bulbs and switches Each of next M lines contain two space seperated integer l and r the operating range of ith switch. sample input: 2 5 2 1 2 3 5 Answer yes use both switches once and we can switch on all bulbs asked 01 Dec, 18:11

Hi, There is actually a very simple solution to this. We will use what we call, Now, the above solution fails because it is exponential. What we can do is, bring down the complexity by adding few more states, called Now, do a basic recursion+backtracking. Instead of choosing from the original two states, chose from those 2 PLUS the dummy states. Thats the only change to do!! At first sight one can feel that this is increasing the complexity, but in the time complexity section we will discuss how this is polynomial. Now, here is the key. Once you are at the end of recursion and have chosen the states of switches do the usual check, sped up with dummy states! In brute force, you had to iterate over ALL chosen switches, and check if all lightbulbs are lit up or not. In our Now, to the $time$ $complexity$ part. We can clearly show by Chernoff's bound that the time complexity will be $O(f(N))$ where $f(N)$ is a polynomial of degree $N$!! A slight proof for it is below $f(X)= K*(X+X/2+X/3+X/4....+1)$ (averaging among all subsets. You can use SoS dp to find this.) $\implies f(X) \le K*(X^N+(X/2)^N....+1^N)$ To practically check the time complexity, you can use the $time()$ or $clock()$ function (whichever supported in your language). You'd see that for $N=1$ the answer is answered in mere nanoseconds, hence the time complexity is polynomial. answered 02 Dec, 16:27
"There is actually a very simple solution to this.", why not share that then? XD
(02 Dec, 18:43)
Did you just solve P = NP ?
(02 Dec, 18:45)
1
A very nice solution, thank you
(02 Dec, 18:55)
On going contest. Cannot let him get plagiarised :p
Wheres my million dollars :(
You're welcome. Keep it a secret tho ;)
(02 Dec, 20:38)
1
And if you find you haven't got enough dummy states, go and ask your professor for more. They're usually available in packs of 50.
(02 Dec, 22:22)
1
LMAO @vijju123.... Very nice solution.. seems like best solution for this question... Will keep this link to share when people ask for this question
(03 Dec, 00:42)
Packs of 50 XD
(03 Dec, 00:43)
Hahahahahaha :D :D :D ROFL u deserve Codechef Laddus for this answer ! :D :D :D
(03 Dec, 00:59)
@admin , please fulfil the above suggestions. :) XD
(03 Dec, 01:18)
showing 5 of 9
show all

Ohk since contest ended We could solve it as follows: For each of n bulbs first find in which switches does it lies in. Lets say first bulb lies in switch 1 and 3 So we have first equation as: x1+x3=1 Similarly do for all bulbs We'll get n equations Now just see if there exists a solution to this(and yeah consider all operation modulo 2) Using gaussian elimination ,u can do it in N^3/64 answered 03 Dec, 02:25
1
Are you sure you can use Gaussian elimination here? There are m equations and n variables, m!= n
(05 Dec, 13:27)
Oob right...sorry i haven't used gaussian elimination method,i asked my friend how to solve linear equations,and he suggested this... Though u can refer this for m!=n case: http://cpalgorithms.com/linear_algebra/linearsystemgauss.html
(05 Dec, 17:38)

if it is ongoing contest then I have a solution...
keep a switch on/off (2 combination per switch)
check every combination ( $O(2^m)$)
for each combination check if all bulbs are on
all over complexity ( $O(2^m*n*m)$) XD
Ha ha XD !
@l_returns  what, you're not considering the order you flip the switches in? Multiply another $m!$ in immediately.
lol @joffan... Correct...
Can someone share what was the other question present in the contest.