h1. FMI No Stress 4 - Solutii

h2. 'Pariuri':problema/pariuri

(toc)*{text-align:center} *Lista de probleme*
* 'Pariuri':fmi-no-stress-4/solutii#pariuri
* 'Beri':fmi-no-stress-4/solutii#beri
* 'Palin3':fmi-no-stress-4/solutii#palin3
* 'Melodii':fmi-no-stress-4/solutii#melodii
* 'Plicuri':fmi-no-stress-4/solutii#plicuri
* 'Camionas':fmi-no-stress-4/solutii#camionas
* 'Frumoasa':fmi-no-stress-4/solutii#frumoasa
* 'Autobuze':fmi-no-stress-4/solutii#autobuze
* 'Dtcsu':fmi-no-stress-4/solutii#dtcsu
* 'Peluza Sud':fmi-no-stress-4/solutii#peluzasud
* 'Peluza Nord':fmi-no-stress-4/solutii#peluzanord

h4. $Solutia 1: O(N * M + MAXT) - 80 puncte$

==include(page="fmi-no-stress-4/solutii/pariuri")==

Avand in vedere ca pentru $80%$ dintre teste, momentele de timp in care se pariaza erau ≤ $10^6^$, puteam retine un vector auxiliar astfel:

==include(page="fmi-no-stress-4/solutii/beri")==

* $s[i]$ = suma de bani castigata in total de catre cei N oameni la momentul de timp $i$

==include(page="fmi-no-stress-4/solutii/palin3")==

Printr-o simpla parcurgere a perechilor de tipul $(timp, bani)$ din fisierul de intrare, vom actualiza suma de bani astfel:

==include(page="fmi-no-stress-4/solutii/melodii")==

* $s[timp] = s[timp] + bani$;

==include(page="fmi-no-stress-4/solutii/plicuri")==

De asemenea, este nevoie sa marcam undeva si momentele de timp in care s-au facut pariuri, pentru a sti exact ce momente de timp sa afisam. Astfel, parcurgand cu un contor $i$ momentele de timp de la $1$ la $10^6^$, daca $i$ este marcat, vom afisa $i$ si $s[i]$.

==include(page="fmi-no-stress-4/solutii/camionas")==

h4. $Solutia 2: O(N * M) - 100 puncte$

==include(page="fmi-no-stress-4/solutii/frumoasa")==

Bazandu-ne pe acelasi principiu ca si cel anterior, constatam ca putem retina o tabela de dispersie / tabela hash pentru toate momentele de timp in care s-a pariat. Pentru fiecare moment de timp vom retine in hash valoarea de bani castigata de cei $N$ oameni. In final, vom afisa doar momentele de timp care exista in hash.

==include(page="fmi-no-stress-4/solutii/autobuze")==

h2. 'Camionas':problema/camionas

==include(page="fmi-no-stress-4/solutii/dtcsu")==

h4. $Solutia 1: O(M * log N) - 100 puncte$

==include(page="fmi-no-stress-4/solutii/peluzasud")==

Basmul poate fi privit ca un graf orientat cu $N$ noduri si $M$ muchii, in care fiecare muchie are o rezistenta si se garanteaza ca exista cel putin un drum intre nodul $1$ si nodul $N$.
Rezistenta unei muchii trebuie marita doar daca aceasta este mai mica strict decat greutatea camionasului. Deci, raspunsul problemei este numarul minim de muchii cu rezistenta strict mai mica decat $G$ prin care este nevoit camionasul sa treaca, mergand din nodul $1$ si oprindu-se in nodul $N$. Astfel, putem atribui costuri muchiilor astfel:

==include(page="fmi-no-stress-4/solutii/peluzanord")==

* O muchie $i$ are costul $1$, daca rezistenta ei este mai mica strict decat greutatea camionasului $(g ~i~ < G)$.
* O muchie $i$ are costul $0$, daca rezistenta ei este mai mare decat greutatea camionasului $(g ~i~ >= G)$.
 
In concluzie, problema se reduce la gasirea drumului de cost minim intre nodul $1$ si nodul N. O solutie este un algoritm de tip Dijkstra.
 
h4. $Solutia 2: O(M + N) - 100 puncte$
 
Bazandu-ne pe aceeasi observatie ca si la solutia anterioara, putem identifica componentele conexe din graful initial, folosind doar muchiile ce au cost $0$. Astfel, putem crea un nou graf, avand ca noduri componentele conexe identificate. Apoi, vom trage muchiile ce au cost $1$ pentru a uni aceste componente conexe intre ele. Deci, problema se reduce acum la gasirea unui drum de lungime minima intre componenta conexa in care se afla nodul $1$ si cea in care se afla nodul $N$. Aceasta lungime minima se gaseste foarte usor cu o parcurgere in latime.
 
