Problema saptamanii - Interclasare (Solutie)

Cosmin Negruseri
14 august 2010

Problema Interclasare a dat ceva bataie de cap membrilor comunitatii infoarena. Ma asteptam sa stie lumea ceva mai bine ce inseamna sortare stabila sau memorie suplimentara.

Solutie:

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.

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.

Probleme de inrudite:

1.(CLRS, interviu) Se dau doua siruri sortate de lungime m si n, sa se determine in O(log (n + m)) timp mediana sirului obtinut prin interclasarea celor doua siruri.

2.(interviu Microsoft) Se da un sir de caractere de dimensiune n, sa se roteasca la dreapta cu k pozitii in timp O(n) si folosind memorie suplimentara O(1). De exemplu pentru "abcdef", n = 6, k = 2 trebuie sa obtinem "efabcd".

3.(interviu Microsoft) Se da un sir de caractere ce contine cuvinte separate prin spatii. Se cere sa se inverseze ordinea cuvintelor din sir in timp liniar si folosind memorie suplimentara constanta. De exemplu "Ana are mere" -> "mere are Ana".

4.(interviu Facebook) Se da un sir de obiecte X ce au chei de valori 0 sau 1. Se cere sa se sorteze stabil sirul de obiecte in complexitate mai buna de O(n^2) folosind memorie suplimentara constanta.

5.(Oni 2004) Sortare cu inversari http://infoarena.ro/problema/invsort