iamskp's blog

Atcoder Problem C (SWITCH)
By iamskp, history, 4 years ago, In English

I was doing this problem from Atcoder : https://atcoder.jp/contests/abc128/tasks/abc128_c

Can someone please explain the solution?

I have seen the editorial but couldn’t understand it.

Solution link: https://atcoder.jp/contests/abc128/submissions/15518338 (Python)

Solution link: https://atcoder.jp/contests/abc128/submissions/5640467 (C++)

  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is saying that you should use a brute force approach, going through every single possible state of the switches. Say you have 2 switches, That means there are 2^2 = 4 different states, namely 00, 01, 10, and 11 (where 1 represents ON and 0 represents OFF), Because the bounds are so low, even with an exponential complexity you should be able to solve the question with this approach.

a.k,a

  • iterate through all possible states as binary numbers
  • check for all states whether all the lightbulbs would be on or not
→ Reply