maximum-students-taking-exam.cpp

// Time:  O(m * n * sqrt(m * n))
// Space: O(m * n)

// template from https://www.geeksforgeeks.org/hopcroft-karp-algorithm-for-maximum-matching-set-2-implementation/
static const int NIL = 0;
static const int INF = numeric_limits<int>::max();
  
// A class to represent Bipartite graph for Hopcroft 
// Karp implementation 
// Time:  O(E * sqrt(V))
// Space: O(V)
class BipGraph 
{ 
    // m and n are number of vertices on left 
    // and right sides of Bipartite Graph 
    int m, n; 
  
    // adj[u] stores adjacents of left side 
    // vertex 'u'. The value of u ranges from 1 to m. 
    // 0 is used for dummy vertex 
    list<int> *adj; 
  
    // These are basically pointers to arrays needed 
    // for hopcroftKarp() 
    int *pairU, *pairV, *dist; 
  
public: 
    BipGraph(int m, int n); // Constructor 
    void addEdge(int u, int v); // To add edge 
  
    // Returns true if there is an augmenting path 
    bool bfs(); 
  
    // Adds augmenting path if there is one beginning 
    // with u 
    bool dfs(int u); 
  
    // Returns size of maximum matcing 
    int hopcroftKarp(); 
}; 
  
// Returns size of maximum matching 
int BipGraph::hopcroftKarp() 
{ 
    // pairU[u] stores pair of u in matching where u 
    // is a vertex on left side of Bipartite Graph. 
    // If u doesn't have any pair, then pairU[u] is NIL 
    pairU = new int[m+1]; 
  
    // pairV[v] stores pair of v in matching. If v 
    // doesn't have any pair, then pairU[v] is NIL 
    pairV = new int[n+1]; 
  
    // dist[u] stores distance of left side vertices 
    // dist[u] is one more than dist[u'] if u is next 
    // to u'in augmenting path 
    dist = new int[m+1]; 
  
    // Initialize NIL as pair of all vertices 
    for (int u=0; u<m; u++) 
        pairU[u] = NIL; 
    for (int v=0; v<n; v++) 
        pairV[v] = NIL; 
  
    // Initialize result 
    int result = 0; 
  
    // Keep updating the result while there is an 
    // augmenting path. 
    while (bfs()) 
    { 
        // Find a free vertex 
        for (int u=1; u<=m; u++) 
  
            // If current vertex is free and there is 
            // an augmenting path from current vertex 
            if (pairU[u]==NIL && dfs(u)) 
                result++; 
    } 
    return result; 
} 
  
// Returns true if there is an augmenting path, else returns 
// false 
bool BipGraph::bfs() 
{ 
    queue<int> Q; //an integer queue 
  
    // First layer of vertices (set distance as 0) 
    for (int u=1; u<=m; u++) 
    { 
        // If this is a free vertex, add it to queue 
        if (pairU[u]==NIL) 
        { 
            // u is not matched 
            dist[u] = 0; 
            Q.push(u); 
        } 
  
        // Else set distance as infinite so that this vertex 
        // is considered next time 
        else dist[u] = INF; 
    } 
  
    // Initialize distance to NIL as infinite 
    dist[NIL] = INF; 
  
    // Q is going to contain vertices of left side only.  
    while (!Q.empty()) 
    { 
        // Dequeue a vertex 
        int u = Q.front(); 
        Q.pop(); 
  
        // If this node is not NIL and can provide a shorter path to NIL 
        if (dist[u] < dist[NIL]) 
        { 
            // Get all adjacent vertices of the dequeued vertex u 
            list<int>::iterator i; 
            for (i=adj[u].begin(); i!=adj[u].end(); ++i) 
            { 
                int v = *i; 
  
                // If pair of v is not considered so far 
                // (v, pairV[V]) is not yet explored edge. 
                if (dist[pairV[v]] == INF) 
                { 
                    // Consider the pair and add it to queue 
                    dist[pairV[v]] = dist[u] + 1; 
                    Q.push(pairV[v]); 
                } 
            } 
        } 
    } 
  
    // If we could come back to NIL using alternating path of distinct 
    // vertices then there is an augmenting path 
    return (dist[NIL] != INF); 
} 
  
// Returns true if there is an augmenting path beginning with free vertex u 
bool BipGraph::dfs(int u) 
{ 
    if (u != NIL) 
    { 
        list<int>::iterator i; 
        for (i=adj[u].begin(); i!=adj[u].end(); ++i) 
        { 
            // Adjacent to u 
            int v = *i; 
  
            // Follow the distances set by BFS 
            if (dist[pairV[v]] == dist[u]+1) 
            { 
                // If dfs for pair of v also returns 
                // true 
                if (dfs(pairV[v]) == true) 
                { 
                    pairV[v] = u; 
                    pairU[u] = v; 
                    return true; 
                } 
            } 
        } 
  
        // If there is no augmenting path beginning with u. 
        dist[u] = INF; 
        return false; 
    } 
    return true; 
} 
  
// Constructor 
BipGraph::BipGraph(int m, int n) 
{ 
    this->m = m; 
    this->n = n; 
    adj = new list<int>[m+1]; 
} 
  
