Maximaler OR-Wert von 2D Array von Bits

Question

Angenommen, es gibt ein 2D-Array (m x n) von Bits.

Zum Beispiel:

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

hier, m = 4, n = 5.

I Flip kann (01 wird, wird 10) die Bits in jeder Zeile. Wenn Sie die Bits in einer bestimmten Zeile spiegeln, spiegeln Sie die Bits .

Mein Ziel ist es, den maximalen Wert OR zwischen einem bestimmten Paar von Zeilen zu erhalten.

Das heißt, wenn das gegebene Paar von Reihen (r1, r2) ist, dann kann ich eine beliebige Anzahl von Zeilen Flip zwischen r1 und r2, und ich soll den maximal möglichen OR Wert aller Zeilen zwischen r1 und r2 finden.

In dem obigen Beispiel (man denke Arrays mit 1 basierten Index), wenn r1 = 1 und r2 = 4, I kann der 1. Reihe Flip zu erhalten. Nun, wenn ich den OR Wert aller Zeilen von 1 bis 4 finde, erhalte ich den Wert 31 als den maximal möglichen Wert OR (es kann andere Lösungen geben).

Auch wäre es schön, die Antwort für (r1, r1) zu berechnen, (r1, r1+1), (r1, r1+2), ..., (r1, r2-1) während das gleiche für (r1,r2) berechnen.

Constraints

1 <= m x n <= 10^6

1 <= r1 <= r2 <= m

Eine einfache würde Brute-Force-Lösung, die eine Zeitkomplexität von O(2^m) haben. Gibt es eine schnellere Möglichkeit, dies zu berechnen?

Answer 1

Da A <= A | B, der Wert einer Zahl A wird nur, wie wir OR mehr Zahlen zu A. steigen

Deshalb können wir binäre Suche verwenden.

Wir können eine Funktion verwenden, um das Maximum zwischen zwei Zeilen zu erhalten und das Ergebnis OR ed als dritte Zeile speichern. Vergleichen Sie dann zwei dieser dritten Zeilen, um eine Zeile auf höherer Ebene zu erhalten, und vergleichen Sie dann zwei dieser Zeilen auf höherer Ebene und so weiter, bis nur noch einer übrig ist.

mit Ihrem Beispiel:

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] 

Und natürlich können Sie Zweige nach Bedarf kürzen, wenn m ist nicht eine Potenz von 2

So würde diese O(m) Zeit. Bedenken Sie, dass es für eine große Anzahl von Zeilen wahrscheinlich keine eindeutigen Lösungen gibt.Mehr als wahrscheinlich wäre das Ergebnis 2^n - 1.

Eine wichtige Optimierung: Wenn m >= n, dann muss der Ausgang 2^n - 1 sein. Nehmen wir an, wir haben zwei Zahlen A und B. Wenn B k Nummer fehlende Bits hat, dann wird garantiert, dass A oder ~A mindestens eines dieser Bits füllt. Mit einem ähnlichen Token, wenn m >= log n, dann muss die Ausgabe auch 2^n - 1 sein, da jede A oder ~A garantiert ist, mindestens die Hälfte der ungefüllten Bits in B zu füllen.

Mit diesen Verknüpfungen können Sie eine Brute-Force-Suche durchführen, wenn Sie möchten. Ich bin nicht 100% der binäre Suchalgorithmus funktioniert in jedem einzelnen Fall.

Answer 2

Betrachtet man das Problem, die Zeilen in der gesamten Matrix umzudrehen und dann zusammenzufassen, um so viele 1s wie möglich zu erhalten, behaupte ich, dass dies möglich ist, wenn die Anzahl der Spalten weniger als 2^m ist die Anzahl der Zeilen Betrachten Sie die Zeilen nacheinander. In Stufe I, die von 0 aus zählt, müssen Sie weniger als 2^(m-i) Nullen füllen. Da beim Umkehren einer Zeile Nullen in Einsen umgewandelt werden und umgekehrt, füllt entweder die aktuelle Zeile oder die umgedrehte Zeile mindestens die Hälfte dieser Nullen aus. Wenn Sie alle Zeilen durchgearbeitet haben, müssen Sie weniger als 1 Nullen füllen, damit diese Prozedur eine perfekte Antwort liefert.

Ich behaupte dies ist erreichbar, wenn die Anzahl der Spalten mindestens 2^m ist, wobei m die Anzahl der Zeilen ist. Es gibt 2^m mögliche Muster von gekippten Zeilen, aber dies ist nur O (N), wobei N die Anzahl der Spalten ist. Wenn Sie also alle möglichen Muster von gekippten Zeilen ausprobieren, erhalten Sie in diesem Fall einen O (N^2) -Algorithmus.