PROBLEM LINK:
Author: Utkarsh Lath
Tester: Istvan Nagy and Praveen and Kevin Atienza
Editorialist: Kevin Atienza
PREREQUISITES:
Maximum-cardinality bipartite matching, bitwise operators
PROBLEM:
Given an N\times N matrix of nonnegative integers, take N numbers from it, each with a distinct row and column from the others. What is the maximum bitwise AND you can get among all choices?
QUICK EXPLANATION:
Let’s call a given number M amenable if there is some choice of N numbers whose bitwise AND “contains” M, i.e. if X is the bitwise AND of the chosen numbers, then every “on” bit of M is also “on” in X.
A number M is amenable if and only if there is a perfect matching in the bipartite graph with N nodes on each side (r_1,\ldots,r_N) and (c_1,\ldots,c_N), where there is an edge from r_i to c_j if and only if A_{i,j} “contains” M. Therefore, checking whether a number is amenable can be done with a O(N^3) bipartite matching algorithm.
To find the answer, we start with M = 0 (which is amenable) and we try to guess its bits from the most-significant to least. Whenever we can include a certain bit and still keep M amenable, we greedily include it. This takes O(\log \max A_{i,j}) iterations at worst.
EXPLANATION:
When you encounter a problem involving bitwise operations, it helps to answer the problem bit by bit. This is because most binary bitwise operations only affect corresponding bits; for instance, the third bits of the operands of a bitwise AND operation has no effect whatsoever on the fifth bit of the result.
Since we want to solve this problem bit by bit, we can try to solve first a simpler version of the problem: we assume that 0 \le A_{i,j} \le 1.
The case 0 \le A_{i,j} \le 1
Since the values of the matrix can only be 0 or 1, the result of the bitwise AND can only be either a 0 or a 1. Since we want to maximize the result, we want to choose all the operands to be 1, if possible. Thus the problem becomes:
Given a binary N\times N matrix, is there a set of N 1 s that have distinct rows and columns?
But this problem is simply a problem of finding a perfect matching in a bipartite graph! Namely, we create 2N nodes, r_1, \ldots, r_N, c_1, \ldots, c_N, where each node represents a row or a column, and there is an edge from r_i to c_j if and only if A_{i,j} = 1. Then the set of N 1 s mentioned in the problem corresponds to a perfect matching in this graph! This problem can be solved in O(N^3) time using many standard algorithms.
Now that we know how to solve the problem if all elements only have one bit, let’s now try solving it when there are two bits.
The case 0 \le A_{i,j} \le 3
This time, the input values have two bits, and the result can now be 0, 1, 2 or 3. Since we want to maximize the result, we first want to ensure that the higher-order bit is on, if possible. But we can answer this easily, because this is just the previous problem! Thus we can know whether the answer has the higher bit on or not in O(N^3). Furthermore, if we discover that it is impossible to ensure that the higher bit is on, then we can ignore the higher bits entirely and focus on the remaining bit, reducing it to the previous problem again.
But what if the higher bit is on? In this case, we know that the answer can only be 2 and 3, and we want it to be a 3 if possible. This means that we want the N numbers to be all 3 s, and we can ignore all other values. But this again reduces the problem to the previous one! Therefore, we can answer this too in O(N^3). Great!
Generalizing the approach
The above approaches actually hint at a correct solution for this problem, so let’s try to inspect why the above approaches work, and why we’re always able to reduce the problem to a series of bipartite matching problems. Since we want to maximize the result, we’re always first checking if the highest bit can be 1, and then whether it is possible or not, we check if it is possible to “add” the next bit, and then the next one, and so on. The key routine that we are using at any point answers the following question:
*Given any bitmask M, is it possible for the answer to be M, or some bitmask that “contains” M? *
(here A “contains” B if and only if every “on” bit of B is also “on” in A)
This can be answered, obviously, by reducing it to the bipartite matching problem like above: Create 2N nodes, r_1, \ldots, r_N, c_1, \ldots, c_N, and add an edge from r_i to c_j if and only if A_{i,j} “contains” M.
So the algorithm is now: For every bit from the most to the least significant, we try to check whether we can include this bit in the answer using this routine. There can be at most \lfloor \log_2 \max A_{i,j} \rfloor + 1 steps and each application runs in O(N^3) time, so the whole algorithm runs in O(N^3 \log \max A_{i,j})!
Time Complexity:
O(N^3 \log \max A_{i,j})
AUTHOR’S AND TESTER’S SOLUTIONS:
Will be posted soon.