ビットの2D配列の最大OR値

Question

ビットの2次元配列(m x n)があるとします。例えば

：ここ

1 0 0 1 0 
1 0 1 0 0 
1 0 1 1 0 
0 0 0 0 1 

、m = 4、n = 5。

0は1になります。1は0になります。任意の行のビットです。特定の行のビットを反転すると、すべてのビットが反転します。

私の目標は、与えられた行の間に最大ORの値を得ることです。

行の所与の対が(r1, r2)である場合、私はr1とr2間の行の任意の数を反転することができ、そしてIはr1とr2間のすべての行の最大可能OR値を見つけるべきです。

r1 = 1とr2 = 4の場合、上記の例（1から始まるインデックスを持つ配列を考慮）では、最初の行を反転してにすることができます。今、私が1から4までのすべての行のORの値を見つけたら、31の値を最大でORという値にします（他の解決策もあります）。

また、(r1, r1)、(r1, r1+1)、(r1, r1+2)のための答えを計算するためにいいだろう...、(r1, r2-1)(r1,r2)のために同じことを計算しながら。

制約

1 <= m x n <= 10^6

1 <= r1 <= r2 <= m

、単純なブルートフォースソリューションはO(2^m)の時間の複雑さを持っているでしょう。 これを高速に計算する方法はありますか？

Answer 1

はA <= A | Bので、数Aの値が唯一の私たちは、バイナリ検索を使用することができ、

そこでAに我々OR以上の数字として上がるだろう。

2つの行の間の最大値を取得し、ORの結果を3番目の行として保存する関数を使用できます。次に、これらの3つの行のうちの2つを比較してより高いレベルの行を取得し、次にこれらの2つの上位行を比較します。あなたの例を使用して

：

array1 = 1 0 0 1 0 [0] 
     1 0 1 0 0 [1] 
     1 0 1 1 0 [2] 
     0 0 0 0 1 [3] 

array2 = 1 1 0 1 1 <-- [0] | ~[1] 
     1 1 1 1 0 <-- [2] | ~[3] 

array3 = 1 1 1 1 1 <-- [0] | [1] 

そしてmだから、これはO(m)時間になります。2.

の力でないとき、明らかにあなたは、必要に応じて枝を切り捨てることができます。また、多数の行については、固有の解決策がない可能性があることに注意してください。おそらく結果は2^n - 1になります。

：m >= nの場合、出力は2^n - 1である必要があります。 2つの数字AとBがあるとします。Bの数字がkの場合、Aまたは~Aは、これらのビットの少なくとも1つを満たすことが保証されます。同様のトークンでm >= log nの場合、Aまたは~Aは、埋められていないビットの少なくとも半分がBであることが保証されているので、出力も2^n - 1でなければなりません。

これらのショートカットを使用して、必要に応じて無差別に検索することができます。私は100％ではないバイナリ検索アルゴリズムはすべての場合に動作します。

Answer 2

行列全体の行を反転し、それらを一緒にしてできるだけ多くの1を得るという問題を考えると、列の数が2^mより小さい場合、これは扱いやすいと私は主張する。行数行を1つずつ考えてみましょう。 0から数えているステージiでは、満たすべき2 ^（m-i）以下のゼロがあります。行を反転すると0が1に反転し、逆も同様であるため、現在の行または反転された行の少なくとも1つは、それらの0の少なくとも半分を埋め込みます。すべての行を処理した場合は、1より小さい0を入力する必要があります。したがって、この手順では完全な答えが得られることが保証されています。

これは、列数が2^m以上の場合には扱いやすいと主張しています。ここでmは行数です。フリップされた行のパターンは2^m通りありますが、これはO（N）だけです（Nは列の数です）。だから、反転された行のすべての可能なパターンを試してみると、この場合O（N^2）アルゴリズムが得られます。