Par koji daje najveći XOR - Rešenje

Rešenje grubom silom podrazumeva da se na svaki par brojeva primeni operacija XOR i da se ispiše maksimum dobijenih rezultata. Složenost ovog pristupa je \(O(n^2)\).

Efikasnije rešenje možemo dobiti primenom naprednih struktura podataka. Pokušajmo da za svaki novi uneti broj efikasno izračunamo najveći broj koji se može dobiti primenom operacije XOR na njega i neki od prethodno unetih brojeva (u rešenju grubom silom, to se dešava u unutrašnjoj petlji). Pokušajmo da taj broj odredimo bit-po-bit i to krenuvši od bitova najveće težine. Na mestu bita najveće težine možemo dobiti 1 ako tekući broj počinje bitom 0 i među ranije učitanim brojevima postoji neki koji počinje bitom 1 ili ako tekući broj počinje bitom 1 i među ranije učitanim brojevima postsoji neki koji počinje bitom 0. U suprotnom, na mestu najveće težine rezultata mora biti bit 0. Nakon određivanja prvog bita, određujemo naredni, ali u slučaju da smo na vodeće mesto rezultata upisali 1, među učitanim niskama zadržavamo samo one koje su na vodećem mestu imali bit suprotan bit vodećem bitu tekućeg broja (u slučaju da smo na vodeće mesto rezultata upisali 0, tada su svi ranije učitani brojevi počinjali istim bitom kojim počinje tekući broj i svi se zadržavaju). Postupak sada ponavljamo za drugi bit, pri čemu razmatramo samo niske koje nisu ranije odbačene.

1001
1010
0110

0010

1001
1010

1001

Pretragu možemo veoma jednostavno organizovati ako sve učitane binarne zapise jedan po jedan upisujemo u prefiksno drvo. Prilikom obrade tekućeg broja, njegove bitove prolazimo sleva nadesno, za svaki bit se spuštajući na naredni nivo drveta. Na svakom nivou drveta, dakle, određujemo jedan bit rezultata. Ako na tekućem nivou postoji grana obeležena bitom suprotnom od tekućeg bita trenutnog broja, spuštamo se njome i u rezultat upisujemo jedinicu, dok se u suprotnom spuštamo granom na kojoj se nalazi bit jednak tekućem bitu trenutnog broja i u rezultat upisujemo nulu. Spuštanjem na naredni nivo drveta ujedno eliminišemo sve one niske koje na odgovarajućem mestu nemaju potreban bit. Ovaj postupak je ilustrovan na slici 1.

Složenost ovog algoritma je \(O(n)\), pri čemu je konstanta jednaka broju bitova kojima se zapisuju brojevi (s obzirom na ograničenja data u zadatku, to je 64).

#include <iostream>

using namespace std;

typedef unsigned long long ull;

struct Cvor {
  Cvor* grane[2];
};

Cvor* noviCvor() {
  Cvor* novi = new Cvor();
  novi->grane[0] = novi->grane[1] = nullptr;
  return novi;
}

void ubaci(Cvor* koren, ull broj) {
  Cvor* cvor = koren;
  ull mask = 1ull << (8*sizeof(ull) - 1);
  while (mask != 0) {
    int bit = (broj & mask) != 0;
    if (cvor->grane[bit] == nullptr)
      cvor->grane[bit] = noviCvor();
    cvor = cvor->grane[bit];
    mask >>= 1;
  }
}

void obrisi(Cvor* koren) {
  if (koren != nullptr) {
    obrisi(koren->grane[0]);
    obrisi(koren->grane[1]);
    delete koren;
  }
}

ull maxXOR(Cvor* koren, ull broj) {
  Cvor* cvor = koren;
  ull rez = 0;
  ull mask = 1ull << (8*sizeof(ull) - 1);
  while (mask != 0) {
    int bit = (broj & mask) != 0;
    if (cvor->grane[!bit] != nullptr) {
      rez = rez | mask;
      cvor = cvor->grane[!bit];
    } else
      cvor = cvor->grane[bit];
    mask >>= 1;
  }
  return rez;
}

int main() {
  int n;
  cin >> n;
  unsigned long long x;
  cin >> x;
  Cvor* koren = noviCvor();
  ubaci(koren, x);
  unsigned long long max = 0;
  for (int i = 1; i < n; i++) {
    cin >> x;
    unsigned long long rez = maxXOR(koren, x);
    if (rez > max)
      max = rez;
    ubaci(koren, x);
  }
  cout << max << endl;
  obrisi(koren);
  return 0;
}