B. Batch Sort

Codeforces

IDCF724B

Time2000ms

Memory256MB

Difficulty—

brute forcegreedyimplementationmath

English · Original

Chinese · Translation

Formal · Original

You are given a table consisting of _n_ rows and _m_ columns. Numbers in each row form a permutation of integers from 1 to _m_. You are allowed to pick two elements in one row and swap them, but **no more than once** for each row. Also, **no more than once** you are allowed to pick two columns and swap them. Thus, you are allowed to perform from 0 to _n_ + 1 actions in total. **Operations can be performed in any order**. You have to check whether it's possible to obtain the identity permutation 1, 2, ..., _m_ in each row. In other words, check if one can perform some of the operation following the given rules and make each row sorted in increasing order. ## Input The first line of the input contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 20) — the number of rows and the number of columns in the given table. Each of next _n_ lines contains _m_ integers — elements of the table. It's guaranteed that numbers in each line form a permutation of integers from 1 to _m_. ## Output If there is a way to obtain the identity permutation in each row by following the given rules, print "_YES_" (without quotes) in the only line of the output. Otherwise, print "_NO_" (without quotes). [samples] ## Note In the first sample, one can act in the following way: 1. Swap second and third columns. Now the table is<center>1 2 3 4</center><center>1 4 3 2</center> 2. In the second row, swap the second and the fourth elements. Now the table is<center>1 2 3 4</center><center>1 2 3 4</center>

给定一个包含 #cf_span[n] 行和 #cf_span[m] 列的表格。每行中的数字构成从 #cf_span[1] 到 #cf_span[m] 的一个排列。你可以选择某一行中的两个元素进行交换，但每行最多只能交换一次。此外，你最多只能进行一次列交换操作，即选择两列并交换它们。因此，你总共可以执行从 #cf_span[0] 到 #cf_span[n + 1] 次操作。*操作的顺序可以任意*。你需要判断是否可能使每一行都变为恒等排列 #cf_span[1, 2, ..., m]。换句话说，判断是否能在遵循上述规则的前提下，使每一行都按递增顺序排列。输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 20]）— 表格的行数和列数。接下来的 #cf_span[n] 行每行包含 #cf_span[m] 个整数 — 表格的元素。保证每行中的数字构成从 #cf_span[1] 到 #cf_span[m] 的一个排列。如果可以通过遵循给定规则使每一行都变为恒等排列，则在输出的唯一一行中打印 "_YES_"（不含引号）；否则，打印 "_NO_"（不含引号）。在第一个样例中，可以按以下方式操作： ## Input 输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 20]）— 表格的行数和列数。接下来的 #cf_span[n] 行每行包含 #cf_span[m] 个整数 — 表格的元素。保证每行中的数字构成从 #cf_span[1] 到 #cf_span[m] 的一个排列。 ## Output 如果可以通过遵循给定规则使每一行都变为恒等排列，则在输出的唯一一行中打印 "_YES_"（不含引号）；否则，打印 "_NO_"（不含引号）。 [samples] ## Note 在第一个样例中，可以按以下方式操作：交换第二列和第三列。此时表格变为 #cf_span[1 2 3 4] 和 #cf_span[1 4 3 2]。在第二行中，交换第二个和第四个元素。此时表格变为 #cf_span[1 2 3 4] 和 #cf_span[1 2 3 4]。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n, m \leq 20 $. Let $ T = (R_1, R_2, \dots, R_n) $ be a table of $ n $ rows, where each $ R_i = (r_{i,1}, r_{i,2}, \dots, r_{i,m}) $ is a permutation of $ \{1, 2, \dots, m\} $. Let $ I = (1, 2, \dots, m) $ denote the identity permutation. **Operations** 1. **Row swap**: For any row $ R_i $, swap two elements **at most once**. 2. **Column swap**: Swap two entire columns **at most once** (applied uniformly across all rows). Operations may be performed in any order and total number of operations is between $ 0 $ and $ n + 1 $. **Objective** Determine whether there exists a sequence of allowed operations such that for all $ i \in \{1, \dots, n\} $, $ R_i = I $.

Samples

Input #1

2 4
1 3 2 4
1 3 4 2

Output #1

YES

Input #2

Output #2

NO

Input #3

3 6
2 1 3 4 5 6
1 2 4 3 5 6
1 2 3 4 6 5

Output #3

YES

API Response (JSON)

{
  "problem": {
    "name": "B. Batch Sort",
    "description": {
      "content": "You are given a table consisting of _n_ rows and _m_ columns. Numbers in each row form a permutation of integers from 1 to _m_. You are allowed to pick two elements in one row and swap them, but **n",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF724B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a table consisting of _n_ rows and _m_ columns.\n\nNumbers in each row form a permutation of integers from 1 to _m_.\n\nYou are allowed to pick two elements in one row and swap them, but **n...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个包含 #cf_span[n] 行和 #cf_span[m] 列的表格。\n\n每行中的数字构成从 #cf_span[1] 到 #cf_span[m] 的一个排列。\n\n你可以选择某一行中的两个元素进行交换，但每行最多只能交换一次。此外，你最多只能进行一次列交换操作，即选择两列并交换它们。因此，你总共可以执行从 #cf_span[0] 到 #cf_span[n + 1] 次操作。*操作的顺序可以任...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 20 $.  \nLet $ T = (R_1, R_2, \\dots, R_n) $ be a table of $ n $ rows, where each $ R_i = (r_{i,1}, r_{i,2}, \\dots, r_{i,m}) $ is ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments