PROBLEM LINK:
Author: Praveen Dhinwa
Tester: Jingbo Shang
Editorialist: Hanlin Ren
DIFFICULTY:
Easy-Medium
PREREQUISITES:
disjoint set union, bipartite graph, spanning forest
PROBLEM:
A matrix B_{N\times N} is good if there is an array A such that B_{i,j}=B_{j,i}=|A_i-A_j| for all 1\le i,j\le N. Given a matrix where exactly Q entries are filled, and every filled entry is 0 or 1, determine if we can fill the rest entries(by any integer, possibly not 0,1) such that the resulting matrix is good.
QUICK EXPLANATION:
The answer is “yes” if and only if you can assign every number in [1,n] even or odd, such that:
- When B_{i,j}=0, i and j have the same label;
- When B_{i,j}=1, i and j have different label.
To check this, we can either:
- Link a bidirectional edge (i,j) for any known B_{i,j}, find a spanning forest and assign labels along the tree greedily, and check if the assignment is valid;
- or, use a Disjoint Set Union structure that maintains parity information, and add edges into the structure.
EXPLANATION:
An observation
The problem actually asks if there exists an array A that satisfies Q conditions of the form “|A_i-A_j|=val”. Consider a graph with n nodes, for every such condition, we link an edge with weight val between node i and node j.
Let’s say a node i is even if A_i\equiv 0\pmod 2, otherwise say node i is odd. Then,
- if two nodes are connected by an edge of weight 0, then they’re both even or both odd;
- if two nodes are connected by an edge of weight 1, then one of them is even and the other is odd.
Thus, if the array A exists, there must be an assignment that maps every node to either even or odd, and satisfies the above requirements. But can the existence of A be guaranteed by the existence of that assignment? The answer turns out to be yes! For a valid assignment, we simply put A_i=1 if node i is odd, and put A_i=0 if it’s even. Why does this work? For every edge (i,j) in the graph,
- if its weight is 0, then either i,j are both odd, or they are both even. If they are both odd, then A_i=A_j=1; if they are both even, then A_i=A_j=0. In both cases we have A_i=A_j;
- if its weight is 1, then one of A_i,A_j is 1 and the other is 0, therefore |A_i-A_j|=1.
We see that all edges, no matter its weight is 0 or 1, is satisfied by our array A.
That is to say, the answer is “Yes” if and only if there exists a valid assignment. How to check this? There are many different solutions:
Author’s Solution
Let’s first find a spanning forest of the graph. We can maintain a data structure called disjoint set union(“DSU”), and do something similar to Kruskal’s Algorithm.
As in Kruskal’s Algorithm, initially no edge is added to the graph, and every vertex itself forms a set. Then let’s add edges one by one, in an arbitrary order(since we only need “a spanning forest”, not a “minimum” one or something, so any order is acceptable). Every time we add an edge (u,v), if u and v are in different sets, we combine these sets into one set, and add this edge to the spanning forest; otherwise we do nothing.
Pseudocode:
for i in nodes
makeset(i) //i itself is a set
for (u,v) in edges
if find(u) != find(v)
add edge (u,v) to the edge list of spanning forest
Union(u,v)//merge two sets
After we have a spanning forest, we can solve the problem. First let’s consider the case that all edges are in the spanning forest. In this case the answer is always “Yes”, and we can find a valid assignment in linear time. For every connected component, we pick an arbitrary node v and suppose v is even. For any node u in this component, if the distance between u and v is odd(i.e., there are odd edges that has weight 1 in the path from u to v), then u is odd; otherwise u is even. This assignment can be computed in one dfs:
dfs(u) : //procedure dfs()
for v is u's child :
parity[v] = parity[u] xor (the weight between (u, v))
dfs(v)
//main
for i in nodes :
if i's component is not visited :
dfs(i)
What if there are other edges? Note that no “other edge” can cross two components. If for every edge (u,v), (the parity of u) xor (the parity of v) xor (the weight of (u,v)) is 0(“parity constraint”), then the assignment is already valid. Otherwise, say edge (u,v) violates that constraint, then there is a cycle of odd weight(that passes through u and v). A cycle of odd weight means that a number’s parity is different from itself’s, which is impossible. So we only need to check if every other edge satisfies the parity constraint.
To demonstrate the idea, let’s consider the last test case in the sample. A spanning forest(tree) is shown below. Now we are adding an edge (1,3) which has weight 1. However parity of 1 and 3 are both 0(even), and this edge has weight 1, thus violates the parity constraint. Since there is an edge that violates the constraint, there should be an odd cycle — it’s 1\to 2\to 3\to 1 in this case, and this cycle means that parity(1)\ne parity(1), so there must be no solution.
Pseudocode:
for (u, v) in edges :
if parity[u] xor parity[v] xor weight[u,v] == 1 :
//an odd cycle found
print "No" and exit
print "Yes"//All edges satisfy the parity constraint
The time complexity is O(M\alpha(N)), since we used DSU.
Tester’s solution
We can modify the DSU structure so that it records parity information. Recall that the DSU structure is a set of rooted trees, where a tree stands for a set. Let father[x] be x's parent.
The basic procedure for DSU is finding root. Let find(x) be x's root. We’ll use a technique that’s called path compression: for every node that lies between x ans find(x), we set its father to be the root. The following is a demonstration of path compression.
Pseudocode:
find(x) :
if x == father[x] : //x is root
return x
father[x] = find(father[x]) //path compression
return father[x]
When merging two sets, we set the father of one’s root the other root:
Union(x, y) :
father[find(x)] = find(y)
Now comes the modification: for every node x in the DSU, we maintain diff[x], which is defined as parity(x) xor parity(father[x]). For example, consider the DSU shown in picture below. Black/white nodes are odd/even nodes respectively, and the value of diff[x] is written on the edge x\to father[x]. Note that find() changes several diff's(red ones).
We can easily rewrite our find() function. Let parity(x) be x's parity(0 if x is even and 1 if x is odd). In the following code, t is x's original father, and after find(t), diff[t] becomes parity(root) xor parity(t). Now the old diff[x] is equal to parity(x) xor parity(t), and we want the new diff[x] become parity(root) xor parity(x). It’s easy to see diff[x](new) should become diff[x](old) xor diff[t].
find(x) :
if x == father[x] : return x
t = father[x] //the original father of x
father[x] = find(t)
diff[x] = diff[x] xor diff[t]//compute new diff[x].
return father[x]
When merging two sets, we not only set the father of root_x be root_y, but also computes the new diff[root_x]. In the following pseudocode, w is the weight of inserted edge so parity(x) xor parity(y)=w; We also have parity(x) xor parity(root_x)=diff[x] and parity(y) xor parity(root_y)=diff[y]. Thus diff[root_x], which should be equal to parity(root_x) xor parity(root_y), can be computed by w xor diff[x] xor diff[y].
Union(x, y, w) :
//w is the weight of the edge (x, y)
root_x = find(x)
root_y = find(y)
father[root_x] = root_y
diff[root_x] = w xor diff[x] xor diff[y]//compute diff[root_x].
OK, with the modified DSU structure, we can solve the problem more conveniently. Just like Kruskal’s algorithm, we insert edges one by one. For an edge (u,v) with weight w, if u and v are in different sets, we just merge them; if they are in the same set, we use diff to check if this edge doesn’t make an odd-weighted cycle. The indicator for an odd-weighted cycle is an edge (x,y) with weight w such that parity(u) xor parity(v) xor w=1. Since u and v are connected, they have the same root, say r. Then diff[u]=parity(r) xor parity(u) and diff[v]=parity(r) xor parity(v), so what we need to check is diff[u] xor diff[v] xor w=1.
for (u,v) in edges:
w = weight of (u,v)
if find(u) != find(v) :
Union(u, v, w)
else :
if diff[u] xor diff[v] xor w == 1 :
return "No"
//otherwise do nothing
So we just scan all edges and judge every edge that’s not in the forest one by one. This solution also has complexity O(M\alpha(N)).
Editorialist’s solution
We can find a spanning forest by simple dfs.
Let’s iterate over all nodes. When we meet an unvisited node, we mark it as visited, search its component, and return the dfs tree. Of course, every node in its component is also marked visited. When we meet a visited node, we just do nothing. The procedure is better described by pseudocode:
dfs(x) :
visited[x] = true
for y adjacent to x
if not visited[y] then
add (x,y) to the spanning forest
dfs(y)
construct_spanning_forest() :
for i in all nodes
if not visited[i] then
dfs(i)
This gives the spanning forest in linear time. The rest is the same as Setter’s solution.
A note on DSU’s complexity
There are two tricks that used in DSU to make its complexity O(\alpha(n)) per operation.
The first one is path compression, which we mentioned in Tester’s solution part. The second one is union by rank, which means: when you merge two sets rooted at r_1 and r_2, you should let the final root be the one whose rank is larger; and the rank is something similar to depth. You can find detailed explanation here.
If you only use path compression, or you only use union by rank, the complexity should be O(\log n) per operation. The implementation in this editorial only uses path compression, so its complexity is actually O(M\log N).
However, in practice, people usually only implements path compression. The reason is that for most cases, path compression performs already quite fast. In fact, as pointed by the Author, the complexity of path compression with randomized union is O(\alpha(n)) per operation, and many data can be seen as random data for DSU. See this paper for more details.
ALTERNATIVE SOLUTION:
As you can see, there are many approaches to tackle the problem.
So if your solution is different with ours, feel free to leave a comment 
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.(NOTE: This gets WA)
Tester’s solution can be found here.
Editorialist’s solution can be found here.
RELATED PROBLEMS:
-
CEOI1999 Parity DSU with parity.
. But I must say, I learnt a lot of terminologies from editorial. Reminds me that I still have a long way to go…