Note de curs, clasele 9-10, 15 martie 2013

From Algopedia
Jump to navigationJump to search

Algoritmi pe vectori și matrice

Mulți erau cunoscuți, dar am vrut să mă asigur, căci intervin foarte des.

  • problema majorității: se dă un vector, să se identifice (dacă există) un element care apare de n/2 + 1 ori.
    • soluție O(n): eliminarea numerelor în perechi
    • soluție O(n): găsirea medianului (cu algoritmul de selecție)
    • soluție O(n): construim o tabelă hash care mapează valori la frecvențe
  • MSW (minimum over a sliding window): se dă un vector, să se tipărească min(v[i], v[i + 1], ..., v[i + k - 1]) pentru fiecare i = 0, 1, ..., n - k
    • soluție O(n) amortizat: cu un deque (coadă cu două capete)
    • soluție cu heap: O(n log k)
  • subsecvența de sumă maximă: se dă un vector, să se găsească o subsecvență de sumă maximă
    • soluție O(n): programare dinamică
  • dreptunghiul de sumă maximă
    • naiv O(n6): generăm toate dreptunghiurile în O(n4) și le verificăm în O(n2)
    • soluție O(n4): precalculăm s[i][j] = suma elementelor din dreptunghiul (1, 1) - (i, j)
    • soluție O(n3): pentru fiecare pereche de rânduri i și j, căutăm în O(n) coloanele k și l care ne dau dreptunghiul maxim
      • implică niște precalculări, apoi reducerea la subsecvența de sumă maximă
  • dreptunghiul de sumă maximă de dimensiune p*q
    • soluție O(n2): cu precalcularea unor sume de p elemente pe linie, respectiv q pe coloană
  • maximum gap: se dă un vector nesortat; să se găsească distanța maximă între două elemente consecutive în vectorul sortat
    • soluție O(n): cu principiul cutiei
  • șmenul lui Mars
  • dreptunghiul maximal: se dă o matrice de 0 și 1, să se găsească dreptunghiul de arie maximă care conține doar 0
    • soluție naivă O(n6): generăm toate dreptunghiurile în O(n4) și le verificăm în O(n2)
    • soluție O(n4): precalculăm s[i][j] = suma elementelor din dreptunghiul (1, 1) - (i, j)
    • soluție O(n4): fixăm colțul stânga-sus, apoi pentru fiecare linie numărăm zerourile dinspre dreapta
    • soluție O(n3): idem, dar precalculăm numărul de zerouri dinspre dreapta
    • soluție O(n2): cu o coadă dublă (sau stivă), similar cu problema Skyline / cel mai mare dreptunghi de sub histogramă

Discuții inginerești

  • despre munca la Google, unelte pentru code versioning, unit testing, practici inginerești sănătoase

Temă

  • cel mai mare dreptunghi gol (maximum empty rectangle sau MER): se dă un dreptunghi prin coordonatele sus, jos, stânga, dreapta ale marginilor. În acest dreptunghi sunt n puncte de coordonate reale. Să se găsească aria celui mai mare dreptunghi conținut în primul care să nu aibă niciun punct în interior.
    • căutați o soluție O(n2)
    • are elemente comune cu maximum gap
  • subsecvență de sumă S: se dau un vector și un număr S. Să se găsească o subsecvență (interval continuu) de sumă S
    • căutați o soluție O(n)