You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

raghav225311's gravatar image

2★raghav225311
71
accept rate: 0%

3

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

(02 Dec, 10:52) l_returns4★
1

Ha ha XD !

(02 Dec, 11:30) admin55★

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

(02 Dec, 12:31) joffan5★

lol @joffan... Correct...

(02 Dec, 15:07) l_returns4★

Can someone share what was the other question present in the contest.

(03 Dec, 08:13) mohit96m4★

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.

link

answered 02 Dec, 16:27

vijju123's gravatar image

5★vijju123 ♦♦
15.1k11857
accept rate: 18%

edited 02 Dec, 16:31

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

(02 Dec, 18:43) abdullah7686★

Did you just solve P = NP ?

(02 Dec, 18:45) abdullah7686★
1

A very nice solution, thank you

(02 Dec, 18:55) swetankmodi ♦♦6★

why not share that then? XD

On going contest. Cannot let him get plagiarised :p

Did you just solve P = NP ?

Wheres my million dollars :(

A very nice solution, thank you

You're welcome. Keep it a secret tho ;)

(02 Dec, 20:38) vijju123 ♦♦5★
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) joffan5★
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) l_returns4★

Packs of 50 XD

(03 Dec, 00:43) l_returns4★

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

(03 Dec, 00:59) rohan_bose955★

@admin , please fulfil the above suggestions. :) XD

(03 Dec, 01:18) vijju123 ♦♦5★
showing 5 of 9 show all

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

link

answered 01 Dec, 19:36

jk9873's gravatar image

4★jk9873
111
accept rate: 0%

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

(02 Dec, 09:46) joffan5★

please provide the link to the question ?

(02 Dec, 10:23) pavitra_ag4★

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

(02 Dec, 15:21) swetankmodi ♦♦6★

I think it is live here :

LINK

(02 Dec, 17:24) noob_1234560★

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

link

answered 03 Dec, 02:25

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

1

Are you sure you can use Gaussian elimination here? There are m equations and n variables, m!= n

(05 Dec, 13:27) apptica5★

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://cp-algorithms.com/linear_algebra/linear-system-gauss.html

(05 Dec, 17:38) vivek_19982996★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,032
×1,643

question asked: 01 Dec, 18:11

question was seen: 1,157 times

last updated: 05 Dec, 17:38