Bazaconii

Prima observatie pe care o putem face este ca putem rezolva problema independent pentru fiecare bit al numerelor. Vom numi vecini doua numere din sir daca intre ele exista o relatie prin care este cunoscuta suma lor xor. Daca pentru al i-lea numar din sir setam al j-lea bit 0 stim ca pentru toti vecinii lui i bitul j este fortat la una din cele doua valori posibile (ecuatiile 0 xor x = 0 si 0 xor x = 1 au solutii unice). Acelasi lucru se intampla si daca setam al j-lea bit 0. Odata ce am setat bitii pentru vecinii lui i putem seta si biti pentru vecinii vecinilor lui i si asa mai departe. Practic vom folosi o coada in care vom introduce intai al i-lea numar apoi vom scoate mereu din coada un numar caruia i-am setat bitul si daca vecinii sai nu se afla deja in coada ii vom introduce si pe acestia. Pentru a obtine solutia minim lexicografica vom incerca mereu sa alegem numarul cu indicele cel mai mic care nu a fost deja preprocesat si daca atat 0 cat si 1 furnizeaza o solutie valida vom seta bitul la valoarea 0. La sfarsit mai trebuie sa verificam daca toate conditiile se respecta. Mai simplu decat sa verificam pentru fiecare bit in parte este sa observam ca daca exista solutie, atunci daca fixam un numar din sir pe valoarea 0 va exista si in acest caz o solutie.