iamskp's blog

By iamskp, history, 11 months 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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you post its editorial in English!

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I used google translate.So it might contain inaccuracies.

    Here it is :

    First, ignoring the condition, the switch on/off combination is 2 There are N streets. Switch conditions that meet the conditions It is difficult to count the states directly, so let's fix this combination as one. Then each light bulb The answer can be obtained by checking whether is lit and determining whether all are lit. This time The amount of calculation is O(MN ∗ 2 N). To fix the switch status, use DFS or switch the switch status to an N-bit integer. There is a method of encoding. This time it was a constraint that can be solved by enumerating all, but since it can be regarded as a problem to count the solutions of simultaneous equations in mod 2, It can also be obtained faster by calculating rank etc. Example answer: https://atcoder.jp/contests/abc128/submissions/5640467

»
11 months 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