PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY : BEGINNER
PREREQUISITES:
Matrixes
PROBLEM:
A NxN square matrix is a Latin square if each element in it is one among the N different values, without being repeated within a row or a column. Here you will be handling only “natural Latin squares” in which the N values are the integers between 1 and N including 1 and N.
Given a matrix that contains only integers in the interval 1 to N, find its trace and verify if it is such a Latin Square.
NOTE: You need to consider the number of rows and the number of columns that contain repeated values.
For each of the test cases, output one line containing the following statement:- 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.
QUICK EXPLANATION:
The question is very straightforward, so is the answer. Calculate the sum of elements with same indices (of index [i][i] ) to get the trace.
For each row and column, find whether it contains a duplicate element and if yes, increment their respective counters.
EXPLANATION:
For finding trace:
Iterate from 0 to N-1 and find the sum of diagonal elements(i.e. Matrix[i][i], if i is the iterator).
For finding the number of rows of the matrix that contain repeated elements:
Since the constraints are low, there are many possible solutions. One solution is to iterate through each row and find the unique elements and to check whether it is equal to the original row.
For finding the number of columns of the matrix that contain repeated elements:
Same method as that of rows. Iterate through each column and find the unique elements and to check whether it is equal to the original column.
SOLUTIONS:
Setter's Solution
#include
#include
#include
#include
#include
using namespace std;
int main() {
int n;
cin>>n;
for(int i=0;i<n;i++)
{
int s,ip;
int col=0,row=0;
float tran=0;
cin>>s;
int ar[s][s],uni[s],tar[s][s];
for(int j=0;j<s;j++)
{
for(int k=0;k<s;k++)
{cin>>ar[j][k];
tar[k][j]=ar[j][k]; // storing the transpose in another matrix
}
}
for(int m=0;m<s;m++)
tran+=ar[m][m]; // finding the trace
for(int k=0;k<s;k++)
{ copy(ar[k],ar[k]+s,uni); //assigning the k th row to the array uni
sort(uni,uni+s); // sort the array uni
ip=unique(uni,uni+s)-uni; // finding the number of unique elements
if(ip!=s) // if all elements are not unique
row++;
}
for(int l=0;l<s;l++)
{
copy(tar[l],tar[l]+s,uni); // same method, but with transpose.
sort(uni,uni+s);
ip=unique(uni,uni+s)-uni;
if(ip!=s)
col++;
}
cout<<"Case "<<i+1<<": "<<tran<<" "<<row<<" "<<col<<"\n";
}
return 0;
}
Tester's Solution
Same Person
Editorialist's Solution
Same Person