H and V atcoder problem

I am not able to understand what to do in this question please help.
Link:

A very naive algorithm could be something like store the rows and columns in bits.

Example, if you select 0th, 2nd and 4th row, it will be stored in (2^0 + 2^2 + 2^4) = 21. Like this, we can have 64 (from 0 to 63) numbers and if the ith bit is set, that means you choose the ith row (and similarly for columns). Then you naively search the grid if there are k black cells or not. If yes, you increase your counter, else go to the next one.

Time complexity: O(2^r * 2^c * r * c)

Sample Code
//Header files
char matrix[8][8];

int FindAnswer(int r, int c, int k) {
    int ans = 0;
    for(int i = 0; i < (1 << r); i++) { //(1 << r) is 2 ^ r
        for(int j = 0; j < (1 << c); j++) { //(1 << c) is 2 ^ c
             int cnt = 0;
             for(int row = 0; row < r; row++) {
                   if(i >= (1 << row) && i < (1 << (row + 1))) { //if the rowth bit is set or not
                          continue; //This means the bit is set, so we have painted the row red
                   }
                   //else, we move on to the columns
                  for(int col = 0; col < c; col++) {
                         if(j >= (1 << col) && j < (1 << (col + 1))) { //if the colth bit is set or not
                               continue; //the bit is set, thus, we have painted the column red
                         }
                         //else we increase the counter if it is a black cell
                         if(matrix[row][col] == '#') {
                                cnt++;
                         }
                  }
             }
             if(cnt == k) {
                  ans++;
             }
        }
    }
    return ans;
}

int main() {
     //input
     FindAnswer(r, c, k);
}
3 Likes

How to solve this if h and w>15?

1 Like

Thanks

1 Like

I really don’t know. In the editorial of the contest, the expected complexity was O(2^r * 2^c * r * c). Using prefix sums, the time complexity can be reduced to O(2^r * 2^c * (max(r, c))). This is the best that I can think of right now. Will let you know if another idea pops up in my mind.

1 Like

Someone on the cf blog commented that, dfs can be used to in this constraints, but I am not sure how to do that.

How to write these math symbols in codechef comments :sweat_smile:

1 Like

Start with (dollar notation) and end with (dollar notation), just like this-

(dollar) O(2^r) (dollar)-> O(2^r)

3 Likes

Also this is handy: https://en.wikibooks.org/wiki/LaTeX/Mathematics

2 Likes

I didn’t know how to write summation, for all etc, until I found the following:


This template is good for learning summation.

\sum_{i = 1} ^ {N} i = (i * (i + 1)) / 2

\forall_{i = 1} ^ {N} i = a[i] \bmod m

2 Likes