410497: GYM104027 J runaway problem

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. runaway problemtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Recently, lzd has been learning two-view correspondences and geometry using order-aware network, which is a neural network that infers the probabilities of correspondences being inliers and regresses the relative pose encoded by the essential matrix. The order-aware network contains three novel operations: differentiable pooling layer(a permutation-invariant methods to cluster nodes in a learnable manner and capture the local context), order-aware differentiable unpooling layer(to upsample the coarsened feature maps and build a hierarchical architecture), and order-aware filtering block(to capture the global context with spatial connections). Since the order-aware network achieved the state-of-the-art(SOTA) performance, lzd considers it a good methods and want to share a problem, which is relevant to one of the operation mentioned above, for you to solve.

Shortly, the problem can be refined as:

You are given a matrix $$$A$$$ with the shape of $$$n\times m$$$ and a matrix $$$B$$$ with the shape of $$$m\times m$$$. You can swap the arbitrary(任意) two rows of A and you can do this operation arbitrary times(possibly, 0 times).

Now, the question is that is it possible to make $$$B=A^T\times A$$$, where the $$$A^T$$$ stands for the transpose(转置) of matrix $$$A$$$ and the "$$$\times$$$" stands for the multiplication between two matrix.

Input

The first line consists of two integers $$$n,m(1\leq n,m\leq 100)$$$, describing the shape of $$$A$$$ and $$$B$$$.

In the following $$$n$$$ lines, each line contains $$$m$$$ intergers $$$A_{i,j}(0\leq A_{i,j}\leq 10^6)$$$, denoting the matrix $$$A$$$.

In the following $$$m$$$ lines, each line contains $$$m$$$ intergers $$$B_{i,j}(0\leq B_{i,j}\leq 10^{15})$$$, denoting the matrix $$$B$$$

Output

Output a line containing a string. Output "YES"(without quotes) or "NO"(without quotes), denonting is it possible for you to make $$$B=A^T\times A$$$.

ExamplesInput
6 6
1 1 4 5 1 4
1 1 4 5 1 4
1 1 4 5 1 4
1 1 4 5 1 4
1 1 4 5 1 4
1 1 4 5 1 4
6 6 24 30 6 24
6 6 24 30 6 24
24 24 96 120 24 96
30 30 120 150 30 120
6 6 24 30 6 24
24 24 96 120 24 96
Output
YES
Input
1 4
1 2 3 4
1 2 3 114514
2 4 6 8
3 6 9 12
4 8 12 16
Output
NO

加入题单

上一题 下一题 算法标签: