1349. Maximum Students Taking Exam

Problem Description

Given a classroom seating arrangement represented by an m x n matrix seats, where '.' represents an available seat and '#' represents a broken seat. Students can see the answers of those sitting to their left, right, upper-left, and upper-right, but not directly in front or behind. Find the maximum number of students that can take the exam without cheating.

Solution: State Compression with Dynamic Programming (Memoization)

This problem can be efficiently solved using bit manipulation and dynamic programming. The core idea is to represent the seating arrangement of each row using a bitmask.

Bitmask Representation:

Each row can be represented by an integer (bitmask). Each bit corresponds to a seat in the row. A bit set to 1 indicates a student is seated in that position, and 0 indicates it's empty. This allows us to efficiently check for adjacent students and valid seating arrangements.

Dynamic Programming (with Memoization):

We use a recursive function dfs(seat, row) with memoization to find the maximum number of students for a given state.

• seat: An integer representing the bitmask of the current row's seating arrangement.
• row: The current row index.

The function explores all possible valid seating arrangements for the current row and recursively calls itself for the next row. Memoization (using a cache f) stores previously computed results to avoid redundant calculations.

Validity Check:

Before placing students in a row, we need to check the validity of the arrangement:

1. Available Seats: The selected seats (mask) must be a subset of available seats (seat).
2. No Adjacent Students: No two adjacent seats can be occupied. This is checked using (mask & (mask << 1)) == 0.

Base Case:

If we reach the last row, the function returns the number of students seated in that row.

Recursive Step:

For rows other than the last, the function does the following:

1. Iterates through all possible seating arrangements (mask).
2. Checks the validity of the arrangement.
3. Recursively calls dfs() for the next row, considering the constraints of previously seated students in the current row. The next row's available seats are adjusted to reflect the current row's arrangement (avoiding cheating).
4. Updates the maximum number of students (ans).

Time and Space Complexity:

• Time Complexity: O(4n * m), where m is the number of rows and n is the number of columns. Each row has up to 4n possible seating arrangements (due to constraints). Memoization helps significantly reduce the runtime.
• Space Complexity: O(2n * m). This is due to the memoization table f.

Code Implementation (Python)

from functools import cache
 
class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        def f(seat: List[str]) -> int:
            mask = 0
            for i, c in enumerate(seat):
                if c == '.':
                    mask |= 1 << i
            return mask
 
        @cache
        def dfs(seat: int, i: int) -> int:
            ans = 0
            for mask in range(1 << n):
                if (seat | mask) != seat or (mask & (mask << 1)):
                    continue
                cnt = mask.bit_count()
                if i == len(ss) - 1:
                    ans = max(ans, cnt)
                else:
                    nxt = ss[i + 1]
                    nxt &= ~(mask << 1)
                    nxt &= ~(mask >> 1)
                    ans = max(ans, cnt + dfs(nxt, i + 1))
            return ans
 
        n = len(seats[0])
        ss = [f(s) for s in seats]
        return dfs(ss[0], 0)

Other languages (Java, C++, Go, TypeScript) would follow a similar structure, primarily differing in syntax and data structure handling. The core algorithm remains the same.