michaellin250's blog

By michaellin250, history, 4 weeks ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 0010

maskC = 3 , in binary 0011

So, 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[0][0] == '#': black = black + 1 : False

.

.

.

((maskR >> 0) & 1) == 0 and ((maskC >> 2) & 1) == 0 && and c[0][2] == '#': black = black + 1 : True

So we have one black square after the coloring

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How’d you get color column 0 and column 1 with row 0?

    Where did column 0 and 1 come from?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.