Overview

This is a problem where we determine whether the “readable values (those not equal to \(-1\))” in each memo can be consistently matched at corresponding positions. Ultimately, it suffices to check whether “for each column (each position), all values that are not \(-1\) are the same.”

Analysis

Each memo contains exactly one \(-1\), and the position with \(-1\) can be filled in with any value later. Therefore, the condition for a password \(P\) to exist is as follows:

• When looking at each position \(j\), if there are any values written that are not \(-1\), they must all be the same.

If for the same column \(j\): - One memo has \(S_{i,j}=5\) - Another memo has \(S_{k,j}=7\)

and different values appear like this, then no matter what \(P_j\) we choose, we cannot satisfy both, so it is impossible.

Conversely, if no contradiction ever occurs in any column, then: - If at least one value is written in that column, adopt that value as \(P_j\) - If the column contains only \(-1\) values, \(P_j\) can be anything (e.g., \(0\))

By doing this, we can construct a \(P\) that is consistent with all memos, so it is possible.

A naive approach of “constructing a password candidate \(P\) and checking it against all rows” also works, but the key insight is that we only need to look at the constraints column by column (in this problem, since \(N \times M \le 2\times 10^5\), a solution that examines all elements once is optimal).

Algorithm

1. Prepare an array col of length \(M\) to manage the “determined value” for each column. Initialize all to undetermined (None).
2. Read all elements \(S_{i,j}\).
   • If \(S_{i,j}=-1\), there is no constraint, so ignore it.
   • If \(S_{i,j}\neq -1\):
     • If col[j] is undetermined, set col[j]=S_{i,j} to fix the value for that column.
     • If col[j] is already determined and a different value appears, there is a contradiction, so output No.
3. If no contradiction is found by the end, output Yes.

Concrete examples: - If a column looks like [3, -1, 3, 3], we can set \(P_j=3\) - If a column looks like [3, -1, 4], then 3 and 4 conflict, so it is impossible (No)

Complexity

• Time complexity: \(O(NM)\) (checking each element once)
• Space complexity: \(O(M)\) (storing the determined value for each column)

Implementation Notes

• Managing col[j] with two states — “undetermined (None) / determined value” — allows for concise code.

• The constraint is \(N \times M \le 2\times 10^5\), but in Python, input can easily become a bottleneck, so it is safe to use sys.stdin.buffer.read() for fast reading as shown in the code.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    M = int(next(it))

    col = [None] * M

    for _ in range(N):
        for j in range(M):
            x = int(next(it))
            if x == -1:
                continue
            v = col[j]
            if v is None:
                col[j] = x
            elif v != x:
                print("No")
                return

    print("Yes")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.