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.

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 a_x, y ≠ 1, there should exist two indices s and t so that a_x, y = a_x, s + a_t, y, where a_i, 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 a_i, j (1 ≤ a_i, j ≤ 10⁵).

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:

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! 🙂

C# – CodeForces – Okabe and Future Gadget Laboratory

Related posts: