### michaellin250's blog

By michaellin250, history, 4 weeks ago, , Here's the problem:

Problem The editorial [Scroll to problem C]

I don't understand why they did if ((maskR >> i) & 1) == 0 and ((maskC >> j) & 1) == 0 && and c[i][j] == '#': black = black + 1.

I understand they are brute forcing all possible combinations so I get why they did (1 << H) — 1 and (1 << W) — 1. But I don't understand why the shift right maskR and maskC and check if the last bit for both is 0. What does that have to do with the solution?  Comments (3)
 » 4 weeks ago, # | ← Rev. 3 →   This line "((maskR >> i) & 1) == 0 and ((maskC >> j) & 1) == 0 && and c[i][j] == '#': black = black + 1" means : If the i-th row and the j-th column not choosen to be colored, and the intersection between the i-th row and the j-th column (c[i][j]) equales '#', that means this black square will remain black after coloring the chosen rows and columns, so we want to count it.let's look at the first example:2 3 2..####and let's say maskR = 2 , in binary 0010maskC = 3 , in binary 0011So, that means we are going to color the Row No.1 (0-based) and Column 0 and 1 (0-based) and we want to count the number of black squares after coloring the choosen rows and columns.((maskR >> 0) & 1) == 0 and ((maskC >> 0) & 1) == 0 && and c == '#': black = black + 1 : False...((maskR >> 0) & 1) == 0 and ((maskC >> 2) & 1) == 0 && and c == '#': black = black + 1 : TrueSo we have one black square after the coloring
•  » » How’d you get color column 0 and column 1 with row 0? Where did column 0 and 1 come from?
•  » » » The ith bit in the mask of row is set if the ith row is painted red. Same is for the column. So we just have to count number of black cells which are not in the rows and columns in the mask. Finally, if it is equal to k then increment your answer.