|
Titlul: 640 Primar Scris de: Airinei Adrian din Ianuarie 27, 2008, 14:47:19 Aici puteţi discuta despre problema Primar (http://infoarena.ro/problema/primar).
Titlul: Răspuns: 640 Primar Scris de: Bozianu Ana din Ianuarie 31, 2008, 11:03:15 Am reusit ( cu greu #-o ) 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 ? |