Overview

Given a seating chart, find “unique seats” where the same class name does not appear elsewhere in the same row or column, and output the concatenation of those class names in order from top-left to bottom-right.

Analysis

For each seat, we need to check whether there is another seat with the same class name in its row or column. A naive approach would be, for each seat \((i, j)\), to scan the entire row \(i\) and column \(j\) to check for the existence of the same class name. However, this results in a time complexity of \(O(HW \times (H + W))\). With a maximum of \(1000 \times 1000 = 10^6\) seats and checking each row/column (up to 1000 elements each), this requires \(10^6 \times 2000 = 2 \times 10^9\) operations, which will not fit within the time limit.

Instead, by precomputing the occurrence count of each class name for every row and every column, we can perform the check for each seat in constant time.

Algorithm

1. Preprocessing: Count the occurrences of each class name for every row and every column
   • row_counts[i]: A dictionary storing the occurrence count of each class name in row \(i\)
   • col_counts[j]: A dictionary storing the occurrence count of each class name in column \(j\)
2. Main processing: For each seat \((i, j)\), check the following conditions:
   • The occurrence count of class name \(G_{i,j}\) in row \(i\) is 1
   • The occurrence count of class name \(G_{i,j}\) in column \(j\) is 1
3. Output: Concatenate the class names of seats satisfying the conditions in order from top-left to bottom-right and output the result

Complexity

• Time complexity: \(O(HW)\)
  • Preprocessing to count each row/column: \(O(HW)\)
  • Main processing to check each seat: \(O(HW)\)
• Space complexity: \(O(HW)\)
  • Storing the grid: \(O(HW)\)
  • Data structures for row and column counts: \(O(HW)\) (total size of dictionaries for all rows and columns)

Implementation Notes

• Use a list of dictionaries for the row and column counts

  • row_counts is a list of length \(H\), where each element is the dictionary for row \(i\)
  • col_counts is a list of length \(W\), where each element is the dictionary for column \(j\)

• Perform the counting in a single double loop for efficient processing

• Append the class names of seats satisfying the conditions to a list, then concatenate and output at the end

  Source Code

import sys

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        return
    
    H, W = map(int, data[0].split())
    grid = []
    for i in range(1, 1 + H):
        grid.append(data[i].strip())
    
    row_counts = [{} for _ in range(H)]
    col_counts = [{} for _ in range(W)]
    
    for i in range(H):
        for j in range(W):
            c = grid[i][j]
            if c in row_counts[i]:
                row_counts[i][c] += 1
            else:
                row_counts[i][c] = 1
                
            if c in col_counts[j]:
                col_counts[j][c] += 1
            else:
                col_counts[j][c] = 1
                
    result = []
    for i in range(H):
        for j in range(W):
            c = grid[i][j]
            if row_counts[i][c] == 1 and col_counts[j][c] == 1:
                result.append(c)
                
    print(''.join(result))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.