Solutia problemei Tygyn
Solutia este bazata pe formarea unui arbore special care contine toate numerele naturale. Vom numi acest arbore special "Arborele Divizorilor". Radacina acestui arbore este nodul 1. Fiecare numar natural mai mare decat 1 poate fi scris ca produs de numere prime. Tatal fiecarui nod este egal cu numarul nodului impartit la cel mai mare numar prim care il divide. De exemplu, 3 * 5 * 5 * 7 il are pe 3 * 5 * 5 ca parinte, in timp ce 2 * 2 * 2 il are pe 2 * 2 ca parinte.
Pentru a intelege aceasta structura, ne putem uita la imaginea din dreapta. Aici este un mic fragment din Arborele Divizorilor. Putem observa ca toate numerele prime il au ca tata pe nodul cu numarul 1, iar adancimea fiecarui nod este egala cu numarul de cate ori trebuie sa impartim acel numar cu un numar prim pentru a ajunge egal cu 1 (suma exponentilor in descompunerea sa in factori primi).
Daca ne uitam cu atentie la Arborele Divizorilor, la proprietatile sale si structura sa, in relatie cu enuntul problemei, observam ca putem face o turma cu toate vacile aflate in subarborele unei vaci existente. Minimizand numarul de turme inseamna sa cream cate o turma pentru fiecare vaca, in afara de cele pentru care avem un stramos deja aflat in arbore. Daca vaca are un stramos aflat in arbore, inseamna ca poate sa fie in aceeasi turma cu acesta. In acest fel, si corectitudinea turmelor, si numarul minim al acestora este respectat.
Sunt multe feluri pentru a implementa acest algoritm. Trebuie, totusi, sa facem o parcurgere a arborelui, deci trebuie sa retinem cel mai mare divizor prim pentru fiecare numar in timp ce vizitam nodurile. Implementarea oficiala foloseste un BFS pe Arborele Divizorilor, marcand in acelasi timp carei turme ii apartine fiecare nod. Datele de intrare sunt usor tratate cu un vector de bool, marcand toate vacile vizitate.
Solutia, de asemenea, necesita cunostinte pentru a afla toate numerele prime pana la M. Putem folosit Ciurul lui Eratostene pentru a le afla, sau ciurul liniar pentru a afla toate numerele prime pana la un anumit numar. Complexitatea finala este O(N + M * log(log(M)) sau O(N + M), depinzand de felul in care ciurul este implementat.
Nota si Multumiri
Multumim lui 
Pentru varianta in engleza a editorialului, vizitati pagina sa
