Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

You are given n switches and m lamps. The i-th switch turns on some subset of the lamps.…

  1. User

    You are given n switches and m lamps. The i-th switch turns on some subset of the lamps. This information is given as the matrix a consisting of n rows and m columns where ai, j = 1 if the i-th switch turns on the j-th lamp and ai, j = 0 if the i-th switch is not connected to the j-th lamp.

    Initially all m lamps are turned off.

    Switches change state only from "off" to "on". It means that if you press two or more switches connected to the same lamp then the lamp will be turned on after any of this switches is pressed and will remain its state even if any switch connected to this lamp is pressed afterwards.

    It is guaranteed that if you push all n switches then all m lamps will be turned on.

    Your think that you have too many switches and you would like to ignore one of them.

    Your task is to say if there exists such a switch that if you will ignore (not use) it but press all the other n - 1 switches then all the m lamps will be turned on. Input

    The first line of the input contains two integers n and m (1 ≤ n, m ≤ 2000) — the number of the switches and the number of the lamps.

    The following n lines contain m characters each. The character ai, j is equal to '1' if the i-th switch turns on the j-th lamp and '0' otherwise.

    It is guaranteed that if you press all n switches all m lamps will be turned on.

    Output

    Print "YES" if there is a switch that if you will ignore it and press all the other n - 1 switches then all m lamps will be turned on. Print "NO" if there is no such switch.

    Examples

    Input

    4 5 10101 01000 00111 10000

    Output

    YES

    Input

    4 5 10100 01000 00110 00101

    Output

    NO

  2. DeepSeek Assistant

    We need to determine if there exists a switch that can be ignored while still turning on all lamps when using the other n-1 switches. In other words, for each lamp, it must be turned on by at least one of the remaining switches.

    Given that with all n switches, every lamp is covered (each lamp is turned on by at least one switch). We need to know if there exists a switch such that for every lamp, there is some other switch (different from the ignored one) that turns it on. That is, no lamp is exclusively turned on by that switch alone (i.e., that switch is the sole provider for some lamp). If we remove switch i, then if there is any lamp j such that a[i][j] == 1 and for all other switches k != i, a[k][j] == 0, then lamp j would be off after ignoring i. So for i to be "ignorable", we must have that for every lamp j where a[i][j]==1, there exists some other switch k != i with a[k][j]==1. Equivalent: no lamp is uniquely covered by switch i.

    So we need to find a switch that is not essential for any lamp. That is, for each switch, if there exists a lamp where that switch is the only one covering it, then it cannot be ignored. If there is a switch where it's not the unique cover for any lamp, then answer YES.

    But careful: is it sufficient? Suppose a switch i is not uniquely covering any lamp. If we ignore i, then for any lamp j, if a[i][j]==1, then there is another switch covering it; if a[i][j]==0, then clearly other switches cover it (since all lamps are covered by all switches together, but some lamp might be covered only by i? Actually if a[i][j]==0, then lamp j is covered by other switches because overall coverage with all switches ensures that at least one switch covers it; and if i doesn't cover it, it's definitely covered by others). So yes, if i is not a unique cover for any lamp, then ignoring i still covers all lamps. So the condition is necessary and sufficient.

    Thus the problem reduces to: given a binary matrix of n rows (switches) and m columns (lamps), where each column has at least one 1 (since all lamps can be turned on by all switches together, but it's guaranteed only that when pressing all switches, all lamps will be turned on, meaning that for each lamp j, there exists at least one switch i such that a[i][j] = 1. Yes that is the condition. So each column has at least one 1. Determine if there exists a row i such that for every column j where row i has a 1, that column has at least two 1's (i.e., there exists some other row with 1 in that column). Equivalently, row i is not the only 1 in any column it participates in.

    Now n,m up to 2000, so matrix can be up to 4 million entries. We need an efficient solution.

    A naive solution: for each row i, we could check all columns j where a[i][j]=1, and verify that each such column has at least two 1's. That would be O(nm) for each row if we do it naively, leading to O(n^2m). Too large.

    We need to precompute something: For each column, count the number of 1's (i.e., how many switches turn it on). Let colCount[j] = total number of rows with a[i][j]=1. Since total coverage, each colCount[j] >= 1.

    Then for a row i to be ignorable, we need for every j with a[i][j]=1, colCount[j] >= 2. So we need to check if there exists a row i such that for all j where a[i][j]==1, colCount[j] >= 2.

    We can precompute colCount for all j in O(nm). Then for each row i, we can check all j where a[i][j]==1, and see if any colCount[j] == 1. If none (i.e., all columns covered by i have colCount >=2), then i is good. This still might be O(nm) per row? Actually if we iterate over all entries for each row, total time would be O(nm) (since we will examine each entry once while scanning each row? Wait: To check each row, we need to examine the entries in that row only. So total entries is nm. For each row i, we examine each column j where a[i][j]==1. Summed over i, the total number of 1 entries we examine is exactly the total number of 1's in the matrix. That could be up to nm in worst case (all entries 1). So total time O(nm) to check all rows after colCount is computed. That's acceptable: n,m <= 2000, n*m <= 4e6, that's fine. Even if we iterate over all entries twice (once for colCount and once for checking rows), it's fine.

    But careful: We need to check if any column in that row has colCount==1. If we simply iterate over each row and each column, that's O(n*m). That's okay. 4e6 operations is trivial.

    Wait: But we must be careful: reading input as strings and processing.

    The algorithm:

    1. Read n,m.
    2. Initialize matrix as list of strings or list of lists of ints.
    3. Compute colCount array of length m, initially zeros. For each row i: For each column j: if a[i][j] == '1': colCount[j] += 1.
    4. For each row i: flag = True For each column j: if a[i][j] == '1' and colCount[j] == 1: flag = False; break If flag == True: print("YES") and exit.
    5. If no row passes, print("NO").

    That's it.

    But is there any nuance? The problem statement says: "Switches change state only from 'off' to 'on'. It means that if you press two or more switches connected to the same lamp then the lamp will be turned on after any of this switches is pressed and will remain its state even if any switch connected to this lamp is pressed afterwards." This is just standard: pressing a switch turns on its lamps if they are off; once on, they stay on. So the order doesn't matter; final state is the OR of all pressed switches. So condition indeed is that each lamp is covered by at least one pressed switch.

    Thus our solution holds.

    Check examples:

    Example 1: 4 5 10101 01000 00111 10000

    Compute colCounts: col0: row0=1, row2? row2 is 00111 -> col0=0, row3=1 => total 2? Actually row0 col0=1, row1 col0=0, row2 col0=0, row3 col0=1 -> col0 count=2 col1: row0=0, row1=1, row2=0, row3=0 -> count=1 col2: row0=1, row1=0, row2=1, row3=0 -> count=2 col3: row0=0, row1=0, row2=1, row3=0 -> count=1 col4: row0=1, row1=0, row2=1, row3=0 -> count=2

    Now check rows: Row0: ones at col0, col2, col4. col0 count=2, col2=2, col4=2 => all >=2 => GOOD -> YES.

    Thus output YES.

    Example 2: 4 5 10100 01000 00110 00101

    Compute colCounts: col0: row0=1, row1=0, row2=0, row3=0 =>1 col1: row0=0, row1=1, row2=0, row3=0 =>1 col2: row0=1, row1=0, row2=1, row3=1 =>3 (actually row0=1, row2=1, row3=1 =>3) col3: row0=0, row1=0, row2=1, row3=0 =>1 col4: row0=0, row1=0, row2=0, row3=1 =>1

    Now rows: Row0: ones at col0 (count=1) -> fails. Row1: ones at col1 (count=1) -> fails. Row2: ones at col2 (count=3) and col3 (count=1) -> col3 count=1 => fails. Row3: ones at col2 (3) and col4 (1) -> col4 count=1 => fails. Thus NO.

    Matches.

    So simple solution works.

    But wait: Constraints n,m ≤ 2000, but can we have input size up to 4e6? That's fine. However, need to be careful with Python's input reading speed. Use sys.stdin.read() or sys.stdin.buffer.

    We can store rows as strings; no need to convert to ints, just compare characters.

    Implementation steps:

    import sys

    def main(): data = sys.stdin.read().split() # first two are n,m it = iter(data) n = int(next(it)) m = int(next(it)) rows = [] for _ in range(n): rows.append(next(it).strip()) # each row is a string of length m colCount = [0]*m for row in rows: for j,ch in enumerate(row): if ch == '1': colCount[j] += 1 # Check each row for row in rows: ok = True for j,ch in enumerate(row): if ch == '1' and colCount[j] == 1: ok = False break if ok: print("YES") return print("NO")

    if name == "main": main()

    That should work.

    But is there any trick? Guarantee that if all switches are pressed all lamps are on, i.e., each column has at least one 1. So colCount[j] >= 1.

    Edge cases: n=1,m=1. Only one switch. Then colCount[0]=1. The only row: it has a '1' at col0 and colCount=1 => not ok => NO. But is it correct? If we ignore the only switch, we press 0 switches, then lamp is off, so not all on. So answer should be NO. Good.

    n=2,m=1. Suppose rows: '1' and '1'. colCount[0]=2. Row0: has 1 and colCount=2 -> ok => YES. Indeed ignoring one switch, the other still turns on lamp. Works.

    n=2,m=2. rows: '10', '01'. colCount: col0=1, col1=1. Row0: ones at col0 (count=1) -> fail. Row1: ones at col1 (count=1) -> fail. So NO. Indeed each lamp has only one switch; ignore one, one lamp stays off.

    Now, complexity O(n*m). Acceptable.

    But wait: The problem statement says "n switches and m lamps. The i-th switch turns on some subset of the lamps. This information is given as the matrix a consisting of n rows and m columns where ai, j = 1 if the i-th switch turns on the j-th lamp and ai, j = 0 if the i-th switch is not connected to the j-th lamp. Initially all m lamps are turned off. Switches change state only from "off" to "on". It means that if you press two or more switches connected to the same lamp then the lamp will be turned on after any of this switches is pressed and will remain its state even if any switch connected to this lamp is pressed afterwards. It is guaranteed that if you push all n switches then all m lamps will be turned on. Your think that you have too many switches and you would like to ignore one of them. Your task is to say if there exists such a switch that if you will ignore (not use) it but press all the other n - 1 switches then all the m lamps will be turned on."

    All fine.

    Thus answer is simple.

    But sometimes there is a more tricky interpretation: Could it be that pressing switches in some order matters? No, it's OR.

    So solution stands.

    Now, what about large constraints? 2000*2000 = 4e6, reading and processing with Python is fine.

    But maybe we can optimize memory: we don't need to store rows; we could process line by line: compute colCount first pass, but we also need to check each row later, so we need to store the rows. That's up to 4e6 characters, which is about 4 MB, fine.

    Alternative: we could store rows as list of strings.

    Edge Cases: Input lines might have no spaces between characters; using .split() will treat each line as a token because they are separated by newlines. That's fine.

    One more nuance: The input might have extra spaces? Usually not.

    Thus final solution is straightforward.

    Now, let's double-check logic: Could there be a scenario where a switch is not uniquely covering any lamp, but still some lamp might not be turned on because of the order? For example, if a lamp is connected to multiple switches, but pressing some switches might turn it on, but later pressing another switch might turn it off? The problem says switches change state only from off to on, so no turning off. So it's monotonic. So OR is correct.

    Therefore answer stands.

    Thus solution as above.

    Now, consider if there is a switch that covers no lamps at all (all zeros). Then colCount for any column is not increased by that row. For that row, it has no ones, so condition vacuously holds (since for every column where it has a 1, that set is empty, so trivially all those columns have count >=2). So such a switch could be ignored because it contributes nothing. But does the problem allow such a switch? Possibly yes. But is it guaranteed that if you press all switches, all lamps are on? If a switch has no connections, it doesn't affect the coverage; but the guarantee only says that with all switches pressed, all lamps are on. It doesn't require each switch to have at least one lamp. So a zero row is possible. Then if there is a zero row, then ignoring it leaves all other switches unchanged; since all lamps were covered by other switches (since all switches include this zero row, but its removal doesn't affect coverage). So it should be YES. Our algorithm would consider that row: it has no ones, so it will pass the check (since loop over j with ch=='1' finds none, ok remains True). So YES. Good.

    Therefore solution is correct.

    Now test some random small cases manually:

    n=3,m=2 Row0: 11 Row1: 10 Row2: 01 colCount: col0: row0+row1 =2; col1: row0+row2=2. Check rows: Row0: ones at col0 (2) and col1 (2) => ok => YES. Indeed ignoring row0, we still have row1 and row2 covering both lamps. Yes. Row1: ones at col0 (2) => col0 count=2 => ok? Wait row1 has only col0. col0 count=2 => ok. Row1 is also ignorable? If we ignore row1, we have row0 and row2. Row0 covers both, so all lamps are on. So row1 also ok. Our algorithm would find row0 first but row1 also ok. So YES. Good. Row2: similarly ok.

    Now if we had: n=3,m=2 Row0: 10 Row1: 10 Row2: 01 colCount: col0:2, col1:1. Rows: Row0: ones at col0 (2) => ok. Row1: same ok. Row2: ones at col1 (1) => not ok. Thus there is a switch (0 or 1) that can be ignored, answer YES.

    If all rows have at least one unique column, answer might still be YES if some row doesn't. For example, n=3,m=3: Row0: 100 Row1: 010 Row2: 111 colCount: col0: row0+row2=2; col1: row1+row2=2; col2: row2=1. Rows: Row0: ones at col0 (2) => ok. Row1: ones at col1 (2) => ok. Row2: ones at col0, col1, col2. col2 count=1 => not ok. So YES.

    If there is no row with the property, answer NO.

    Now consider pathological case: n=2000,m=2000 all ones. Then colCount each =2000. All rows are all ones, each row passes because all columns have count>=2. So answer YES.

    If each column has exactly one 1, i.e., each lamp is covered by exactly one switch, then each row may cover some columns. For any row, any column it covers has count=1, so it fails. So answer NO.

    Thus solution works.

    Now, we might need to consider time: scanning each row twice: first for colCount, second for checking rows. That's two passes through the matrix. With 4 million chars, it's fine.

    Alternatively, we could compute colCount and simultaneously store rows. That's fine.

    Now, edge: m up to 2000, n up to 2000, product up to 4e6, but Python strings of length 2000 are fine.

    One more nuance: The input lines might have no newline at the end, but .split() handles that.

    I think it's done.

    But wait: The problem statement might be from Codeforces? I've seen a similar problem "Switches and Lamps". Actually it's Codeforces Round 225 Div2? I recall something like that. The solution is as described.

    Double-check: There is also a possibility to solve using bitset, but not necessary.

    Thus final answer: just implement as above.

    Potential pitfalls: We must ensure that we treat each character correctly, not as integer but as string '1'. Good.

    Now confirm the sample inputs: Works.

    So final code:

    import sys

    def solve(): import sys data = sys.stdin.buffer.read().split() if not data: return it = iter(data) n = int(next(it)) m = int(next(it)) rows = [next(it).decode() for _ in range(n)] col_cnt = [0]*m for row in rows: for j,ch in enumerate(row): if ch == '1': col_cnt[j] += 1 for row in rows: ok = True for j,ch in enumerate(row): if ch == '1' and col_cnt[j] == 1: ok = False break if ok: print("YES") return print("NO")

    if name == "main": solve()

    We could use .decode() because sys.stdin.buffer.read().split() returns bytes. Or we can use sys.stdin.read().split() which returns strings. Both fine.

    Better to use sys.stdin.buffer.read().split() for speed. Then we need to decode each row bytes to str. Alternatively, we can treat bytes: we can compare ch == 49 (ord('1')), but easier to decode.

    Since n,m <=2000, performance not an issue.

    Now, there is one more nuance: The matrix entries are characters without spaces; using split() will treat each line as one token; good.

    But what if there are spaces in the lines? No.

    Alright.

    Thus answer.

    But before finalizing, we should consider the possibility that the input may be read incorrectly if the lines have trailing spaces. split() will remove whitespace, so it's fine.

    Now, we might also consider that we can avoid storing all rows by reading them twice? But that's not necessary.

    Now, let's double-check edge case: n=2000,m=2000, all ones. colCount each 2000. For each row, checking 2000 columns, and all passes because none has count 1. The algorithm would find first row and output YES. So fine.

    Thus final solution is correct.

    Now, I'll produce the final answer as code and explanation.

    But the user asked: "You are given n switches and m lamps... Your task is to say if there exists such a switch... Print "YES" if there is...". So we just need to output answer.

    Thus in the final answer, I'll provide the solution with explanation and code.

    Now note: In competitive programming, sometimes there is a more efficient solution using prefix sums, but not needed.

    Now, I recall that a similar problem might be solved by checking if there exists a row such that for every column where it's 1, the column sum >1. This is exactly what we did.

    Thus final.

    Now, one more check: Could there be a scenario where a lamp is turned on by multiple switches, but due to ordering some lamp might not be turned on if we ignore a switch? No, because pressing all remaining switches will turn on all lamps that are connected to at least one of them. So it's just OR.

    So done.

    Thus answer.

    But let me think about potential pitfalls: The problem statement says: "Switches change state only from 'off' to 'on'. It means that if you press two or more switches connected to the same lamp then the lamp will be turned on after any of this switches is pressed and will remain its state even if any switch connected to this lamp is pressed afterwards." This clarifies that pressing a switch does not toggle, it only turns on (if off). So final state is OR of all pressed switches.

    All good.

    Thus final code as above.

    Now I'll write the answer. We can ignore a switch if after removing it, each lamp is still turned on by at least one of the remaining switches.
    That is equivalent to: there exists a switch that is not the only switch controlling any lamp it influences.
    In other words, for some row i, for every column j where a[i][j] = 1, the total number of 1s in column j is at least 2.

    Therefore we can:

    1. Count for each lamp (column) how many switches turn it on (colCount[j]).
    2. For every switch (row), check whether it has a 1 in a column with colCount == 1.
      • If such a column exists, the switch is essential for that lamp and cannot be ignored.
      • Otherwise, the switch can be ignored.

    If at least one row passes the test, answer YES; otherwise NO.

    The algorithm runs in O(n·m) time and O(m) extra space (plus storing the matrix), which is efficient for n,m ≤ 2000.

    import sys
    
    def solve() -> None:
        data = sys.stdin.buffer.read().split()
        if not data:
            return
        it = iter(data)
        n = int(next(it))
        m = int(next(it))
    
        rows = [next(it).decode() for _ in range(n)]
    
        # count ones in each column
        col_cnt = [0] * m
        for row in rows:
            for j, ch in enumerate(row):
                if ch == '1':
                    col_cnt[j] += 1
    
        # find a row that is not the unique one in any of its columns
        for row in rows:
            ok = True
            for j, ch in enumerate(row):
                if ch == '1' and col_cnt[j] == 1:
                    ok = False
                    break
            if ok:
                print("YES")
                return
    
        print("NO")
    
    if __name__ == "__main__":
        solve()