// To add edge from u to v and v to u 
void BipGraph::addEdge(int u, int v) 
{ 
    adj[u].push_back(v); // Add u to v’s list. 
} 
  
// Hopcroft-Karp bipartite matching
class Solution {
public:
    int maxStudents(vector<vector<char>>& seats) {
        static vector<pair<int, int>> directions = {{-1, -1}, {0, -1}, {1, -1}, 
                                                    {-1, 1}, {0, 1}, {1, 1}};
        unordered_map<int, int> lookup;
        int u = 0, v = 0;
        for (int i = 0; i < seats.size(); ++i) {
            for (int j = 0; j < seats[0].size(); ++j) {
                if (seats[i][j] != '.') {
                    continue;
                }
                lookup[i * seats[0].size() + j] = (j % 2 == 0) ? ++u : ++v;
            }
        }
        BipGraph g(seats.size() * seats[0].size(), seats.size() * seats[0].size()); 
        for (int i = 0; i < seats.size(); ++i) {
            for (int j = 0; j < seats[0].size(); j += 2) {
                if (seats[i][j] != '.') {
                    continue;
                }
                for (const auto& [dx, dy] : directions) {
                    const auto& [ni, nj] = make_pair(i + dx, j + dy);
                    if (0 <= ni && ni < seats.size() && 
                        0 <= nj && nj < seats[0].size() &&
                        seats[ni][nj] == '.') {
                        g.addEdge(lookup[i * seats[0].size() + j],
                                  lookup[ni * seats[0].size() + nj]);
                    }
                }
            }
        }
        return u + v - g.hopcroftKarp();
    }
};

// Time:  O(|V| * |E|) = O(m^2 * n^2)
// Space: O(|V| + |E|) = O(m * n)
// Hungarian bipartite matching
class Solution2 {
public:
    int maxStudents(vector<vector<char>>& seats) {
        int count = 0;
        for (int i = 0; i < seats.size(); ++i) {
            for (int j = 0; j < seats[0].size(); ++j) {
                if (seats[i][j] != '.') {
                    continue;
                }
                ++count;
            }
        }
        return count - Hungarian(seats);
    }

private:
    int Hungarian(const vector<vector<char>>& seats) {
        int result = 0;
        vector<vector<pair<int, int>>> matching(seats.size(),
                                                vector<pair<int, int>>(seats[0].size(), {-1, -1}));
        for (int i = 0; i < seats.size(); ++i) {
            for (int j = 0; j < seats[0].size(); j += 2) {
                if (seats[i][j] != '.') {
                    continue;
                }
                vector<vector<bool>> lookup(seats.size(),
                                            vector<bool>(seats[0].size(), false));
                if (dfs(seats, {i, j}, &lookup, &matching)) {
                    ++result;
                }
            }
        }
        return result;
    }
    
    int dfs(const vector<vector<char>>& seats,
            const pair<int, int>& e,
            vector<vector<bool>> *lookup,
            vector<vector<pair<int, int>>> *matching) {
        static vector<pair<int, int>> directions = {{-1, -1}, {0, -1}, {1, -1}, 
                                                    {-1, 1}, {0, 1}, {1, 1}};
        const auto& [i, j] = e;
        for (const auto& [dx, dy] : directions) {
            const auto& [ni, nj] = make_pair(i + dx, j + dy);
            if (0 <= ni && ni < seats.size() && 
                0 <= nj && nj < seats[0].size() &&
                seats[ni][nj] == '.' &&
                !(*lookup)[ni][nj]) {
                (*lookup)[ni][nj] = true;
                if ((*matching)[ni][nj].first == -1 ||
                    dfs(seats, (*matching)[ni][nj], lookup, matching)) {
                    (*matching)[ni][nj] = e;
                    return true;
                }
            }
        }
        return false;
    }
};

// Time:  O(m * 2^n * 2^n) = O(m * 4^n)
// Space: O(2^n)
// dp solution
class Solution3 {
public:
    int maxStudents(vector<vector<char>>& seats) {
        const int state_size = 1 << seats[0].size();
        unordered_map<int, int> dp;
        dp[0] = 0;
        for (const auto& row : seats) {
            int invalid_mask = 0;
            for (int i = 0; i < row.size(); ++i) {
                if (row[i] == '#') {
                    invalid_mask |= 1 << i;
                }
            }
            unordered_map<int, int> new_dp;
            for (const auto& [mask1, v1] : dp) {
                for (int mask2 = 0; mask2 < state_size; ++mask2) {
                    if ((mask2 & invalid_mask) ||
                        (mask2 & (mask1 << 1)) || (mask2 & (mask1 >> 1)) ||
                        (mask2 & (mask2 << 1)) || (mask2 & (mask2 >> 1))) {
                        continue;
                    }
                    new_dp[mask2] = max(new_dp.count(mask2) ? new_dp[mask2] : 0,
                                        v1 + __builtin_popcount(mask2));
                }
            }
            dp = move(new_dp);
        }
        return dp.empty() ? 0 : max_element(dp.cbegin(), dp.cend(),
                                            [](const auto& a, const auto& b) {
                                                return a.second < b.second;
                                            })->second;
    }
};