Code Jam 2020 Qualification Round

Problem: Vestigium 

Vestigium means "trace" in Latin. In this problem we work with Latin squares and matrix traces.

The trace of a square matrix is the sum of the values on the main diagonal (which runs from the upper left to the lower right).

An N-by-N square matrix is a Latin square if each cell contains one of N different values, and no value is repeated within a row or a column. In this problem, we will deal only with "natural Latin squares" in which the N values are the integers between 1 and N.

Given a matrix that contains only integers between 1 and N, we want to compute its trace and check whether it is a natural Latin square. To give some additional information, instead of simply telling us whether the matrix is a natural Latin square or not, please compute the number of rows and the number of columns that contain repeated values.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each starts with a line containing a single integer N: the size of the matrix to explore. Then, N lines follow. The i-th of these lines contains N integers M_i,1, M_i,2 ..., M_i,N. M_i,j is the integer in the i-th row and j-th column of the matrix.

Output

For each test case, output one line containing Case #x: k r c, where x is the test case number (starting from 1), k is the trace of the matrix, r is the number of rows of the matrix that contain repeated elements, and c is the number of columns of the matrix that contain repeated elements.

Limits

Test set 1 (Visible Verdict)

Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
2 ≤ N ≤ 100.
1 ≤ M_i,j ≤ N, for all i, j.

Answer (Java language):

import java.util.*;

import java.io.*;

public class Solution {

    

    public static void main(String args[])

    {

        try{

            // Input the number of test cases you want to run

            Scanner sc = new Scanner(System.in);

            int t = sc.nextInt();

            int caseN0 = 1;

            

            while (t > 0)

            {

                // variables declarations

                int n = sc.nextInt();

                

                int[][] matrix = new int[n][n];

                int trace = 0;

                int r = 0, c = 0;

                Set<Integer> hash_Set = new HashSet<Integer>(); 

                

                // create matrix using user's inpur

                for(int row=0; row < n; row++){

                    for(int col=0; col < n; col++){

                        matrix[row][col] = sc.nextInt();

                        // used to calculate number of repeated element in row

                        hash_Set.add(matrix[row][col]);

                    }

                    if(hash_Set.size() != n)

                        r++;   

                    hash_Set.clear();

                }

                

                // calculate trace

                for(int count=0; count < n; count++){

                    trace += matrix[count][count];

                }

                

                // calculate number of columns of repeated element

                 hash_Set.clear();

                 

                for(int row=0; row < n; row++){

                    for(int col=0; col < n; col++){

                         hash_Set.add(matrix[col][row]);

                    }

                    if(hash_Set.size() != n)

                        c++;   

                    hash_Set.clear();

                }

                

                // display output

                System.out.println("Case #" + caseN0 + ": " + trace + " " + r + " " + c);

                t--;

                caseN0++;

            }

        }

        catch(Exception e) {

            System.out.println("Error" + e);

        }

    }  

}