PROBLEM LINK:Setter: Hasan Jaddouh 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
EXPLANATIONFirst 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 Nonzero XOR. For example, we have four vertices $V[i]$ for $1 \leq i \leq 4$. Assuming edges $(V1, V2, w)$, $(V2, V3, x)$, $(V3, V4, y)$ and $(V4, V1, z)$. We can write $V4 = V1 \oplus z$. Then $V3 = V4 \oplus y = V1 \oplus z \oplus y$. $V2 = V3 \oplus x = V1 \oplus x \oplus y \oplus z$. Finally, we have $V1 = V2 \oplus w = V1 \oplus w \oplus x \oplus y \oplus z$. Let us assume $c = w \oplus x \oplus y \oplus z \neq 0$. We get $V1 = V1 \oplus c$ for nonzero $c$. We can see, no valid value of $V1$ exist, contradicting our assumption that valid assignment for $A$ and $B$ exist, or XOR of all values on cycle have nonzero 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(bit1) times$ to $y0 1111\ldots(bit1) 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(bit1) times$ to $y(!b) 1111\ldots(bit1) 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 ComplexityTime 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 Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 13 Dec '18, 15:23
