3

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.

user2582118
  • 53
  • 5
  • 3
    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 Jan 08 '20 at 19:30
  • 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 Jan 08 '20 at 19:37
  • Could you tell the name of the book and author, please? – Evg Jan 08 '20 at 19:41
  • 2
    @Evg Competitive Programmer’s Handbook by Antti Laaksonen. It's available for free online: https://cses.fi/book/book.pdf – user2582118 Jan 08 '20 at 19:42
  • 1
    @user2582118, thanks! – Evg Jan 08 '20 at 19:45
  • 1
    Could someone please explain why the formula n*(n-1)/2 works? – darthfather Apr 06 '20 at 11:24
  • 1
    @darthfather to make a rectangle with black corners, we need atleast 2 columns. Correct? Now, if we have n such columns, then out of n, we have to choose 2 columns to make such rectangle, so the way to do is nC2 (n!/(n-1)! 2!). nC2 is the way of choosing any 2 items out of n distinct items. – Nakshtra Pradhan May 14 '21 at 01:39
  • @user2582118 can you please explain the optimized solution of it with example, where we divide the grid into blocks of columns. I am not able to understand how this approach is working. Thanks. – Nakshtra Pradhan May 14 '21 at 02:10

1 Answers1

6

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.

Walter
  • 44,150
  • 20
  • 113
  • 196
  • Thank you! n314159's comment to my OP also explained the same thing but thank you for writing it out and explaining, it's nice to see the code in its entirety and really helps. – user2582118 Jan 08 '20 at 19:41
  • Isn't it just one pair of rows (0,3) for which you get the count = 3. @Walter – Tawhid Joarder Dec 25 '21 at 14:01