Блог пользователя iamskp

Автор iamskp, история, 4 года назад, По-английски

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++)

  • Проголосовать: нравится
  • -9
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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