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

general
,
21

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

22

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

23

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

1 Like
24

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