Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-08-14 08:20:27.
Revizia anterioară   Revizia următoare  

Problema saptamanii - Interclasare (Solutie)

Cosmin
Cosmin Negruseri
14 august 2010

Problema Interclasare a dat ceva bataie de cap membrilor comunitatii infoarena.

Putem rezolva problema folosind 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 log n) 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 solutie este sa parcurgem sirul nostru si sa aplicam trucul anterior fiecaror doua secvente crescatoare consecutive.

Singura rezolvare completa a fost a lui Cosmin Gheorghe. Au mai rezolvat problema uitand de pasul de la memorie O(log (n + m)) la memorie O(n): Mihai Lazari, Stefan Istrate, Daniel Dumitran si Ionut Fechete.

Categorii: potw