Dtcsu

Solutie: 100 puncte Duta Vlad •Vman

Datorita limitei de memorie foarte stransa nu putem decat sa incercam sa impartim fiecare numar pe rand la 2, 3, 5, 7, 11 pana cand nu se mai poate, iar daca rezultatul este 1 atunci numaram solutia. Totusi, daca efectuam aceste calcule pentru fiecare numar din input timpul de executie va fi depasit. Ne trebuie asadar o metoda de respingere rapida a numerelor despre care stim sigur ca nu pot fi de forma ceruta, ramanand sa verificam doar numerele care nu au fost respinse, dar pot fi "false positives".

Pornind de la ideea de Bloom Filter, vom construi o tabela de dispersie (hash) in care vom introduce toate cele 276997 numere din fisierul de intrare, urmand ca pentru restul sa verificam daca functia de hash corespunzatoare returneaza true (posibil candidat) sau false (cu siguranta respins). Totodata avem nevoie de o functie (sau mai multe) de hash care sa asigure o rata de respingere de aproximativ 30-40%. Dat insa faptul ca toate cele 276997 valori sunt cunoscute (chiar daca nu sunt date explicit in enunt, ele pot fi generate foarte usor prin backtracking), putem incerca o multime mai mare de functii de hash, iar apoi vom alege acele functii care au rata de respingere cea mai buna.
Aceasta tehnica are aplicatii in baze de date, filtrarea rapida a rezultatelor, url blacklisting, etc.

Pro Tip: Pentru cei care folosesc STL e important de stiut ca atat containerul set cat si map sunt implementati prin arbori rosu-negru si complexitatea per operatie tinde la log(size). Tabelele de hash sunt implementate in librariile unordered_set, respectiv unordered_map. Totusi, in cazul de fata un bitset ar putea fi o solutie mult mai buna dat fiind ca ne este suficient sa setam un bit per intrare, astfel dimensiunea tabelei crescand considerabil.

P.S. E greu sa gasesti un hash bun!