C# – CodeForces – Okabe and Future Gadget Laboratory

CodeForces is a nice website for anyone, who likes checking himself vs the top developers worldwide. It’s even separated into divisions, thus, they kindly provide 3 easy questions and 5 hard. Although, I do not know anyone who can call the first 3 questions of the 2. division easy. Although usually the answer comes within less than 15 minutes. In some of them.codeforces-logo-with-telegram

Thus, I will simply show the first question in the first division. It was something like this:

Okabe needs to renovate the Future Gadget Laboratory after he tried doing some crazy experiments! The lab is represented as an n by nsquare grid of integers. A good lab is defined as a lab in which every number not equal to 1 can be expressed as the sum of a number in the same row and a number in the same column. In other words, for every x, y such that 1 ≤ x, y ≤ n and ax, y ≠ 1, there should exist two indices s and t so that ax, y = ax, s + at, y, where ai, j denotes the integer in i-th row and j-th column.

Help Okabe determine whether a given lab is good!

Input

The first line of input contains the integer n (1 ≤ n ≤ 50) — the size of the lab.

The next n lines contain n space-separated integers denoting a row of the grid. The j-th integer in the i-th row is ai, j (1 ≤ ai, j ≤ 105).

Output

Print “Yes” if the given lab is good and “No” otherwise.

You can output each letter in upper or lower case.

Long story short, you have a matrix and you should say whether it is possible for each value in the matrix to be represented as a sum of one value in the same column and one value in the same row. At least this is what I understood from the first reading.

Whenever we have iteration of a matrix, these are two nested loops. Which is a complexity of N^2. However, we also have to check a given line and a given column within the matrix, for the sum. This makes the complexity up to N^4. And two more nested loops inside ours. I really was pretty curious whether such an ugly solution should work, thus I have decided to try it out:

Well, it worked! 🙂 Cheers! 🙂

About

VBA Developer

Tagged with: , ,