h2. 'Autobuze':problema/autobuze
 
h4. $Solutia 1: O(N^2^) - 50 puncte$
 
Vom considera ca cele $N$ numere sunt nodurile unui graf neorientat, iar fiecare nod $i$ o sa aiba valoarea $a[i]$. Initial, graful are $N$ noduri si $0$ muchii. Pentru fiecare nod $i$ de la $1$ la $N$, vom parcurge toate celelalte $N$ noduri, iar cand gasim un nod $j$ care are proprietatea ca $a[i]$ divide $a[j]$ sau viceversa, vom trage o muchie intre aceste doua noduri $i$ si $j$. In momentul acesta, problema se reduce la gasirea numarului de componente conexe existente in acest graf. Acest lucru se poate face liniar cu o parcurgere in adancime / latime.
 
h4. $Solutia 2.1: O(N * sqrt( MAX_VAL )) - 70 puncte$
 
Pe acelasi principiu ca cel al rezolvarii anterioare, putem adauga valoarea tuturor nodurilor intr-o tabela de dispersie / hash, retinand pentru fiecare valoare $a[i]$ adaugata, numarul de ordine al nodului careia ii apartine, si anume $i$. In continuare vom parcurge valorile tuturor celor $N$ noduri si le vom cauta divizorii in hash. Daca gasim un divizor in hash, vom trage muchie intre nodul curent si nodul din hash care are valoarea divizorului gasit. In acest moment, problema se reduce din nou la gasirea numarului de componente conexe ale grafului.
 
h4. $Solutia 2.2: O(M * log(log M)) + O(N * NR_MAX_DIV) - 100 puncte$ ==user(user="Teodor94" type="tiny")==
 
Vom pregenera numerele prime pana la $sqrt(MAX_VAL)$ folosind Ciurul lui Eratosthenes. Vom descompune in factori primi toate valorile celor $N$ noduri. In continuare, vom genera toti divizorii unui numar cu un algoritm de tip backtraking, folosindu-ne de factorii sai primi si exponentii acestora. Astfel, ajungem din nou la ideea solutiei anterioare, continuand rezolvarea in acelasi fel.
 
Complexitatea preprocesarii numerelor prime este $O(M * log(log M))$, unde $M$ este $sqrt(MAX_VAL)$, iar complexitatea efectiva a problemei este $O(N * NR_MAX_DIV)$, unde $NR_MAX_DIV$ este numarul maxim de divizori al unui numar.
 
h4. $Solutia 3.1: 80 puncte$
 
Adaugam toate numerele intr-un hash, retinand pentru fiecare numar pozitia pe care se afla in vector. Vom considera din nou cele $N$ numere ca fiind nodurile grafului. Parcurgem cele $N$ noduri, iar pentru fiecare valoare, ii vom cauta multiplii in hash folosind un algoritm asemanator cu Ciurul lui Eratosthenes, si vom trage muchie intre nodul curent si nodul gasit in hash. Astfel, ajungem din nou la determinarea numarului de componente conexe ale grafului.
 
h4. $Solutia 3.2: 100 puncte$ ==user(user="Vman" type="tiny")==
 
Vom optimiza solutia precedenta. Pentru fiecare nod $i$ din cele $N$, avem doua optiuni:
 
* Ii putem cauta multiplii incepand cu $2 * a[i]$, pana la $MAX_VAL$, mergand din $a[i]$ in $a[i]$.
* Ii putem cauta multiplii printre valorile celor $N$ noduri.
 
Astfel, pentru nodurile $i$ pentru care $MAX_VAL / a[i] < N$, le vom cauta multiplii folosind prima optiune, iar pentru nodurile $i$ pentru care $MAX_VAL / a[i] >= N$, vom folosi cea de-a doua optiune.
 
h4. $Solutia 4: 100 puncte$ ==user(user="a_h1926" type="tiny")==
 
Putem considera ca fiecare din cele $N$ numere fac parte din cate o multime. Astfel, vom avea initial $N$ multimi, fiecare continand cate un element. In continuare vom folosi un algoritm de tipul paduri de multimi disjuncte pentru a uni multimile care au elemente in comun.
 
h2. 'Dtcsu':problema/dtcsu
 
h4. $Solutie: 100 puncte$ ==user(user="Vman" type="tiny")==
 
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 "fals 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!

public

private