Problema saptamanii - Initializare (Solutie)

[•Cosmin]

Comentarii la http://infoarena.ro/blog/problema-saptamanii-initializare-solutie

[•MciprianM]

M-am gandit si eu la aceasta solutie, dar nu mi s-a parut ok. Pe aceasta structura de date trebuie sa se execute operatii "de initializare, adaugare si verificare a incluziunii" in timp constant cu O(n) memorie aditionala. Daca primim doar un sir de astfel de operatii nu o sa stim numarul final n de elemente. Si astfel nu stim cata memorie trebuie sa alocam pentru vectorul nostru. Si nu putem sa alocam memorie pe masura ce adaugam elemente la sirul nostru, cum e, de exemplu la vector din stl ( in c++ ), pentru ca, din cate stiu eu, asta e O(1) amortizat. Liste nu putem sa folosim, pentru ca avem nevoie de indexare. Gresesc undeva?
L.E.: Nu stiu in Python cum sunt implementate array-urile alea.
L.L.E.: Acuma am vazut ca se presupune stiut numarul de elemente adaugat de dinainte. Nasol. 

[•raduberinde]

Ciprian,

Daca stim ca o sa fie maxim N elemente in structure la orice moment de timp, se poate tine o lista inlantuita de locuri nefolosite in storageu nostru de lungime N. Poate fi implementat foarte simplu, nmem e urmatorul element liber din lista daca i e liber, si mai tii undeva doar capul listei. La inceput toate elementele sunt libere deci nmem = i+1 (de exemplu).

Daca nu stim nici N-ul asta, incepem cu un nmem mic si cand se umple, mai alocam inca pe-atat (dublam de fiecare data marimea alocata).

[•raduberinde]

A, scuze, problema e ca nu are voie sa fie amortizat. Interesant..

Am putea in loc sa folosim memorie suplimentara, sa folosim tot memoria in care incap U intregi.

Presupunem ca intregii din uvec sunt destul de mari, sa zicem cel putin max[log(2N)+1, log(U)+1] biti, deci pot tine numere de la -2N la +2N sau de la -U la U.

Tinem max ca la solutia initiala.

Intregul i e in multime daca:

Cod:

* i < max si uvec[i] este negativ 
sau
* i >= max si 0 <= uvec[i] < max si abs(uvec[uvec[i]]) = i

Deci ideea e ca folosim primii max intregi ca storage, si mai folosim un bit (semnul negativ) pentru numerele din zona asta.

Inserare:

Cod:

* daca i < max:  uvec[i] = -abs(uvec[i])
* daca i >= max: 
   - flag = contains(max)    // verificarea de mai sus, O(1)
   - uvec[max] = i; uvec[i] = max;
   - daca flag sau (i == max): uvec[max] = - uvec[max]
   - max = max +1

[•MciprianM]

Multumesc de raspuns(uri). Dar mi se pare ca e o problema in codul tau ( al doilea post ). Eu am presupus ca uvec e zona de memorie data in enuntul problemei, ca la inceputul rularii algoritmului tau max e egal cu 0 si ca presupunerea facuta de tine legata de marimea intregilor tine de marimea intregilor care pot fi memorati in zona de memorie, iar nu de marimea intregilor care vor fi inserati/testati de apartenenta(astia incep de la 0 si se duc pana la U-1) si ca i din algoritm e intregul care e inserat sau testat daca apartine multimii. Apoi am testat algoritmul tau pe urmatorul set de date de intrare:

Cod:

insereaza 2
insereaza 3
insereaza 4
test 3
test 4
test 2

Si nu mi-a dat prea bine... Instructiunea test x testeaza daca x a fost adaugat in multime.
Sper ca nu am gresit cand am "rulat" algoritmul.
Si legat de ideea de a folosi faptul ca nu se specifica dimensiunea intregilor care pot fi memorati in zona de memorie data sa stii ca nu prea imi "place"-dar asta e legat strict de preferinte. As fi interesat sa vad un algoritm care accepta si urmatoarea restrictie: intregii memorati in zona de memorie sa fie in intervalul inchis [0,U-1] sau macar zona de memorie sa fie continua si sa contina U bucati de cate 1+[log (U-1)] biti. Si [y]=parte intreaga din y. Nu merge cu x.

[•raduberinde]

Fie ca iti "place" sau nu, in practica marimea numerelor nu e o problema cand e vorba de un singur bit in plus (de exemplu daca avem U numere pe 32 de biti, va fi mai mult decat suficient in aproape orice situatie).

Cand expui un contraexemplu, spune exact ce nu iti da bine, si eventual problema algoritmului pe care crezi ca ai gasit-o.

Eu unul nu vad problema. Presupunerile pe care le-ai facut sunt corecte. Dupa insertii vom avea
max = 3
uvec[0] = 2, uvec[1] = 3, uvec[2] = -4
uvec[3] = 1, uvec[4] = 2

test 3: 3 >= max si uvec[3] = 1, abs(uvec[1]) = 3 deci DA
test 4: 4 >= max si uvec[4] = 2, abs(uvec[2]) = 4 deci DA
test 2: 2 < max si uvec[2] este negativ, deci DA

[•raduberinde]

Inca o idee: in loc sa folosim cate un numar pentru cele <max> valori, putem folosi grupuri de numere.
De exemplu, daca stim ca U > 2N, putem sa folosim cate doua numere:

Atunci de exemplu uvec[0] si uvec[1] au cate un bit rezervat sa arate daca 0 respectiv 1 sunt in multime (sa zicem semnele), si apoi raman 2logU-2 biti pe care putem sa-i folosim ca primul numar din "lista" noastra. Deci

Cod:

extra_storage(i) = abs(uvec[2*i]) * U + abs(uvec[2*i+1])

test(i) = DA daca:
* i < 2*max si uvec[i] < 0
* i >= 2*max si 0 <= uvec[i] < max si extra_storage(uvec[i]) = i

inserare(i): 
daca i < 2*max, uvec[i] = -abs(uvec[i])
daca i >= 2*max:
* flag1 = test(2*max)
* flag2 = test(2*max+1)
* uvec[2*max] = i / U
* uvec[2*max+1] = i % U
* daca flag1 sau (i == 2*max) atunci u[2*max] = - u[2*max]
* daca flag2 sau (i == 2*max+1) atunci u[2*max+1] = -u[2*max+1]

Deci atata timp cat 2N < U, ne ajung numere de max(logN, logU/2+1) biti.

[•MciprianM]

Scuze ca nu am spus care e problema la algoritmul acela: dupa rulare uvec[2] va fi +4 in loc de -4.
Se pare ca gresisem. Verificam daca multimea il contine pe i in loc de max in linia a treia de la inserare.