Problem statement

https://leetcode.com/problems/maximum-students-taking-exam/

Solution 1

First solution idea is to fill line by line and make sure that we do not have any collisions between line. What we can do is for every line (row) compute all possible patterns for this row first. Then we will use function dp(curr, i), where:

  1. curr is bitmask for the current row we are now.
  2. i is number of current row.

Then to evaluate dp(curr, i), we need to look at all rows from masks[i-1] and make sure that we do not have a collision: we already checked that we do not have any in each row, it is enough the check that we do not have between rows, we can do it, using if not (curr >> 1) & prev and not curr & (prev >> 1) condition: we move one of the rows to the left and check if we have ones at the same place.

Complexity

Rude estimate is $O(2^n \cdot 2^n \cdot m)$, because we have $2^n \cdot m$ different states and $O(2^n)$ transitions from one state to others. Space complexity is $O(2^n\cdot m)$. In fact, there will be no more than $O(\phi^n)$ states for each row, so final time complexity can be estimated as $O(\phi^{2n} \cdot m)$, space complexity is $O(\phi^{n} \cdot m)$.

Code

class Solution:
    def maxStudents(self, seats):
        m, n = len(seats), len(seats[0])
        masks = []

        for row in seats:
            mask = sum((1 << j)*(v==".") for j, v in enumerate(row))
            masks.append([i for i in range(1<<n) if i & mask == i and not i & (i>>1)])
            
        @lru_cache(None)
        def dp(curr, i):
            if i == -1: return 0
            
            res = 0
            for prev in masks[i-1]:
                if not (curr >> 1) & prev and not curr & (prev >> 1):
                    res = max(res, dp(prev, i - 1))

            return res + bin(curr).count("1")

        return max(dfs(mask, m-1) for mask in masks[m-1])

Solution 2

There is smarter solution, using idea of dp with broken profile, see also similar problem 1659.

\[\begin{array}{|c|c|c|c|c|c|c|} \hline &&&&&&\\ \hline &&&&&&\\ \hline &&&ind&r[0]&r[1]&r[2]\\ \hline r[3]&r[4]&r[5]&r[6]&r[7]&&\\ \hline &&&&&&\\ \hline \end{array} \ \ \ \ \ \begin{array}{|c|c|c|c|c|c|c|} \hline &&&&&&\\ \hline &&&&&&\\ \hline &&&r[0]&r[1]&r[2]&r[3]\\ \hline r[4]&r[5]&r[6]&r[7]&&&\\ \hline &&&&&&\\ \hline \end{array}\]

Here we need to keep broken row with total $n+1$ elements. Now, we can try to fill element in index place either with $0$ or with $1$. We always have option to put $0$. If we want to put $1$ we need to make sure, that we do not have conflict:

  1. We need to make sure, that if we have neighbour to the right, then value of this element is not equal to $1$: first bit of row can be taken with row & (1<<n) formula.
  2. We need to make sure, that if we have neighbour to the right bottom, then its value is not equal to $1$. To get this element we can use row & 1, which will give the last bit of `row.
  3. We need to make sure, that if we have neighbour to the left bottom, then its value is not equal to $1$. To get this element we need to take row & 4, that is the 3-rd element from the end of row.
  4. Finally, we need to make sure, that S[y][x] is not equal to #.

In the end we return dp(m*n-1, 0).

Complexity

We can estimate number of states as $O(mn\cdot 2^{n+1})$, and we have $2$ transactions from one state to another. Hence time and space complexity is $O(mn\cdot 2^n)$. It can be shown that in fact it is $O(mn\cdot \phi^n)$.

Code

class Solution:
    def maxStudents(self, S):
        m, n = len(S), len(S[0])
        
        @lru_cache(None)
        def dp(index, row):
            if index == -1: return 0
            y, x = index//n, index%n
            c = (x < n-1 and row & 1<<n) or (x < n-1 and y < m-1 and row & 1)
            c = c or (x > 0 and y < m-1 and row & 4) or (S[y][x] == "#")
            cands = [dp(index-1, row//2)]
            if not c: cands.append(1 + dp(index-1, row//2 + (1<<n)))
            return max(cands)
 
        return dp(m*n-1, 0)

Remark

There is in fact $O(m^2 n^2)$ time complexity algorithm for this problem, because our graph in fact bipartite: odd and even columns can be seen as two parts of our graph and the question is to find maximum independent set in this graph.