Problema saptamanii curente a fost rezolvata de 13 cititori. Problema nu e asa interesanta ca si problemele anterioare, dar e singura de vara asta care are o aplicatie practica.
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. O solutie pentru a scapa de problemele generate de memoria neinitializata e sa folosim un al doilea sir, nmem, de lungime N ce il initializam pentru a verifica daca umem spune adevarul.
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.
La adaugarea unui nou element v in set dupa ce au fost deja adaugate max elemente, il adaugam la 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.
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:
