Hi,
There is actually a very simple solution to this.
We will use what we call, Dummy States. Instead of using traditional on and off, which goes upto 2^m (i.e. exponential) solution, and hence is useless for most of the problems, we can try to find a polynomial time solution which might fetch us 100 points.
Now, the above solution fails because it is exponential. What we can do is, bring down the complexity by adding few more states, called Dummy States (you can read about the concept here). Introduce N-2 dummy states. If N-2 goes to negative, set the total states to N+\delta (where \delta=5)for the theorem to work.
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 dummy state solution, we dont need to do that!! As soon as we see that there is a dummy state, immediately terminate the check and try another combination. Now we dont have to go upto end of the entire list, as we can terminate as soon as we get a dummy state. Worst case its still linear, but we can use some maths to show that the upper bound for such cases would be very low and bounded by an inverse function of N.
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)
\implies f(X) \equiv Polynomial \ of \ Degree(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.
