Bitconnect

Solutie

Construim graful din enunt si facem BFS pe el.

Solutie

Construim un graf cu N + log(N) noduri si ducem muchie de la fiecare nod la bitii activi pe care ii contine. Acum raspunsul la un query va fi distanta in graful acesta dintre cele doua noduri / 2.

Solutie - 100p sau 52, depinde de implementare

Rezolvam pentru inceput cazul in care nu sunt updateuri intre queryuri.
Ne imaginam ca spargem fiecare numar pe biti. Daca la bitul i ducem muchie intre oricare 2 valori care au bitul i setat atunci obtinem o clica si niste noduri izolate.Acum vrem de fapt sa vedem un drum minim daca suprapunem clicile. Pentru asta comprimam clicile si vom avea muchie intre 2 clici cu costul 1 daca exista un numar care sa aiba si bitul primei clici si bitul celei de a doua setat. Acum vrem sa folosim cat mai putine clici pentru ca in fiecare clica de pe drumul intermediar vom schimba valoarea numarul exact o data. Putem demonstra asta prin reducere la absurd: presupunem ca intr-o clica intermediara nu schimbam numarul. Atunci vom avea un lant de clici a-b-c,unde numarul ramane la fel. Inseamna ca numarul are bitul a si bitul b setat(deoarece avem muchie a-b) si bitul b si bitul c setat(deoarece avem muchie b-c). Atunci vom aveam si muchie a-c,deci drumul nu mai este minim. Acum, la un query vrem sa vedem distanta minima de la o clica la care x are bitul setat la o clica la care y are bitul setat. Acum aplicam un BFS pe graf ca sa vedem drumul minim de la o clica de a lui x la o clica de a lui y. Raspunsul va fi distanta + 1. Cazul x = y este unul particular si trebuie trata separat. Astel, un query se rezolva in .
Acum mai trebuie doar sa rezolvam updateurile. Pentru fiecare muchie tinem minte cate numere au ambii biti corespunzatori cliciilor setati si vedem astfel cand trebuie sa o adaugam/scoatem. O optimizare care poate fi folosita pentru a imbunatatii timpi e ca la update/erase sa iei in considerare doar bitii activi ai lui x. Complexitatea updateului : .