is it possible to switch all the bulbs using any of the m switches any number of time

algorithm
dynamic-programming

#1

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


#2

This is a on going contest question. Don’t ask till the contest is over


#3

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.


#4

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


#5

Where is this an ongoing contest? Do you have a link?


#6

please provide the link to the question ?


#7

##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


#8

Ha ha XD !


#9

@l_returns - what, you’re not considering the order you flip the switches in? Multiply another m! in immediately.


#10

lol @joffan… Correct…


#11

please provide the link to the contest if this is ongoing?


#12

I think it is live here :

LINK


#13

“There is actually a very simple solution to this.”, why not share that then? XD


#14

Did you just solve P = NP ?


#15

A very nice solution, thank you


#16

why not share that then? XD

On going contest. Cannot let him get plagiarised :stuck_out_tongue:

Did you just solve P = NP ?

Wheres my million dollars :frowning:

A very nice solution, thank you

You’re welcome. Keep it a secret tho :wink:


#17

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.


#18

LMAO @vijju123… Very nice solution… seems like best solution for this question… Will keep this link to share when people ask for this question


#19

Packs of 50 XD


#20

Hahahahahaha :smiley: :smiley: :smiley: ROFL u deserve Codechef Laddus for this answer ! :smiley: :smiley: :smiley: