Algorithm (Dynamic Programming)
- Let $f(i,V)$ denote the maximum number of students could be seated in first $i$ rows with last row seating configuration $V.$
- Then we have $$f(i,V)=\begin{cases}
\underset{V_{\mathrm{valid}}\in\text{feasible_config}(\mathrm{row}(i-1)),\text{no_cheat}(V_{\mathrm{valid}},V)}{\max}\{f(i-1,V_{\mathrm{valid}})+\mathrm{count}(V)\} & \text{if }V\in\text{feasible_config}(\text{row}(i)),i>0\\\\
\text{count}(V) & \text{if }i=0\text{ and }V\in\text{feasible_config}(\text{row}(i))\\\\
-\infty & \text{if }V\notin\text{feasible_config}(\text{row}(i))
\end{cases},$$ where
feasible_config
and no_cheat
are helper functions that could be easily implemented.
- Then the final solution is $$\max_{V\in\text{feasible_config}(\text{row}(R-1))}f(R-1,V)$$
- Note that the seating configuration could be encoded in
bitset
, which makes memoization of $f$ straightforward by using fixed size arrays.
Code (Cpp17)
namespace utils::dynamic_bitset {
template <typename bitset_t = int, typename... Ts, typename std::enable_if_t<std::conjunction_v<std::is_same<int, Ts>...>>* = nullptr>
int flip(bitset_t mask, Ts...arg) { return ((mask ^= (1 << arg)), ...); }
template <typename bitset_t = int, typename... Ts, typename std::enable_if_t<std::conjunction_v<std::is_same<int, Ts>...>>* = nullptr>
bool test(bitset_t mask, Ts... arg) { return ((mask & (1 << arg)) && ...); }
template <typename bitset_t = int>
int count_upto (bitset_t mask, int n) { int acc = 0; for (int i = 0; i < n; i++) if ((mask & (1 << i)) > 0) acc++; return acc; };
template <typename bitset_t = int>
int popcount(bitset_t x) {
if constexpr (std::is_same_v<bitset_t, int>)
return __builtin_popcount(x);
else if (std::is_same_v<bitset_t, long>)
return __builtin_popcountl(x);
else if (std::is_same_v<bitset_t, long long>)
return __builtin_popcountll(x);
}
} // end namespace utils::dynamic_bitset
class Solution {
public:
int maxStudents(vector<vector<char>>& seats) {
using namespace utils::dynamic_bitset;
const auto [R, C] = std::pair{std::size(seats), std::size(seats[0])};
const struct { mutable std::optional<int> f[1 << 8][8]; } mempool;
auto fit = [&](int mask, const vector<char> & seat) {
bool acc = true;
for (int i = 0; i < C and acc == true; ++i)
if (test(mask, i) and seat[i] == '#')
acc = false;
for (int i = 0; acc == true and i < C; ++i) {
if (i == 0 and test(mask, i) and test(mask, i + 1))
acc = false;
else if (i == C - 1 and test(mask, i) and test(mask, i - 1))
acc = false;
else if (0 < i and i < C - 1 and test(mask, i) and (test(mask, i + 1) or test(mask, i - 1)))
acc = false;
}
return acc;
};
auto no_cheat = [&](int cur_mask, int prev_mask) {
bool acc = true;
for (int i = 0; acc == true and i < C; ++i) {
if (i == 0 and test(cur_mask, i) and test(prev_mask, i + 1))
acc = false;
else if (i == C - 1 and test(cur_mask, i) and test(prev_mask, i - 1))
acc = false;
else if (0 < i and i < C - 1 and test(cur_mask, i) and (test(prev_mask, i + 1) or test(prev_mask, i - 1)))
acc = false;
}
return acc;
};
std::function<int(int, int)> f = [&, memo = std::ref(mempool.f)](int mask, int i) {
if (memo[mask][i])
return memo[mask][i].value();
else
return *(memo[mask][i] = [&]() {
if (i == 0)
return fit(mask, seats[i]) ? popcount(mask) : INT_MIN;
else if (i > 0 and fit(mask, seats[i]))
return [&](int acc = INT_MIN) {
for (int prev_mask = 0; prev_mask <= (1 << C) - 1; ++prev_mask)
if (fit(prev_mask, seats[i - 1]) and no_cheat(mask, prev_mask))
acc = std::max(acc, f(prev_mask, i - 1) + count_upto(mask, C));
return acc;
}();
else if (i > 0 and not fit(mask, seats[i]))
return INT_MIN;
else throw std::domain_error("unmatched case");
}());
};
const auto solution = [&] (int acc = INT_MIN) {
for (int mask = 0; mask < (1 << C); ++mask)
if (fit(mask, seats[R - 1]))
acc = std::max(acc, f(mask, R - 1));
return acc;
}();
return solution;
}
};