Am reusit ( cu greu
) sa rezolv problema de 100 p.
Am o intrebare legata de complexitate.
In rezolvarea oficiala este vorba de o sortare care ridica complexitatea la O(n*log n).
Eu am "numit" aleile cu numere mai mici decat 4*131072=2^19 astfel :
-directia si semnul coordonatei corespunzatoare = 2 biti
-valoarea absoluta a coordonatei modulo 131072 =17 biti
adica am folosit un fel de hasing .
Precizand apoi la fiecare punct pe care alei se gaseste am creat graful intersectiilor si am procedat mai departe ca in sol oficiala.
Intrebarea :
Este aceasta rezolvare de complexitate O(n) sau ma pacalesc eu la ceva ?
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena