PROBLEM LINK:
Setter: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Taranpreet Singh
DIFFICULTY:
Medium
PREREQUISITES:
Backtracking, Connected Components in Graph, Constructive Algorithms and Bitwise Algorithms.
PROBLEM:
Suppose we have two arrays A of length N and B of length M. Consider matrix C defined by C[i][j] = A[i] \oplus B[j].
We are given matrix C with some elements missing and minimum and maximum values for each value of arrays A and B, find out any possible arrays A and B or determine that no solution exist.
QUICK EXPLANATION
- Find connected components in graph formed by N+M vertices each representing a position in array A or B and all edges (i, j) where C[i][j] \neq -1. If there’s any cycle with non-zero XOR of all edges of the cycle, we don’t have any solution.
- After that, Let us build the arrays A and B from most significant bit to least significant. Values of positions in each component are uniquely defined if any one value is fixed. If at any point, we are not able to assign neither 0 nor 1 to the fixed position, we backtrack.
- We check if it’s possible to assign any bit to current bit, by checking for all nodes in the connected component if assigning this bit to fixed position won’t cause current position value to be outside the specified range.
- If we are able to assign values till the last bit, we can assign values to nodes of the current connected component. The answer is yes if we are able to assign values to all connected components. If an answer exists, we can just take the bits assigned to all bits for each connected components and xor it with all positions in the connected component to get possible A and B arrays.
EXPLANATION
First of all, forget about range constraints. We are given a partially filled matrix C and we want to find any valid A and B arrays exist or determine that they don’t exist.
Let us build a graph with N+M nodes, first N nodes corresponding to elements of array A while next M nodes corresponding to nodes of array B. For every position (i, j) in C such that C[i][j] \neq -1 add an edge (i,j,C[i][j]) between node i and node N+j with value C[i][j].
Lemma: If any valid values of A and B exist, All cycles in the graph generated as above by C matrix shall have XOR of all values in the cycle as zero.
Proof: Let us assume that a valid assignment of A and B exist, and we have a cycle having Non-zero XOR. For example, we have four vertices V[i] for 1 \leq i \leq 4. Assuming edges (V[1], V[2], w), (V[2], V[3], x), (V[3], V[4], y) and (V[4], V[1], z). We can write V[4] = V[1] \oplus z. Then V[3] = V[4] \oplus y = V[1] \oplus z \oplus y. V[2] = V[3] \oplus x = V[1] \oplus x \oplus y \oplus z. Finally, we have V[1] = V[2] \oplus w = V[1] \oplus w \oplus x \oplus y \oplus z.
Let us assume c = w \oplus x \oplus y \oplus z \neq 0. We get V[1] = V[1] \oplus c for non-zero c. We can see, no valid value of V[1] exist, contradicting our assumption that valid assignment for A and B exist, or XOR of all values on cycle have non-zero XOR.
Hence, If a valid assignment of A and B exist, All cycles have XOR of all values on cycle as zero only.
Another thing we can see is that we can separately solve each connected component.
Coming back to the original problem now.
Now, We have a connected component, with constraints on the minimum and maximum value of each node. We know, If a single element in connected component gets assigned a value, remaining nodes are automatically assigned values by moving over the path from the assigned node to other nodes. We try to calculate this value.
Let us choose any node in the connected component. We try to assign it values such that no node in component violate range restriction. Let us do this bit by bit, from most significant bit to least significant bit.
We shall keep separate temp intervals for all nodes (initially (0, 2^{30}-1)) so that if we are trying to assign values for ith bit, left end and the right end of interval shall have same bits for all bits significant than the ith bit.
This way, At every step, we shall have two choices, on bit or off bit. Since all intervals have bits significant than ith bit same, They can differ only in the ith bit. Consider we have LE and RI as minimum and the maximum value of position x while processing an ith bit. Suppose, we want to assign off bit to the current bit. Take a number y such that all bits of le significant that ith bit are same in y, and lower bits are all off bits. So, If we assign off bit, value at current position shall lie between y0 000\ldots(bit-1) times to y0 1111\ldots(bit-1) times. If this interval has any position common with the interval [LE, RI], we can assign this bit. We perform this check for all nodes while taking care of xor.
Taking care of XOR
Suppose we are assigning bits to the value of node x, and are performing the check for node y where x and y belong to the same component. So, If ith bit of XOR on path from node x to node y is set bit, our check intervals become y(!b) 000\ldots(bit-1) times to y(!b) 1111\ldots(bit-1) times if assign bit b to node x. This way, we have checked for all nodes in the component if all nodes allow assigning bit b to node x or not.
Now, all that left is to update temp intervals and move to the lower bit. We can repeat the same procedure and if we are able to assign values at bit 0 too, we have found the solution. Also, At this stage, left ends and right ends of our temporary intervals shall coincide and will be the values of arrays A and B.
In some cases, where we are able to assign both bits, we shall turn by turn try both bits. If we find the solution of either of them, we return that solution, otherwise, we backtrack to assign opposite bit. If the solution not found for either bit, we backtrack to parent.
This way, If any valid assignment exists, we shall get that assignment automatically in our temporary intervals. If we do not get them, no valid solution exists.
Optimisation
Although the above solution passes all tests, it can be further optimized by performing another pruning while backtracking. The pruning is, that if any node in connected component have interval coinciding with the temp intervals we made, we don’t necessarily need to check them again for lower bits.
This optimization greatly reduces the complexity to a constant factor of 30*(N+M) because, either the intervals allow both bits to be assigned to the current bit. Then recursing to lower bit shall make one end of temp interval to be same or stricter than the input range restrictions. This means, that when recursing further, we are required to check lesser positions, only those position, which still may restrict our choice to assign lower bits.
In the case nodes are not getting deleted, these would probably won’t allow us to choose lower bits, reducing running time.
Time Complexity
Time complexity, with additional optimization, can be proven to be O(B*(N+M)*C) except for N*M input, where B = 30 is the number of bits to be assigned and C is the constant factor.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 