Autobuze

Solutia 1: O(N²) - 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.

Solutia 2.1: O(N * sqrt( MAX_VAL )) - 70 puncte Teodor Plop •Teodor94

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.

Solutia 2.2: O(M * log(log M)) + O(N * NR_MAX_DIV) - 100 puncte Teodor Plop •Teodor94

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.

Solutia 3.1: 80 puncte Duta Vlad •Vman

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.

Solutia 3.2: 100 puncte Duta Vlad •Vman

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.

Solutia 4: 100 puncte Heidelbacher Andrei •a_h1926

Putem considera ca fiecare din cele N numere face 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.