Problem-Click Here
I have already solved this problem using bitsets but i am not able to understand the solution given in the editorial of this problem.
Editorial-Click Here (Scroll to page 13)
I am not able to understand these lines in the pseudocode
(For seeing the whole psedocode , refer the link to editorial above!)
Can Anyone explain the idea behind the lines (8-11) from above image?
Thanks in Advance!
if those bits are 1 that means we have painted them red, otherwise they are in original form. So if they are black in original form then we will increase the counter.
Thank You for the reply,
Though i solved this problem using bitsets but can you please elaborate in detail on the picture i posted above,i am unable to understand it properly.
I didn’t get what else is remaining. Here bits in maskR are all possibilities for coloring rows , bits in maskC represent the possibilities of coloring the column. If bit is 1 that means we have colored it red if bit is 0 that means no coloring for this row/ column is done.
Here is my logic:
int ans{};
for(int i=0; i<(1<<h); ++i){
for(int j=0;j<(1<<w);++j){
int counter{};
for(int k = 0; k<h; ++k){
for(int l = 0; l<w; ++l){
if(grid[k][l]!='#')continue;
if((i&(1<<k))!=0 || (j&(1<<l))!=0){
continue;
}
++counter;
}
}
if(counter ==x){
++ans;
}
}
}
cout << ans << '\n';
Just point out what particular thing you didn’t get in this code.
Thanks for the explaination,
See,My Logic was that First i calculated number of ‘#’ in input matrix,then i converted maskR & maskC into their binary representation using bitsets and if their are ones in their binary representations (that means elements in selected rows and columns are painted red)then i checked if their are ‘#’ in selected rows and columns or not ,then i subtracted those number of ‘#’ from total number of ‘#’ and if the number of left ‘#’ are equal to k then i incremented my answer.
This is my AC Solution:Click Here
But i didn’t get what are trying to do in these lines,i mean can you explain it in layman language:
{
if(grid[k][l]!='#')continue;
if((i&(1<<k))!=0 || (j&(1<<l))!=0){
continue;
}
++counter;
I am really sorry for the dumbness,i know it’s a simple thing but it’s not getting into my head!
Can You explain in layman language(these above lines of your code)?
Thanks Again!
Let me try again.
If the current cell isn’t black then it makes no sense to check, if it is painted red or not. Because the cell isn’t black now, after painting it, it’s still not black.
So we can claim that if cell isn’t black initially then we can skip it.
Here we are checking if kth bit of i is on or not. let i be 5. then binary representation of i will be 101.
Now for let’s check (1<<k) part for different values of k.
for k=0 : (1 << 0) it will be 1 binary = 0001
for k=1 : (1 << 1) it will be 2 binary = 0010
for k=1 : (1 << 2) it will be 4 binary = 0100
for k=1 : (1 << 3) it will be 8 binary = 1000
Now you can see that we perform & between i and k=1, k=2 we will get 1. And as I mentioned earlier that if a bit is 1 that means we have painted it red. So you must have to skip it.
char matrix[8][8];
void PrintAnswer(int r, int c, int k) {
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++;
}
}
}
cout << ans << endl;
}
Here is my code, and this was already mentioned in a post, please see those first rather than creating new ones.
Thank you so much @hello_hell ,After looking at your explaination and doing some paperwork on this for a while i understood the logic you were trying to say.
Thanks Again! 
Thank You so much @aryan12,I got the logic by looking at your well commented code. It helped me in understanding bitmasking better.
PS-Talking Out of context, but your graph inspires me a lot