Lincoln's Lab

Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 512M

Problem type

Lincoln has damanged their laboratory after a series of interesting experiments. We describe Lincoln's lab as an \(n \times n\) grid of integers. Lincoln may have to re-build part of the lab but they also don't want to spend money unless they absolutely must. The lab is still okay if every number not equal to \(1\) can be expressed as a sum of numbers in the same row and a number in the same column.

I.e. In a good lab, for every \(x,y 1\leq x,y\leq n\) and \(a_{x,y} \neq 1\) there exists two indicies \(s\) and \(t\) such that \(a_{x,y} = a_{x,s} + a_{t,y}\)

Help Lincoln work out if their lab is still okay!

Input Specification

The first line contains an integer \(n (1\leq n \leq 50)\) the side-length of the lab.

The next \(n\) lines contain \(n\) space-separated integers describing the lab's layout. The integer in row \(r\) and column \(c\) is \(a_{r,c} (1 \leq a_{r,c} \leq 10^5)\).s

Output Specification

Print "YES" if the lab is still okay and "NO" otherwise.

Sample Input 1

1 1 1
1 3 2
1 4 6

Sample Output 1


Sample Input 2

1 5 2
1 1 1
2 1 3

Sample Output 2



In the first example, the 3 is produced by summing the 2 to the right and the 1 above. The 4 is made by summing the 3 above and 1 to the left and the 6 is made by summing the 4 to the left and two above.

In the second example, no number in the first row and number in the second column can sum to 5. The lab is therefore not okay.


There are no comments at the moment.