Neka je dato \(n\) binarnih brojeva. Koristeći prefiksna stabla pronaći maksimalni broj koji se može dobiti \(XOR\)-ovanjem (ekskluzivna disjunkcija) ovih brojeva.
Sa standarnog ulaza se unosi broj \(n\), a zatim i \(n\) celih brojeva u intervalu \([0, 1000000]\). Svi brojevi se unose u binarnom formatu zapisani sa \(20\) bitova.
Na standardni izlaz ispisati maskimalnu vrednost koju je moguće dobiti \(XOR\)-ovanjem datih \(n\) brojeva. Broj ispisati u binarnom formatu zapisan sa \(20\) bitova.
3 00000000000000000101 00000000000000000000 00000000000000000011
00000000000000000110
Osnovna ideja rešenja je da koristimo prefiksna stabla. Sve brojeve možemo zapisati u binarnom formatu. Prefiks reči (broja) dužine \(i\) je zapravo niz bitova najveće težine zaključno sa pozicijom \(i\). Dodavanje broja u stablo se svodi na dodavanje bitova u grane stabla.
Ideja određivanja maksimalne vrednosti \(XOR\)-a za par vrednosti je da za svaki broj iz skupa nađemo maksimalni \(XOR\) njega i svih drugih brojeva. Ovo možemo uraditi tako što broj prvo dodamo u prefiksno stablo, a zatim tražimo maksimalni \(XOR\) njega i svih ostalih prethodno dodatih vrednosti. Kada postupak ponovimo za poslednji broj iz skupa, imaćemo vrednost maksimalnog \(XOR\)-a za sve vrednosti. Kako nalazimo maksimalnu vrednost \(XOR\)-a za trenutni broj i sve prethodno dodate brojeve?
Nakon što broj dodamo u stablo, kretaćemo se kroz njega bit po bit (počevši od bita najveće težine). Kako je vrednost operacije \(XOR\) za bitove različite vrednosti \(1\), a za bitove iste vrednosti \(0\), mi pokušavamo da se krećemo uvek suporotno od vrednosti trenutnog bita. Dakle, ako je bit do koga smo stigli \(1\), želimo da idemo granom na kojoj se nalazi \(0\) jer na taj način maksimizujemo \(XOR\) (odgovarajući bit \(XOR\)-a će biti \(1\)). Ukoliko grana na kojoj se nalazi bit suprotne vrednosti ne postoji, krećemo se granom na kojoj je bit iste vrednosti i odgovarajući bit operacije \(XOR\) će biti \(0\). Složenost opisanog algoritma je \(O(n \cdot m)\), gde je \(n\) broj brojeva koji se dodaju u stablo, i \(m\) dužina binarne reprezentacije svakog broja. Ukoliko je \(m\) konstanta, složenost algoritma je \(O(n)\).
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
struct Node
{
Node *left = nullptr;
Node *right = nullptr;
};
void add(Node *trie, const string &binary)
{
for (auto b : binary) {
if (b == '0') { // left
if (trie->left == nullptr) // create left
trie->left = new Node();
trie = trie->left; // go left
} else { // right
if (trie->right == nullptr) // create right
trie->right = new Node();
trie = trie->right; // go right
}
}
}
string max_xor(Node *trie, const string &binary)
{
string xor_binary = "";
for (auto b : binary) {
if (b == '0') {
if (trie->right != nullptr) { // try right
xor_binary += '1';
trie = trie->right;
} else {
xor_binary += '0';
trie = trie->left;
}
} else {
if (trie->left != nullptr) { // try left
xor_binary += '1';
trie = trie->left;
} else {
xor_binary += '0';
trie = trie->right;
}
}
}
return xor_binary;
}
void free(Node *trie)
{
if (trie == nullptr) return;
free(trie->left);
free(trie->right);
delete trie;
}
int main(void)
{
int n; cin >> n;
vector<string> numbers(n);
for (int i = 0; i < n; i++) {
cin >> numbers[i];
}
Node *trie = new Node();
auto max_binary = string(20, '0');
for (const auto &bin_num : numbers) {
add(trie, bin_num);
auto xor_binary = max_xor(trie, bin_num);
if (max_binary < xor_binary) {
max_binary = xor_binary;
}
}
cout << max_binary << endl;
free(trie);
return 0;
}