Google codejam 2020 solution to vestigium problem

0 / 166
vestigium google code jam 2020

Problem statement

 

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, TT 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 Mi,1Mi,2 …, Mi,NMi,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 ≤ Mi,j ≤ N, for all i, j.

 

Sample

 

Input
 
Output
 
3
4
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
4
2 2 2 2
2 3 2 3
2 2 2 3
2 2 2 2
3
2 1 3
1 3 2
1 2 3

  
Case #1: 4 0 0
Case #2: 9 4 4
Case #3: 8 0 2

  

 

In Sample Case #1, the input is a natural Latin square, which means no row or column has repeated elements. All four values in the main diagonal are 1, and so the trace (their sum) is 4.

 

In Sample Case #2, all rows and columns have repeated elements. Notice that each row or column with repeated elements is counted only once regardless of the number of elements that are repeated or how often they are repeated within the row or column. In addition, notice that some integers in the range 1 through N may be absent from the input.

 

In Sample Case #3, the leftmost and rightmost columns have repeated elements.

 

 

 

Solution in C++ below:-

 

 

#include <bits/stdc++.h>

using namespace std;


int main() {
  int T, k = 1;

  cin >> T;

  while (T--) {
    int N;
	cout << endl;
    cin >> N;
    int i, matrix[N][N];
    
	
	bool rowHasDups = false;
	bool colHasDups = false;
	
	
	for (int x = 0; x < N; x++) {
	    for (int y = 0; y < N; y++) {
	        cin >> matrix[x][y];
	    }
	}
	
	int rowRepeatCount = 0, colRepeatCount = 0,
	diagonalSum = 0;
	
	for (int i = 0; i < N; i++) {
		rowHasDups = colHasDups = false;
		std::multiset<int>row;
	    std::multiset<int>col;
		
		for (int j = 0; j <  N; j++) {
		    
			if (i == j) {
				diagonalSum += matrix[i][j];
			}
			int rowc = matrix[i][j];
			int colc = matrix[j][i];
			
			
			if (row.count(rowc)) {
				rowHasDups = true;
			}
			
			if (col.count(colc)) {
				colHasDups = true;
			}
			
			row.insert(rowc);
			col.insert(colc);
		}
		
		if (rowHasDups) {
			rowRepeatCount++;
		}
		
		if (colHasDups) {
			colRepeatCount++;
		}
	}

    cout << "Case #" << k << ": " << diagonalSum << " " 
    << rowRepeatCount << " " << colRepeatCount << endl;
    
    //k is for printing the Case Number
    k++;
  }

  return 0;
}

 

 

Solution analysis:-

 

  • Iterate through the matrix elements for processing elements

 

  • Push the elements from the ith row and jth column in row and column multisets during each iteration. Also compute sum of all diagonal elements by checking for condition where i = j

 

  • As elements are processed, check if a particular element is already present in the multiset which will determine to find out how many times a particular element is duplicated in a particular row and column

 

  • After the current row and column processing is finished, increment the row and column duplicates count

 

  • For each matrix, output Diagonal sum, row element repeat count and column element repeat counts

 

Algorithm runs in O(N^2) time complexity.

 

Subscribe and follow Golibrary on Facebook and Linkedin to get all the updates.

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts