LeetCode: Maximum Students Taking Exam

Posted on August 5, 2019July 26, 2020 by braindenny

Maximum Students Taking Exam

Similar Problems:

Given a m * n matrix seats that represent seats distributions in a classroom. If a seat is broken, it is denoted by ‘#’ character otherwise it is denoted by a ‘.’ character.

Students can see the answers of those sitting next to the left, right, upper left and upper right, but he cannot see the answers of the student sitting directly in front or behind him. Return the maximum number of students that can take the exam together without any cheating being possible..

Students must be placed in seats in good condition.

Example 1:

Input: seats = [["#",".","#","#",".","#"],
                [".","#","#","#","#","."],
                ["#",".","#","#",".","#"]]
Output: 4
Explanation: Teacher can place 4 students in available seats so they don't cheat on the exam.

Example 2:

Input: seats = [[".","#"],
                ["#","#"],
                ["#","."],
                ["#","#"],
                [".","#"]]
Output: 3
Explanation: Place all students in available seats.

Example 3:

Input: seats = [["#",".",".",".","#"],
                [".","#",".","#","."],
                [".",".","#",".","."],
                [".","#",".","#","."],
                ["#",".",".",".","#"]]
Output: 10
Explanation: Place students in available seats in column 1, 3 and 5.

Constraints:

seats contains only characters ‘.’ and’#’.
m == seats.length
n == seats[i].length
1 <= m <= 8
1 <= n <= 8

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

## https://code.dennyzhang.com/maximum-students-taking-exam
## Basic Ideas: dynamic programming + bitmask
##
##  1. For each row, try all the possiblities
##  2. How we confirm no adjacent students in one row?
##      Use bitmask for each row. 1 represent, it's taken
##      Fact: For X, if X & (X<<1) == 0, there are no two adjacent 1s in its binary representation
##  3. dp[r][mask] = max(dp[r][mask], dp[r - 1][prev_mask] + bit_count(mask)
##
## Complexity: Time ?, Space ?
class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        m, n = len(seats), len(seats[0])
        dp = [collections.defaultdict(lambda: -1) for _ in range(m+1)]
        dp[0][0] = 0
        res = 0
        for i in range(1, m+1):
            # print(i, dp[0], dp[0][0])
            rowState = 0
            for j in range(n):
                # 0s in rowState means broken seats
                rowState = 2*rowState + (seats[i-1][j] == '.')
            for s2 in range(2**n):
                # make sure the state is valid
                if s2 & rowState != s2: continue
                # adjacent students in this row
                if s2 & (s2>>1) != 0: continue
                for s1 in range(2**n):
                    # check upper left
                    if s2 & (s1>>1) != 0: continue
                    # check upper right
                    if s2 & (s1<<1) != 0: continue
                    # s1 is valid in previous row
                    if dp[i-1][s1] != -1:
                        dp[i][s2] = max(dp[i][s2], dp[i-1][s1]+f'{s2:b}'.count('1'))
                    if i == m:
                        res = max(res, dp[i][s2])
        return res

Post Views: 0