F. Matrix

Codeforces

IDCF10074F

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

You're given a matrix with n rows and n columns. A basic property of a square matrix is the main diagonal: all cells that have the same row and column number. We consider all diagonals that are parallel to the main one. We consider them from left-low corner to the right-upper one. So, the first cell of each diagonal will be, in order: (n, 1) (n - 1, 1) ... (1, 1) (1, 2) ... (1, n). You need to choose one number from each diagonal. More, all 2*n-1 numbers must be pairwise distinct. The first line contains number n (1 ≤ n ≤ 300). Next n lines contain n numbers, representing the elements of the matrix. All elements of the matrix are between 1 and 109. If there is no solution, output "NO". Otherwise, output "YES". Next, on the same line, output 2n-1 numbers, separated by spaces. Each number represents the chosen value from a diagonal. Diagonals are considered in the order given by the problem. ## Input The first line contains number n (1 ≤ n ≤ 300). Next n lines contain n numbers, representing the elements of the matrix. All elements of the matrix are between 1 and 109. ## Output If there is no solution, output "NO". Otherwise, output "YES". Next, on the same line, output 2n-1 numbers, separated by spaces. Each number represents the chosen value from a diagonal. Diagonals are considered in the order given by the problem. [samples]

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 300 $. Let $ A = (a_{i,j}) \in \mathbb{Z}^{n \times n} $ be an $ n \times n $ matrix with $ 1 \leq a_{i,j} \leq 10^9 $. For $ k \in \{1, 2, \dots, 2n-1\} $, define the $ k $-th diagonal $ D_k $ as the set of cells $ (i,j) $ such that $ i + j = k + 1 $, ordered by increasing row index (i.e., from bottom-left to top-right). Equivalently, $ D_k = \{ (i, k+1-i) \mid \max(1, k+1-n) \leq i \leq \min(n, k) \} $. **Constraints** 1. For each diagonal $ D_k $, exactly one element $ a_{i,j} \in D_k $ is selected. 2. The selected elements $ \{ x_1, x_2, \dots, x_{2n-1} \} $ must be pairwise distinct: $ x_k \ne x_{k'} $ for all $ k \ne k' $. **Objective** Determine if there exists a selection $ x_k \in D_k $ for each $ k \in \{1, \dots, 2n-1\} $ such that all $ x_k $ are distinct. If yes, output "YES" followed by $ x_1, x_2, \dots, x_{2n-1} $. If no, output "NO".

API Response (JSON)

{
  "problem": {
    "name": "F. Matrix",
    "description": {
      "content": "You're given a matrix with n rows and n columns. A basic property of a square matrix is the main diagonal: all cells that have the same row and column number. We consider all diagonals that are paral",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10074F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You're given a matrix with n rows and n columns. A basic property of a square matrix is the main diagonal: all cells that have the same row and column number.\n\nWe consider all diagonals that are paral...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 300 $.  \nLet $ A = (a_{i,j}) \\in \\mathbb{Z}^{n \\times n} $ be an $ n \\times n $ matrix with $ 1 \\leq a_{i,j} \\leq 10^9 $.  \n\nFor $ k \\in \\{1...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments