# Maximum Students

Posted: 19 Jun, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### 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.
`````` Approach 1

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:

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.