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.
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!
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).
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class Startup { static void Main() { int n = int.Parse(Console.ReadLine()); List<List<int>> myList = new List<List<int>>(); string strResult = "Yes"; for (int i = 0; i < n; i++) { myList.Add(ReadLineAndParseToList()); } int intValueToCompare = 0; for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) { if (myList[i][k]!=1) { intValueToCompare = myList[i][k]; bool bZeroAchieved = false; for (int ii = 0; ii < n; ii++) { for (int kk = 0; kk < n; kk++) { if (ii!=i && kk!=k) { if(intValueToCompare - myList[i][kk] - myList[ii][k]==0) { bZeroAchieved = true; } } } } if (!bZeroAchieved) strResult = "No"; } } } Console.WriteLine(strResult); } public static List<int> ReadLineAndParseToList() { return Console.ReadLine().Split().Select(int.Parse).ToList(); } } |
Well, it worked! 🙂 Cheers! 🙂