We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Students Taking Exam

Number: 1471

Difficulty: Hard

Paid? No

Companies: SAP

Problem Description

Given an m x n matrix representing the classroom seats (where '.' represents a good seat and '#' a broken one), determine the maximum number of students that can sit in the classroom such that no cheating occurs. A student can see the answer sheets of adjacent students to his left, right, upper left, and upper right. Hence, two students must not be positioned in seats where one can see the other's exam.

Key Insights

  • Use bitmasking to represent each row's seating arrangement; each bit corresponds to whether a student is seated.
  • Pre-calculate all possible valid configurations (bitmasks) for each row that respect the “no adjacent students in the same row (left/right)” rule and account for broken seats.
  • Use dynamic programming with state transition between rows while making sure that the current row’s configuration does not conflict with the previous row’s configuration (i.e. avoid cheating from upper left and upper right positions).
  • Transition validation between rows is achieved by ensuring that no student in the current row has a cheating conflict with a student in the previous row (check (prev_mask << 1) and (prev_mask >> 1) against current mask).

Space and Time Complexity

Time Complexity: O(m * 2^n * 2^n) – For each of m rows, we iterate over all valid masks (at most 2^n) and check compatibility with each valid mask from the previous row. Space Complexity: O(m * 2^n) – DP table stores up to m rows with 2^n states each.

Solution

The solution uses bitmask dynamic programming to explore valid student seating arrangements row by row:

  1. Convert each row of seats into a bitmask (masking out broken seats).
  2. For each row, enumerate all valid masks where no two seated students are adjacent.
  3. Use a DP array where dp[row][mask] indicates the maximum number of students seated up to that row using the configuration represented by mask.
  4. For each row (after the first), iterate over all valid current masks and all valid previous masks, ensuring that the cheating condition is not violated by checking that no student in the current mask is directly diagonally adjacent (upper left or upper right) to any student in the previous mask.
  5. Finally, the answer is the maximum value in the DP table for the last row.

Code Solutions

# Python solution using Bitmask DP approach

def maxStudents(seats):
    m, n = len(seats), len(seats[0])
    
    # Convert each row's seat status to bitmask (1 means available seat)
    rowMasks = []
    for row in seats:
        mask = 0
        for j, seat in enumerate(row):
            if seat == '.':
                mask |= (1 << j)
        rowMasks.append(mask)
    
    # Precompute all valid seatings (bitmask) for a row given its good seats.
    validMasks = []
    for mask in range(1 << n):
        # Check if mask fits within available seats (i.e., no seat outside the good seats)
        valid = True
        for j in range(n):
            if mask & (1 << j) and not (mask & (1 << j)) <= 0:
                # Implicit check, now ensure mask is valid with respect to broken seats
                pass
        # Ensure no two adjacent seats are taken
        if mask & (mask << 1):
            valid = False
        if valid:
            validMasks.append(mask)
    
    # Filter valid configurations with respect to each row's available seats
    validMasksPerRow = []
    for i in range(m):
        masks = []
        for mask in validMasks:
            # mask must be a subset of available seats
            if mask & rowMasks[i] == mask:
                masks.append(mask)
        validMasksPerRow.append(masks)
    
    # DP initialization: each row dp[mask] stores maximum number of students using that row configuration.
    dp = [{} for _ in range(m)]
    for mask in validMasksPerRow[0]:
        dp[0][mask] = bin(mask).count("1")
    
    # Process subsequent rows.
    for i in range(1, m):
        for curMask in validMasksPerRow[i]:
            curCount = bin(curMask).count("1")
            for prevMask in dp[i-1]:
                # Check compatibility: No student in curMask should be diagonally adjacent to any student in prevMask.
                if (curMask & (prevMask << 1)) or (curMask & (prevMask >> 1)):
                    continue
                dp[i][curMask] = max(dp[i].get(curMask, 0), dp[i-1][prevMask] + curCount)
    
    # Return max value from last row's dp states.
    return max(dp[m-1].values()) if dp[m-1] else 0

# Example usage:
seats = [["#", ".", "#", "#", ".", "#"],
         [".", "#", "#", "#", "#", "."],
         ["#", ".", "#", "#", ".", "#"]]
print(maxStudents(seats))  # Expected output: 4
← Back to All Questions