SRM 533: Div1 500 MagicBoard explanation

Finally solved it. It is a nice problem that is worth explaining in a post.

You have a grid/board of at most 50x50 cells. Some cells contain a diamond. You need to find if it is possible to build a sequence of cells that visits each diamond cell exactly once. With the added condition that if we number the cells in the path in the order in which they are visited, every even cells must share the row with the cell that comes after it. And every odd cell must share the column with the next cell in the sequence.

I had difficulties to have a remotely good idea to solve this problem during the match, but I eventually I learned of the trick behind the solutions. "It is often the case that, when dealing with a grid, instead of seeing each cell as a node in a graph, it is better to see each cell as an edge in a graph". This change of perspective is actually frequent in cool problems, I think I remember two occasions in which I had to learn this trick before solving a hard problem for an editorial.

If cells are edges in a graph, what do they connect? The usual idea is to make the cell at position (i,j) connect the i-th row with the j-th column. So, in fact, our graph will contain all the rows and all the columns. There is a bidirectional edge between a row and a column if and only if there is a diamond located at the cell that has that row and that column.

That idea is great for this problem, because you will notice that if you move across the new graph, you will follow the even/odd rule automatically. You can confirm this by just noticing that there are never connections between rows and rows or between columns and columns. So, two consecutive edges will always share either a column or a row but not both.

What we now need is to find if there's a path that visits each edge in a given bidirectional graph at least once. This is a known problem that Euler has solved centuries ago: The Eulerian path.

The holy wikipedia claims that a graph will have an Eulerian path, if all nodes with non-zero degree are connected and there are at most 2 nodes with odd degree.

Catch: This sounds too good to be true. Merely make a graph containing the rows and columns, and connect them using the diamond cells, then check for the parity of the degrees. This will pass example test cases but won't solve the problem. There is a condition that we need to guard for: The first pair of edges we pick must share a row (not a column).

In order to fix this, merely question yourself: Why is the rule that at most two vertices have odd degree? Of course, the reason is that the vertices with odd degree will be the ones that will be necessarily used as extremes in the Eulerian path (start or end) (If all nodes have even degree, then there is not only an Eulerian path, there is an Eulerian cycle, which means that any node can be the start or end of an Eulerian path). Please note that to follow the condition that was just mentioned, then the first node in the path must always be a column - This means that at least one of the (at most 2) odd vertices must be a column.

Some details: If there is only one odd-degree vertex, then there is no problem, there is an Eulerian cycle between all other nodes. And then we can add the odd-degree vertex either to the end or the beginning of the path. This way we can still make sure a path exists that begins with a column and is Eulerian.

When there are no odd-degree nodes, we can begin an Eulerian path in any node, so let's just pick a column.

When there are two odd-degree nodes. Then one of them has to be the beginning of the path. Make sure that one of them is a column, then we can begin in it. If both are rows, it is not possible.

#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++) 
struct MagicBoard 
{ 
     
    bool visited[100]; 
    set<int> edges[100]; 
     
    // Depth-First Search : Used to verify that all nodes with non-zero degree 
    // belong to the same connected component. 
    void dfs(int x) 
    { 
        if (!visited[x]) { 
            visited[x] = true; 
            for_each(y, edges[x]) { 
                dfs(*y); 
            } 
        } 
    } 
     
    string ableToUnlock(vector <string> board) 
    { 
        int w = board.size(); 
        int h = board[0].size(); 
        // Let's build a graph: 
        memset(visited,0, sizeof(visited)); 
        int n = w + h; 
        for (int i=0; i<w; i++) { 
            for (int j=0; j<h; j++) { 
                if (board[i][j] == '#') { 
                    edges[i].insert(w + j); 
                    edges[w+j].insert(i); 
                } 
            } 
        } 
        // Use a dfs to veirfy that all nodes with non-zero degree are connected 
        // meanwhile, count the number of odd nodes that are columns and the 
        // number of odd nodes that are rows. 
        int compos = 0; 
        fill(visited, visited+n, false); 
        int odd_column = 0; 
        int odd_row = 0; 
        for (int i=0; i<n; i++) { 
            if ( (edges[i].size() > 0) &&  ! visited[i] ) { 
                if ( ++compos > 1 ) { 
                    return "NO"; 
                } 
                dfs(i); 
            } 
            if (edges[i].size() % 2 == 1) { 
                if (i < w) { 
                    odd_row++; 
                } else { 
                    odd_column ++; 
                } 
            } 
        } 
        if (odd_row + odd_column > 2) { 
            // Too many odd-degree nodes. 
            return "NO"; 
        } else if (odd_column + odd_row <= 1) { 
            // Can always pick a column as a start. 
            return "YES"; 
        } else if (odd_column >= 1) { 
            // There is one odd column which can be the start. 
            return "YES"; 
        } else { 
            // Sorry, no luck 
            return "NO"; 
        } 
    } 
};