Last Updated: 19 Jun, 2021

Maximum Students

Easy

Asked in companies

Solve now

Problem statement

The Ultimate Ninja Ankush, has prepared a test for all of his fellow Ninja students, but since he is the Ultimate Ninja, he does not like cheating, and since his students are also ninjas, they broke some chairs in the dojo while practicing their moves.

The class consists of ‘M’ * ‘N’ seats, represented in a matrix ‘SEATS’. Among the seats, some of the seats are broken. If a seat is broken, it is denoted by '#' character otherwise it is denoted by a '.' character, denoting that the seat can be occupied. A Ninja can’t sit in a broken seat.

Ankush wants to avoid cheating at any cost. According to his observations, a student can see the answers of four neighboring students sitting next to the left, right, upper left, and upper right, but they cannot see the answers of the student sitting directly in front or behind him. Ankush is very busy so he wants to use the dojo to the fullest. More formally he wants to know the maximum number of ninja students that can be placed in the dojo.

For example

Given:
‘M’ = 3, ‘N’ = 3.
‘SEATS’ = {
   {‘.’, ‘.’, ‘.’},
   {‘#’,’#’, ‘#’},
   {‘.’,’.’,’.’} 
   }
The answer will be 4, since 4 students can be placed at the four corners, i.e. (0,0), (2,2), (2,0), and (0,2) such that no cheating is possible.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘M,’ where ‘M’ is the number of rows in ‘SEATS’ and ‘N’ where ‘N’ is the number of columns in ‘SEATS’.

The next ‘M’ line contains ‘N’ space-separated integers which tell if the seat is broken or in good condition.

Output Format :

For each test case, You are supposed to return an integer that denotes the maximum number of students that can be placed such that no cheating is possible.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= ‘T’ <= 10
1 <= ‘N’ <= 10
1 <= ‘M’ <= 10

Time Limit: 1sec.

Solve now

Approaches

01 Approach

In computing, numbers are internally represented in binary. This means, where you use an integer type for a variable, this will actually be represented internally as a summation of zeros and ones.

Bit masking allows you to use operations that work on bit-level.

Editing particular bits in a byte(s)
Checking if particular bit values are present or not.

You apply a mask to a value, wherein in our case the value is our state 00000101 and a mask is again a binary number, which indicates the bits of interest.

The idea is to use a bitmask to denote the state of each row, where 1 denotes that the seat is good and students can be placed there and 0 denotes that the seat is broken.

When we arrange for the students to sit in this row, we can also use ‘N’ bits to represent the students. The i-th bit is 1 if and only if the i-th seat is occupied by a student. We should notice that n bits representing students must be a subset of ‘N’ bits representing seats.

Since there will be recurring problems, we use a ‘dp[i][j]’ table to store and cache the states, where ‘i’ denotes the row and ‘j’ is the ‘mask’ of seated students.

We denote ‘dp[i][mask]’ as the maximum number of students for the first ‘i’ rows while the students in the i-th row follow the masking mask. There should be no adjacent valid states in the mask. The transition function is:

‘dp[i][mask]’ = max(‘dp[i - 1][mask']’) + number of valid bits(mask)

where mask' is the configuration of students for the (i-1)-th row. To prevent students from cheating, the following equation must hold:

(mask & (mask' >> 1)) == 0, there should be no students in the upper left position for every student.
((mask >> 1) & mask') == 0, there should be no students in the upper right position for every student.

If these two equations hold and ‘dp[i - 1][mask']’ itself is valid, we could then transition from ‘dp[i - 1][mask']’ to ‘dp[i][mask]’ according to the transition function.

The steps are as follows:

Parse the given array ‘SEATS’ into an array ‘validity’ which holds the bitmask for each row, i.e. if the ‘i’th seat is in good condition, the set (1 << ‘i’)th bit, else let it stay zero.
Maintain a 2-D ‘dp’ array used to cache the recurring subproblems.
Loop through each row using ‘i’:
- Maintain a variable ‘valid’ which denotes the ‘validity[i]’.
- We will try all possible combinations of placing students who are eligible, say ‘j’.
- To check whether ‘j’ is eligible it must be a subset of ‘valid’, and check there is no adjacent student in the row.
- This is done by ensuring (‘j’& ‘valid’ == ‘j’) and (‘j’ & ‘j >> 1’ == 0) respectively.
  - Now we will try all possible combinations, say ‘k’, which are eligible in the previous row, w.r.t. to our current placement scheme.
  - To check whether ‘k’ is eligible, (‘j’ & ‘k >> 1’ == 0) and ( ‘ j >> 1’ & ‘k’ == 0) should be satisfied.
  - If they we found such combinations, we will select the global optimal substructure, i.e. ‘dp[i][j]’ = max(‘dp[i][j]’, ‘dp[i - 1][k]’ + __builtin_popcount(‘j’)), where ‘__builtin_popcount(‘j’) tells the number of set bits in the number ‘j’.
The final answer is the maximum value in the whole dp array, find that and return that as the final answer.

Solve now