Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Maximum Students Taking Exam

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

Maximum Students Taking Exam



Similar Problems:

  • CheatSheet: LeetCode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #dynamicprogramming, #bitmaskdp

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:
Maximum Students Taking Exam

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
linkedin
github
slack

Post Views: 0
Posted in HardTagged #classic, #dynamicprogramming, bitmaskdp, redo

Post navigation

LeetCode: Tweet Counts Per Frequency
LeetCode: Minimum Number of Steps to Make Two Strings Anagram

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.