Diferente pentru blog/problema-saptamanii-interclasare-solutie intre reviziile #11 si #15

Nu exista diferente intre titluri.

Diferente intre continut:

O abordare ar fi sa folosim metoda divide and conquer. Pentru a rezolva subproblema curenta, putem gasi in timp cel mult liniar mediana celor 2 siruri. Astfel vom avea patru secvente _A1 A2 B1 B2_, unde elementele din _A1_ si _B1_ sunt mai mici decat mediana iar elementele din _A2_ si _B2_ sunt mai mari decat mediana. Trucul principal din problema este cum putem ajunge din starea _A1 A2 B1 B2_ in _A1 B1 A2 B2_ in timp liniar si folosind memorie suplimentara constanta. Pentru asta putem inversa ordinea elementelor din secventa _A2 B1_ ca sa obtinem o secventa _B1' A2'_ unde _B1'_ e secventa _B1_ inversata iar _A2'_ e secventa _A2_ inversata. Apoi putem inversa secventele _B1'_ si _A2'_ pe rand pentru a obtine sirul format din secventele _A1 B1 A2 B2_. Toate elementele din _A2 B2_ sunt mai mari decat elementele din _A1 B1_, deci am obtinut doua subprobleme de lungime _(m + n) / 2_ similare cu problema initiala. Astfel obtinem un algoritm de complexitate _O((n + m) log (n + m))_ ce foloseste memorie suplimentara _O(log (n + m))_. Avem nevoie de memoria suplimentara pentru a tine starea stivei algoritmului recursiv. Pentru a obtine un algoritm ce nu are nevoie de stiva putem sa rezolvam tot timpul probleme si subprobleme ce au dimensiuni egale cu puteri ale lui doi. Alta idee sa parcurgem sirul nostru si sa aplicam trucul anterior fiecaror doua secvente crescatoare consecutive.
E interesant ca problema poate fi rezolvata si in _O(n + m)_ timp si _O(1)_ memorie suplimentara, dar o asemenea rezolvare e mult mai complicata. Daca gasiti o abordare usor de explicat o veti putea publica ca lucrare de cercetare.
 
*Rezolvitori:*
Singura rezolvare completa a fost a lui *Cosmin Gheorghe*. Au mai rezolvat problema fara a face pasul de _O(log (n + m))_ la _O(1)_ memorie *Mihai Lazari*, *Stefan Istrate*, *Daniel Dumitran* si *Ionut Fechete*.
Singura rezolvare completa pe ideea de mai sus a fost a lui *Cosmin Gheorghe*. *Andrei Dragus* a venit cu o solutie in _O((n + m) sqrt(n + m))_. Au mai rezolvat problema fara a face pasul de _O(log (n + m))_ la _O(1)_ memorie *Mihai Lazari*, *Stefan Istrate*, *Daniel Dumitran* si *Ionut Fechete*.
 
*Probleme de inrudite:*

Diferente intre securitate:

private
protected

Diferente intre topic forum:

 
4982