Tema 2, clasele 11-12, anul 2013-2014

From Algopedia
Jump to navigationJump to search

Problema Memorie este o problemă de RMQ, cu câteva diferențe interesante:

  • Nu se cere minimul, ci numărul de elemente distincte. Totuși, și această operație se pretează la RMQ, căci întrunește condiția de asociativitate. Numărul de elemente distincte este cardinalul reuniunii, iar reuniunea este o operație asociativă.
  • Dat fiind că numerele din vector sunt între 1 și 52, putem folosi o variabilă de tip long long pentru a stoca elementele distincte corespunzătoare unei subsecvențe. Vom folosi doar biții 1-52.
  • În aparență, memoria de 2 MB este insuficientă pentru o implementare cu memorie O(n log n). Matricea rară ar avea nevoie de 100.000 * 16 elemente a câte 8 octeți, adică 12.8 MB. Cum ne încadrăm în 2 MB? Metoda este destul de brutală: împărțim vectorul în intervale de câte 8 elemente. Precalculăm răspunsurile pentru intervale în memorie O(n / 8 log (n / 8)), iar porțiunile incomplete de interval le evaluăm din 1 în 1.

Vă reamintesc o metodă mai generală de a testa problemele unde nu timpul este problema, ci memoria:

  • Faceți întâi o implementare consumatoare de memorie. Aceasta se implementează, în general, mult mai ușor și o puteți folosi ca etalon.
  • Scrieți un generator de teste uriașe. Un program C n-ar trebui să vă ia mai mult de 5 minute. În GNU / Linux, puteți face aceasta direct din shell.
  • Acum scrieți implementarea care economisește memorie și asigurați-vă că dă aceleași rezultate ca cea naivă.