Maximum Students Taking Exam - Solution & Explanation

This approach uses dynamic programming with bitmasks to represent the state of each row. You iterate through each row while keeping track of all allowed seat arrangements, updating possible arrangements for the subsequent rows. The idea is to maximize the number of students placed while satisfying the constraints (no students adjacent).

The solution involves creating a dynamic programming array where every state represents a valid seating arrangement in a row using a bitmask. For each row, compute all valid seating patterns and transition states by checking if placing students in the current row conflicts with the previous one. Maximize the count of seated students.

In this approach, use backtracking with pruning to maximize the number of placed students. You attempt to place a student in each seat and check for conflicts recursively, pruning invalid configurations early. Although slower than DP, this method works due to the constraints on m and n.

The backtracking algorithm places a student at each position if possible. It checks left, right, upper-left, and upper-right neighbors to avoid cheating. If a valid position for a student is found, it records the result and continues. Using a recursive function, the solution explores valid configurations and prunes branches where cheating could occur.

We notice that each seat has two states: selectable and non-selectable. Therefore, we can use a binary number to represent the seat state of each row, where 1 represents selectable, and 0 represents non-selectable. For example, for the first row in Example 1, we can represent it as 010010. Therefore, we convert the initial seats into a one-dimensional array ss, where ss[i] represents the seat state of the ith row.

Next, we design a function dfs(seat, i), which represents the maximum number of students that can be accommodated starting from the ith row, and the seat state of the current row is seat.

We can enumerate all the seat selection states mask of the ith row, and judge whether mask meets the following conditions:

• The state mask cannot select seats outside of seat;
• The state mask cannot select adjacent seats.

If the conditions are met, we calculate the number of seats selected in the current row cnt. If it is the last row, update the return value of the function, that is, ans = max(ans, cnt). Otherwise, we continue to recursively solve the maximum number of the next row. The seat state of the next row is nxt = ss[i + 1], and we need to exclude the left and right sides of the selected seats in the current row. Then we recursively solve the maximum number of the next row, that is, ans = max(ans, cnt + dfs(nxt, i + 1)).

Finally, we return ans as the return value of the function.

To avoid repeated calculations, we can use memoization search to save the return value of the function dfs(seat, i) in a two-dimensional array f, where f[seat][i] represents the maximum number of students that can be accommodated starting from the ith row, and the seat state of the current row is seat.

The time complexity is O(4^n times n times m), and the space complexity is O(2^n times m). Where m and n are the number of rows and columns of the seats, respectively.