Maximum Students

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.

O(M * (4 ^ N)), Where ‘M’ is the number of rows, and ‘N’ is the number of columns.

Since we are trying all possible configurations of columns, twice for every row, the overall time complexity will be O(M * (2 ^ N) * (2 ^ N)) =  O(M * (4 ^ N).

O(M * (2 ^ N)), Where ‘M’ is the number of rows, and ‘N’ is the number of columns.

Since we are using a 2-D array to store the answers of each configuration corresponding to every row. So, the number of rows are M and the total number of configurations are 2^N. Hence, the overall space complexity will be O(M * (2 ^ N)).