Overview

This problem asks us to determine whether multiple memos, each with exactly one missing value (-1), all represent the same password.

Analysis

For all memos to represent the same password \(P\), the values in each column (each digit of the password) must be consistent across all memos. However, -1 (missing values) can be any value, so they can be ignored.

The key observation is that if two or more distinct non-(-1) values exist in the same column, it is impossible for those memos to represent the same password. This is because non-(-1) values are fixed as correct values, so if they differ, a contradiction arises.

Conversely, if for each column all non-(-1) values are the same, or if no non-(-1) values exist (i.e., all memos have -1 in that column), then we can construct a single password \(P\) without contradiction.

Algorithm

1. Read the input data and store the \(N\) memos as a two-dimensional list
2. For each column (\(j = 0\) to \(M-1\)), examine the values of that column across all memos
3. For each column:
   • If non-(-1) values exist, use the first non-(-1) value as the reference value
   • Compare other non-(-1) values in that column with the reference value; if any differ, output “No” and terminate
4. If no contradictions are found across all columns, output “Yes”

Complexity

• Time complexity: \(O(N \times M)\)
• Space complexity: \(O(N \times M)\)

Since the problem constraints guarantee \(N \times M \leq 2 \times 10^5\), this algorithm is sufficiently efficient.

Implementation Notes

• Efficiency is improved by reading all input data at once

• Instead of aggregating values for each column, we reduce memory usage by directly comparing values while scanning through the memos

• Early return: As soon as a contradiction is found, we immediately output “No” and terminate

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print("No")
        return
        
    n = int(data[0])
    m = int(data[1])
    index = 2
    memos = []
    for i in range(n):
        row = list(map(int, data[index:index+m]))
        index += m
        memos.append(row)
    
    # 各列ごとの値（-1以外）を保存するリスト
    columns = [[] for _ in range(m)]
    
    for i in range(n):
        for j in range(m):
            val = memos[i][j]
            if val != -1:
                columns[j].append(val)
                
    # 各列をチェック：同じ列に異なる値が2つ以上あればNo
    for j in range(m):
        if len(columns[j]) == 0:
            continue
        first_val = columns[j][0]
        for val in columns[j]:
            if val != first_val:
                print("No")
                return
                
    print("Yes")

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.