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);
}
```

How to solve this if h and w>15?

Thanks

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.

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

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

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

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