Home » Interview coding problems/challenges

Vestigium - Google CodeJam 2020 qualification round problem1 solution

Here, we are going to find the solution of Vestigium - Google CodeJam 2020 qualification round problem1 with explanation and code.
Submitted by Radib Kar, on June 19, 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, 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.

Constraints:

1 ≤ T ≤ 100.
2 ≤ N ≤ 100.
1 ≤ Mi,j ≤ N,for all i,j.

Example:

Input:
3 #no of test cases
4 # value of N
1 2 3 4 # ith row
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

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

Explanation:

In Example #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 Example #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 Example #3, the leftmost and rightmost columns have repeated elements.

Source: Qualification Round 2020 - Code Jam 2020 - Vestigium

Solution

Before discussing the solution, I want to mention a few points here on Google Codejam. Codejam is similar to competitive programming. Here time complexity is not only the measure. Say your code has a time complexity of O(n) but the loop runs twice and the second one is redundant. This may lead to TLE through your time complexity is optimal. So few things we need to optimize is:

1. Fast i/o- use fast i/o to reduce the time (refer to fast i/o article of our website)
2. Loop optimization: Refactor your code so that there are no redundant loops
3. Avoid functions as this may lead to more time taken (using the function is always recommended to write production-level code, but competitive programming is different)

So here I haven't used any function and have used fast i/o. {Please refer to my code for details.

Now back to the solution.

1) Computing trace

Diagonal means a[i][i]

Trace of a matrix means sum of the diagonal which is sum(a[i][i])

I have computed the trace while taking input as part of loop optimization

While taking the input while row==column, I have added the input to my cumulative sum and after input taking is done, I have my trace value ready too.

2) Checking number of rows having duplicate entry

I have done this too while taking input. While taking input for each row, I have kept a map to check whether the input is already present there or not. If present, mark that row as duplicate and we are done for that row, for further inputs we will not check anymore to reduce time. This can be done using a flag variable.

So, By the time I took my input, I have two things ready. One is trace and another is the count of duplicate rows.

3) Checking number of rows having duplicate entry

For this thing, I was unable to compute while taking the input. As I was taking input row-wise, the column was not ready for me until my last row input. I could have stored additionally each column but that would be not so efficient considering. To compute this using another loop similar I did for row duplicate checking. For each column, we will use a map and check if any duplicate value has arrived r not. If any time, we find a duplicate, just mark that column as duplicate as proceed to the next column.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

#define lli long long int

int main()
{
    // fast io
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int t;
    cin >> t;
    
    for (int test_case = 1; test_case <= t; test_case++) {
        int n;
    
        //input N
        cin >> n;
    
        int** arr = (int**)(malloc(sizeof(int*) * n));
    
        //to calculate trace
        lli sum = 0;
    
        //to calculate duplicate rows
        int row = 0;
    
        for (int i = 0; i < n; i++) {
            arr[i] = (int*)(malloc(sizeof(int) * n));
            map<int, int> mymap;
            bool flag = false;
            for (int j = 0; j < n; j++) {
                cin >> arr[i][j];
                //calculating trace of the matrix
                if (i == j)
                    sum += arr[i][j];
                //to check whether duplicate exists in this column
                if (flag == false && mymap.find(arr[i][j]) != mymap.end()) {
                    row++;
                    flag = true;
                }
                if (flag == false)
                    mymap[arr[i][j]]++;
            }
        }
    
        // to calculate duplicate columns
        int col = 0;
        for (int i = 0; i < n; i++) {
            map<int, int> mymap;
            bool flag = false;
            for (int j = 0; j < n; j++) {
                // to check whether duplicate exists in this column
                if (flag == false && mymap.find(arr[j][i]) != mymap.end()) {
                    col++;
                    flag = true;
                    // once duplicate found simply break
                    break;
                }
                if (flag == false)
                    mymap[arr[j][i]]++;
            }
        }
        cout << "Case #" << test_case << ": " << sum << " " << row << " " << col << endl;
    }
    
    return 0;
}

Output:

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