i know this is trivial question but i am struck at why this happens

consider this..

You are given $N$ lamps and four switches. The first switch toggles $all$ lamps, the second the $even$ lamps, the third the $odd$ lamps, and last switch toggles lamps $1, 4, 7, 10, ... .$

Given the number of lamps, $N$, the number of button presses made (up to $10,000$), and the state of some of the lamps (e.g., lamp $7$ is off), output all the possible states the lamps could be in.

Naively, for each button press, you have to try $4$ possibilities, for a total of $4^{10000}$ (about $10^{6020}$ ), which means there's no way you could do complete search (this particular algorithm would exploit recursion).

Noticing that the order of the button presses does not matter gets this number down to about $10000^4$ (about $10^{16}$ ), still too big to completely search (but certainly closer by a factor of over $10^{6000}$ )

This question has been already answered here ... my question is are we considering order in first case... i'm totally getting confused.. Simple combinations - Party Lamps [IOI 98]

i am not getting that convinced that we are considering order in first and case and not in second case

let's consider string $S="abcd"$

now to generate power set as every char has two possibilities (0 or 1) so no: strings in power set $=2^4=2*2*2*2$

first possibility $0000 (empty string)$

second possibility $1000 (a)$

third possibility $0100(b)$

i don't think i have taken order into consideration here while generating this...if i go by explanation above when order doesn't matter it should be $C(4,2)$, i am utterly confused

explain it in as simple way as it can be explained...


You are correct that the order of pressing the switches doesn't matter, but also because each switch is a toggle all that matters is whether each switch is pressed an even or odd number of times. Now you only have $2^4$ possibilities as each switch can be pressed once or not. As the sum of the parities has to equal the parity of the total number of presses, you only have eight possible configurations for a given number of presses when that number is three or higher.

  • $\begingroup$ I don't see what the two cases are. As you say, the order of button presses does not matter, so we do not consider the order of the presses. All we care about is how many times each button is pressed. For a given total number of presses, this makes it a stars and bars problem. For $10,000$ presses, there are $10003 \choose 3$ ways ways to choose the number of presses. $\endgroup$ – Ross Millikan Aug 26 '16 at 4:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.