Overview

This is a problem where we need to determine whether the notes of \(N\) people (each with exactly one position missing as \(-1\)) could all be records of the same password. For each position, we simply need to check whether all non-\(-1\) values are identical.

Analysis

Key Insight

Let the password be \(P = (P_1, P_2, \ldots, P_M)\). For each note \(i\), if \(S_{i,j} \neq -1\), then \(S_{i,j} = P_j\) must hold.

In other words, for a given position \(j\), if non-\(-1\) values exist in multiple notes, they must all be the same value.

Let’s consider a concrete example. Suppose \(M = 3\) and we have the following two notes:

• Note 1: 3 -1 5
• Note 2: -1 7 5

Looking at position 1: Note 1 has \(3\), Note 2 has \(-1\) (unknown) → No contradiction (\(P_1 = 3\)) Looking at position 2: Note 1 has \(-1\) (unknown), Note 2 has \(7\) → No contradiction (\(P_2 = 7\)) Looking at position 3: Note 1 has \(5\), Note 2 has \(5\) → They match, so no contradiction (\(P_3 = 5\))

Therefore the answer is Yes.

If position 3 of Note 2 were \(9\), then at position 3, Note 1’s \(5\) and Note 2’s \(9\) would contradict, so the answer would be No.

Why This Is Sufficient

Since any value from \(0\) to \(10^9\) can be placed at a \(-1\) position, only the non-\(-1\) positions create constraints. If all non-\(-1\) values are consistent at each position, we can construct the password \(P\). If some position has \(-1\) in all notes, we can choose any value (for example, \(0\)).

Algorithm

1. For each position \(j\) (\(1 \leq j \leq M\)), check \(S_{i,j}\) across all notes.
2. Collect the values where \(S_{i,j} \neq -1\) and determine whether they are all the same value.
3. If there is even one contradicting position, output No; if all positions have no contradictions, output Yes.

Specifically, for each position \(j\), record the “first non-\(-1\) value found” (decided[j]), and verify that subsequent non-\(-1\) values match it.

Complexity

• Time complexity: \(O(N \times M)\)
  • We only scan through all elements of all notes once. Since \(N \times M \leq 2 \times 10^5\) by the constraints, this is fast enough.
• Space complexity: \(O(N \times M)\)
  • We need arrays to store all the notes and the determined value for each position.

Implementation Notes

• Initialize the array decided with None, and for each position, record the first non-\(-1\) value that appears. If a subsequent non-\(-1\) value differs, we can immediately output No and terminate.

• By using sys.stdin.buffer.read() to read all input at once, we can process efficiently even in Python.

• The condition “exactly one position is \(-1\)” does not affect the decision logic itself. Regardless of which position is \(-1\), it is sufficient to only check the consistency of non-\(-1\) values.

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    # For each position j, collect all non-(-1) values
    # We need to check that for each position, all non-(-1) values agree
    # Also, each memo has exactly one -1
    
    # Store memos
    memos = []
    for i in range(N):
        row = []
        for j in range(M):
            row.append(int(input_data[idx])); idx += 1
        memos.append(row)
    
    # For each position j, find the "decided" value (if any)
    # All non-(-1) values at position j must be the same
    decided = [None] * M  # None means no constraint yet
    
    for i in range(N):
        for j in range(M):
            v = memos[i][j]
            if v != -1:
                if decided[j] is None:
                    decided[j] = v
                elif decided[j] != v:
                    print("No")
                    return
    
    # Now, decided[j] is either None (no non-(-1) value seen) or a specific value
    # For positions where decided[j] is None, we can choose any value in [0, 10^9]
    # 
    # But we also need to verify: the decided values are all in [0, 10^9]
    # Since input guarantees S_{i,j} in [0, 10^9] when not -1, this is automatic.
    # For None positions, we just pick 0 (any valid value works).
    
    print("Yes")

main()

---

This editorial was generated by claude4.6opus-thinking.