[Solution] Angled Flip solution codechef

Angled Flip solution codechef – You are given two N \times M integer matrices A and B. You are allowed to perform the following operation on A as many times as you like (possibly, zero):

Table of Contents

[Solution] Angled Flip solution codechef

For example, suppose you choose the submatrix \begin{bmatrix} 1 \;\;\;\; 2 \;\;\;\; 3 \\ 4 \;\;\;\; 5 \;\;\;\; 6 \\ 7 \;\;\;\; 8 \;\;\;\; 9 \end{bmatrix} .

It can be converted into either \begin{bmatrix} 1 \;\;\;\; 4 \;\;\;\; 7 \\ 2 \;\;\;\; 5 \;\;\;\; 8 \\ 3 \;\;\;\; 6 \;\;\;\; 9 \end{bmatrix} by flipping about the main diagonal, or \begin{bmatrix} 9 \;\;\;\; 6 \;\;\;\; 3 \\ 8 \;\;\;\; 5 \;\;\;\; 2 \\ 7 \;\;\;\; 4 \;\;\;\; 1 \end{bmatrix} by flipping about the antidiagonal.

Is it possible to convert A to B by performing this operation several (possibly, zero) times?

Note: For the purposes of this problem, a submatrix of a matrix is the intersection of a contiguous segment of rows with a contiguous segment of columns.

For example, if A = \begin{bmatrix} 1 \;\;\;\; 2 \;\;\;\; 3 \\ 4 \;\;\;\; 5 \;\;\;\; 6 \\ 7 \;\;\;\; 8 \;\;\;\; 9 \end{bmatrix} then \begin{bmatrix} 2 \end{bmatrix}\begin{bmatrix} 5 \;\;\;\; 6 \\ 8 \;\;\;\; 9 \end{bmatrix}, and \begin{bmatrix}1 \\ 4\end{bmatrix} are submatrices of A, while \begin{bmatrix}1 \;\;\;\; 3 \\ 7 \;\;\;\; 9\end{bmatrix} is not.

A square submatrix is a submatrix with the same number of rows and columns.

Angled Flip solution codechef

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains two space-separated integers N and M — the number of rows and columns of the matrices, respectively.
    • The next N lines describe the matrix A. The i-th of these lines contains M space-separated integers ― the values A_{i, 1}, A_{i, 2}, \ldots, A_{i, M}.
    • The next N lines describe the matrix B. The i-th of these lines contains M space-separated integers ― the values B_{i, 1}, B_{i, 2}, \ldots, B_{i, M}.

Output Format

For each test case, print YES if its possible to convert A to B, else print NO.

Each character of the output may be printed in either uppercase or lowercase. For example, the strings YESyesyeSYeS will all be treated as identical.

Constraints

  • 1 \leq T \leq 10^4
  • 1 \leq N,M \leq 3 \cdot 10^5
  • 1 \leq A_{i, j},B_{i, j} \leq 10^9
  • The sum of N\cdot M over all test cases won’t exceed 3 \cdot 10^5.

Sample 1:

Input

Output

2
2 3
1 2 3
4 5 6
1 4 3
6 5 2
3 3
12 11 8
7 1 1
9 2 4
4 1 8
2 1 11
9 7 12
YES
YES

Angled Flip solution codechef Explanation:

Test case 1: A can be converted to B as follows:

\begin{bmatrix} 1 \;\;\;\; 2 \;\;\;\; 3 \\ 4 \;\;\;\; 5 \;\;\;\; 6 \end{bmatrix} \to \begin{bmatrix} 1 \;\;\;\; \textcolor{red}{6} \;\;\;\; \textcolor{red}{3} \\ 4 \;\;\;\; \textcolor{red}{5} \;\;\;\; \textcolor{red}{2} \end{bmatrix} \to \begin{bmatrix} \textcolor{red}{1} \;\;\;\; \textcolor{red}{4} \;\;\;\; 3 \\ \textcolor{red}{6} \;\;\;\; \textcolor{red}{5} \;\;\;\; 2 \end{bmatrix}

For Solution

“Click Here”

Leave a Comment