HackerRank Number Theory – Largest Non-Coprime Submatrix

Challenge: Largest Non-Coprime Submatrix

Subdomeniu: Number Theory (number-theory)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464754132

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/largest-coprime-submatrix/problem

Cerinta

Given a matrix you need to find the submatrix with the largest number of elements, where the GCD (Greatest Common Divisor) of its elements is greater than one. A submatrix of the matrix is a sub-section composed of contiguous rows and columns of the original matrix.
<br/>

**Input**
Two numbers n,m in the first line. Followed by n lines with m numbers in each line.<br/>

**Constraints**  

1<=N,M<=200<br/>
1<=numbers<=10000<br/>

**Output**
Just a largest area where GCD is greater than 1.<br/>

**Sample Input**  

    3 3
    2 6 8
    4 8 3
    6 9 4

**Sample Output**  

    4

If you observe the following submatrix:  

    2 6  
    4 8  

The GCD is 2.
There is no matrix larger than this with a GCD > 1.

Cod sursa

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

static inline int gcd_int(int a, int b) {
    while (b) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<vector<int> > a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) cin >> a[i][j];
    }

    int best = 0;
    vector<int> col(m);

    for (int top = 0; top < n; ++top) {
        fill(col.begin(), col.end(), 0);

        for (int bottom = top; bottom < n; ++bottom) {
            for (int c = 0; c < m; ++c) {
                col[c] = gcd_int(col[c], a[bottom][c]);
            }

            int h = bottom - top + 1;
            vector<pair<int,int> > prev;
            prev.reserve(32);

            for (int r = 0; r < m; ++r) {
                vector<pair<int,int> > cur;
                cur.reserve(prev.size() + 1);
                cur.push_back(make_pair(col[r], r));

                for (size_t t = 0; t < prev.size(); ++t) {
                    int g = prev[t].first;
                    int l = prev[t].second;
                    int ng = gcd_int(g, col[r]);

                    if (ng == cur.back().first) {
                        if (l < cur.back().second) cur.back().second = l;
                    } else {
                        cur.push_back(make_pair(ng, l));
                    }
                }

                for (size_t t = 0; t < cur.size(); ++t) {
                    int g = cur[t].first;
                    int l = cur[t].second;
                    if (g > 1) {
                        int w = r - l + 1;
                        int area = h * w;
                        if (area > best) best = area;
                    }
                }

                prev.swap(cur);
            }
        }
    }

    cout << best << '\n';
    return 0;
}