ThreeColorability (SRM 587 div1 hard)

(main editorial preview post)

Intro

Link to problem statement. In short, we have a square grid. We want to color the corners of the squares using at most 3 colors, in such a way that points connected by a line segment don't share a color. Is it possible? Of course is possible! so, how about making it harder? You also need to add exactly one diagonal in each of the squares. Some squares already start with diagonals. Find a way to fill the remaining diagonals.

This explanation takes the explanation for the division 2 versionas a base. In that explanation we have found a property that is both necessary and sufficient for the setup to be valid. Each row must be equal or completely opposite to the first row. The question is how to use this property to generate the lexicographically-first way to fill the remaining cells?

Is it possible?

Given a grid of some set cells and some unknowns, can the unknown cells be filled in a way that the points are 3-colorable? In a way such that the number of Zs in each 2x2 sub-rectangle is even? In a way such that each row is equal or completely opposite to the first row?

Binary grids that follow those properties follow many other properties. There is a useful one that can be derived from the row property. If each row is equal to the first row or a negative, then we can "negate" the negative rows, the result will look like this (If we once again use 1 for Z and 0 for N):

0110001100101001
0110001100101001
0110001100101001
0110001100101001
0110001100101001
0110001100101001

Then we can negate all the columns that contain 1, and the result is full of zeros. We can conclude that valid setups are those in which you negate a set of rows and a set of columns. Let us assign values to the rows and columns, 0 for rows/columns that are not negated and 1 for the negated ones. Now take a look to the following setup:

????1??????
?0??????0??
????1??????
?0?????????

If cell `(x,y)` has value 0, then there are two possibilities: a) Neither column `x` or row `y` were negated. b) Both column `x` and row `y` were negated. We can just say that the values for row `y` and column `x` must be equal. Likewise, if cell `(x,y)` had a 1, it would mean that the values for the respective row and column must be different. If the cell was '?', then there is no condition that connects the row and column directly.

Consider a set of variables such that each could be 0 or 1. There are some conditions of the form `(v_i = v_j)`, and others in the form `(v_i != v_j)`. Is there at least one way to assign valid values to the variables? If you assign 0 to a variable, the rules will force you to assign 0 to some variables and 1 to others. You can then process the rules for each of these new variables and you will be forced to assign other values to other variables. Repeat until there is a contradiction or until all variables get an assigned value. If we assigned 1 to the first variable it wouldn't really change the result, all variables would just be negated. In other words, each condition connects two variables and we just need a Depth-first search (DFS) between the variables.

Lexicographically first

Once we can confirm if a setup can be filled correctly. We can use the same function to find the lexicographically-first result. Try the first of the unknown cells in row-major order, if adding a N to this cell position is possible, then the lexicographically-first setup will have a N in this location (Because 'N' is smaller than 'Z'). If it is not possible to put a N, put a Z. Then try the remaining unknown cells in row-major order, always placing the smallest possible value in each of them.

Code

int N;
int graph[110][110];
int color[110];


void dfs(int x, int c){
    if (color[x] != -1) {
        return;
    }
    color[x] = c;
    for (int i = 0; i < N ; i++) {
        if (graph[x][i] != -1) {
            dfs(i, (c ^ graph[x][i]));
        }
    }
}

bool check() {
    fill(color, color+N, -1);
    // do a DFS, to fill the values for the variables, start each connected
    // component with 0:
    for (int i = 0; i < N ; i++) {
        if (color[i] == -1) {
            dfs(i, 0);
        }
    }
    for (int i = 0; i < N ; i++) {
        for (int j = 0; j < N ; j++) {
            // Check if there is any inconsistency:
            if (graph[i][j] != -1 && ((color[i] ^ color[j]) != graph[i][j]) ) {
                return false;
            }
        }
    }

    return true;
}

vector <string> lexSmallest(vector <string> cells){
    int X=cells.size(), Y=cells[0].length();
    
    N = X + Y;
    for (int i = 0; i < X ; i++) {
        for (int j = 0; j < Y ; j++) {
            graph[i][j] = -1; //-1 means there is no connection between the variables
        }
    }
    // For each cell != '?':
    for (int i = 0; i < X ; i++) {
        for (int j = 0; j < Y ; j++) {
            if (cells[i][j] != '?') {
                // If the cell is 'Z', the row and column must be different
                // save 1 in the graph. Else 0, they must be equal.
                graph[i][X+j] = graph[X+j][i] = (cells[i][j] == 'Z');
            }
        }
    }
    
    if (!check() ) {
        // the board is already invalid
        return {};
    }
    
    // Lexicographically-first.
    // For each cell in row-major order:
    for (int i = 0; i < X; i++) {
        for (int j = 0; j < Y ; j++) {
            if(cells[i][j] == '?') {
                //Try with N:
                graph[i][X+j] = graph[X+j][i] = 0;
                if (!check()) {
                    // Not possible, put a Z:
                    graph[i][X+j] = graph[X+j][i] = 1;
                }
            }
        }
    }
    // translate the result back to N/Z:
    vector <string> ans(X);
    for (int i = 0; i < X ; i++) {
        for (int j = 0; j < Y ; j++) {
            ans[i] += ((graph[i][X+j] == 0) ? 'N' : 'Z');
        }
    }
    return ans;
}