CODEWITHSUNDEEP
c++algorithmsubgrid
user2582118
user2582118

Reputation: 53

Explaining "counting the number of subgrids" solution in the Competitive Programming Guide Book

I've come across the explanation for a problem in the competitive programmer's handbook and don't really understand how it encompasses all the solutions for the problem and I was wondering if anyone could explain it for me. I'm not sure if I'm just not understand the solution correctly if if I'm missing something about the problem. An image of the question and solution are below:

enter image description here

From the way I understand it, the question is simply asking for subgrids (four corners that make an a x b or a x a box) where each corner is black. Their solution (from what I understand) is that you count the number of black box pairs in each column then calculate the total by using the formula count(count-1)/2. My question if I'm understand this correctly is how does this encompass all the cases? The particular example I had in my head was this:

X O O O O O
O X O O O O
O O X O O O
X O O O O O 
O X O O O O
O O X O O O

and

X X X O O O
O O O O O O
O O O O O O
X X X O O O 
O O O O O O
O O O O O O

Wouldn't these two boxes give the same answer using the solution provided? You would get count = 3 for both inputs which would output 3 for the total for each input, despite them having different solutions. I just feel like I'm missing something when it comes to the solution.

Thank you for your help.

Upvotes: 3

Views: 1974

Answers (2)

Ashraful Dowla
Ashraful Dowla

Reputation: 11

The problem can be solved in O(n^2) time complexity using bit manipulations. By employing the AND operation between two rows, one can identify the corners colored in black. Subsequently, the number of subgrids can be calculated using the sum of count*(count-1)/2 for each pair of rows, where count is the number of set bits between the two rows.

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

int counting_subgrid(vector<vector>& matrix) {

int n = matrix.size();
int m = matrix[0].size();

vector<int> row(n);

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        row[i] |= matrix[i][j] << (m - j);
    }
}

int ans = 0;
for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
        int bits = __builtin_popcount(row[i] & row[j]);
        int count = bits * (bits - 1);
        ans += count / 2;
    }
}

return ans;

}

int main() {

vector<vector<int>> matrix = {
    {0, 1, 0, 0, 1},
    {0, 1, 1, 0, 0},
    {1, 0, 0, 0, 0},
    {0, 1, 1, 0, 1},
    {0, 0, 0, 0, 0}
};

cout << counting_subgrid(matrix) << endl;

}

Upvotes: 1

Walter
Walter

Reputation: 45444

The algorithm given as pseudo code is only the inner loop, as it were. The outer loop is, as explained in the preceding text, a loop over all pairs of rows.

int count_subgrids(const int** color, int n)
{
    int subgrids = 0;
    for(int a=0; a<n; ++a)
        for(int b=a+1; b<n; ++b) {    // loop over pairs (a,b) of rows 
            int count=0;
            for(int i=0; i<n; ++i) {  // loop over all columns
                if(color[a][i]==1 && color[b][i]==1)
                    ++count;
            }
            subgrids += ((count-1)*count)/2;
        }
    return subgrids;
}

In your first example, count=0 for any pair of rows, so subgrid remains 0 too. In your second example, there are three pairs of rows, namely (a,b)=(0,1), (0,2), and (1,2) for which count=2, such that subgrid=3 in the end.

Upvotes: 6

Related Questions