Problema saptamanii - Initializare (Solutie)
Problema saptamanii curente a fost rezolvata de 13 cititori. Ea nu e asa dificila ca si problemele anterioare, dar e singura de vara asta care are o aplicatie practica.
Rezolvitori:
Andrei Grigorean, Radu Berinde, Andrei-Marius Teodorescu, Delia David, Andrei Dragus, Adrian Carcu, Ovidiu Gheorghioiu, Adrian Vladu, George Nachman, Laura Draghici, Paul Dan Baltescu, Mihai Feier si Mihai Calancea.
Solutie:
Notam umem sirul de U pozitii cu memoria neinitializata. Cum avem nevoie de operatii in timp constant am putea tine 1 sau 0 pe pozitia v din umem daca elementul v este in set sau nu. Din pacate memoria nu este initializata si astfel pot exista deja 0 si 1 prin sir care sa ne pacaleasca.
Pentru a scapa de problemele generate de memoria neinitializata folosim un al doilea sir, nmem, de lungime N ce il initializam pentru a verifica daca umem spune adevarul. La adaugarea unui nou element v in set, dupa ce au fost deja adaugate max elemente, il adaugam in nmem la final si pe pozitia v din umem punem valoarea max. Astfel putem testa daca un element este intradevar in set folosind conditia nmem[umem[v]] == v. Trucul e ca realizam o legatura bidirectionala care este reala pentru ca noi controlam sirul nmem.
Aveti aici niste cod in Python scris de George Nachman pe aceasta idee:
umem = newarray(U)
nmem = newarray(N)
max = 0
def contains(v):
if v >= U:
return False
i = umem[v]
if i >= max:
return False
return nmem[i] == v
def add(v):
if contains(v):
return
umem[v] = max
nmem[max] = v
max += 1