 # H and V atcoder problem

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;

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
}

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 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