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

Question

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:

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.

You count the number of black box pairs for each pair of rows independently, then apply the formula before you sum the results of. In the first case, we have for three pairs of rows with count 1 respectively. That becomes 1*0/2 = 0 after the formula which is summed up to 0. In the second case, we have one pair of rows with count 3, which gives us 3*2/2 = 3 after the formula. — n314159
Oh my lord I'm so dumb. Thank you tons!! I just kinda forgot that the code they provided was just the inner loop and not the whole thing so the count(count-1)/2 is evaluated at the end of each row. Thank you again! — user2582118
@Evg Competitive Programmer’s Handbook by Antti Laaksonen. It's available for free online: cses.fi/book/book.pdf — user2582118

Walter Walter · Accepted Answer · 2020-01-08T19:35:43

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.

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

1 Answers