You are not logged in. Please login at www.codechef.com to post your questions!

×

ANDMAT - Editorial

PROBLEM LINK:

Contest
Practice

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.

This question is marked "community wiki".

asked 21 Jun '15, 22:12

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 30 Jun '15, 15:18

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,680
×184
×97
×47
×19

question asked: 21 Jun '15, 22:12

question was seen: 1,579 times

last updated: 30 Jun '15, 15:18