C - Matrix Reducing Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

H_1 行 W_1 列の行列 A と、H_2 行 W_2 列の行列 B が与えられます。

  • 1 \leq i \leq H_1 かつ 1 \leq j \leq W_1 を満たす整数の組 (i, j) について、行列 A の i 行目 j 列目の要素は A_{i, j} です。
  • 1 \leq i \leq H_2 かつ 1 \leq j \leq W_2 を満たす整数の組 (i, j) について、行列 B の i 行目 j 列目の要素は B_{i, j} です。

行列 A に対して、下記の 2 つの操作のうちどちらかを行うことを、好きなだけ（ 0 回でも良い）繰り返すことができます。

  • A の行を任意に 1 つ選んで削除する。
  • A の列を任意に 1 つ選んで削除する。

行列 A を行列 B に一致させることができるかどうかを判定して下さい。

制約

  • 1 \leq H_2 \leq H_1 \leq 10
  • 1 \leq W_2 \leq W_1 \leq 10
  • 1 \leq A_{i, j} \leq 10^9
  • 1 \leq B_{i, j} \leq 10^9
  • 入力中の値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}

出力

行列 A を行列 B に一致させることができる場合は Yes を、 一致させることができない場合は No を出力せよ。 ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入力例 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

出力例 1

Yes

初期状態の行列 A から 2 列目を削除すると、行列 A は

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

となります。そこからさらに 3 行目を削除すると、行列 A は

1 3 4 5
6 8 9 10
16 18 19 20

となります。そこからさらに 1 行目を削除すると、行列 A は

6 8 9 10
16 18 19 20

となります。そこからさらに 4 列目を削除すると、行列 A は

6 8 9
16 18 19

となります。これは行列 B と一致します。 操作の繰り返しによって行列 A を行列 B に一致させることができるので Yes を出力します。

入力例 2

3 3
1 1 1
1 1 1
1 1 1
1 1
2

出力例 2

No

どのように操作を行っても、 行列 A を行列 B に一致させることはできません。 よって、No を出力します。

Score : 300 points

Problem Statement

You are given a matrix A with H_1 rows and W_1 columns, and a matrix B with H_2 rows and W_2 columns.

  • For all integer pairs (i, j) such that 1 \leq i \leq H_1 and 1 \leq j \leq W_1, the element at the i-th row and j-th column of matrix A is A_{i, j}.
  • For all integer pairs (i, j) such that 1 \leq i \leq H_2 and 1 \leq j \leq W_2, the element at the i-th row and j-th column of matrix B is B_{i, j}.

You may perform the following operations on the matrix A any number of (possibly 0) times in any order:

  • Choose an arbitrary row of A and remove it.
  • Choose an arbitrary column of A and remove it.

Determine if it is possible to make the matrix A equal the matrix B.

Constraints

  • 1 \leq H_2 \leq H_1 \leq 10
  • 1 \leq W_2 \leq W_1 \leq 10
  • 1 \leq A_{i, j} \leq 10^9
  • 1 \leq B_{i, j} \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}

Output

Print Yes if it is possible to make the matrix A equal the matrix B; print No otherwise. Note that the judge is case-sensitive.

Sample Input 1

4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
2 3
6 8 9
16 18 19

Sample Output 1

Yes

Removing the 2-nd column from the initial A results in:

1 3 4 5
6 8 9 10
11 13 14 15
16 18 19 20

Then, removing the 3-rd row from A results in:

1 3 4 5
6 8 9 10
16 18 19 20

Then, removing the 1-st row from A results in:

6 8 9 10
16 18 19 20

Then, removing the 4-th column from A results in:

6 8 9
16 18 19

Now the matrix equals the matrix B.
Thus, we can make the matrix A equal the matrix B by repeating the operations, so Yes should be printed.

Sample Input 2

3 3
1 1 1
1 1 1
1 1 1
1 1
2

Sample Output 2

No

Regardless of how we perform the operations, we cannot make the matrix A equal the matrix B, so No should be printed.