|
Titlul: Distante intre doua puncte Scris de: Pripoae Teodor Anton din Iunie 02, 2008, 22:33:23 Cum s-ar face optim (mai putin de n^2 log n) urmatoarea problema ](*,) ?
Deci... Am n puncte in plan, la care se cunosc coordonatele x[ i ] si y[ i ], si se mai cunoaste m[ i ]. Pentru fiecare punct i imi trebuie sa aflu cele mai apropiate m[ i ] puncte de punctul i, si sa afisez si distanta intre ele. Distanta intre a si b este min( | x[ a ] - x[ b ] | , | y[ a ] - y[ b ] | ) +1 Titlul: Răspuns: Distante intre doua puncte Scris de: Andrei Grigorean din Iunie 02, 2008, 22:38:02 Problema asta e compusa de tine? :)
Pai mai bine de N^2 e clar ca nu se poate, nu? Daca m[ i ] = N, oricare ar fi i, trebuie sa afisezi N^2 numere. Poti obtine aceasta complexitate cu radix sort cel mai simplu :). Titlul: Răspuns: Distante intre doua puncte Scris de: Pripoae Teodor Anton din Iunie 02, 2008, 22:47:11 nu. am gasit-o data la rusi la un concurs... in arhiva de probleme a lui mugurel andreica si erau 10000 de puncte si timpul 2 secunde, deci teoretic nu prea merge n^2. oricum nimeni nu a facut problema in concurs :x
https://mail.cs.pub.ro/~mugurel.andreica/task_archive/Russia%20-%20Olympiads/CBOSS%20Cup%20(Russia)%20Contests/CBOSS%20Cup%202004-2005/CBOSS%20Cup%20-%20Volga%20Grand%20Prix%20-%20Rusia%202004/results.htm (https://mail.cs.pub.ro/~mugurel.andreica/task_archive/Russia%20-%20Olympiads/CBOSS%20Cup%20(Russia)%20Contests/CBOSS%20Cup%202004-2005/CBOSS%20Cup%20-%20Volga%20Grand%20Prix%20-%20Rusia%202004/results.htm) Titlul: Răspuns: Distante intre doua puncte Scris de: Andrei Grigorean din Iunie 02, 2008, 22:50:20 Ar trebuie sa intre N^2... nu e asa mult pentru N = 10.000. Oricum, nu se poate mai bine :).
Poate ca rezolvarea oficiala e un smen care optimizeaza mult... cine stie? Titlul: Răspuns: Distante intre doua puncte Scris de: Adrian Diaconu din Iunie 03, 2008, 01:12:41 Iti trebuie toate cele m[ i ] puncte sau doar al m[ i ]-lea ?
Daca iti trebuie doar al m[ i ]-lea poti sa il determini cu statistici de ordine. Este tot O(n2), dar cred ca merge mai repede decat sortare cu radix. Titlul: Răspuns: Distante intre doua puncte Scris de: Gabriel Bitis din Iunie 03, 2008, 07:13:44 Pentru fiecare punct i imi trebuie sa aflu cele mai apropiate m[ i ] puncte de punctul i, si sa afisez si distanta intre ele. De aici eu inteleg ca trebuie toate cele m[ i ] puncte.Titlul: Răspuns: Distante intre doua puncte Scris de: Pripoae Teodor Anton din Iunie 03, 2008, 08:25:03 imi trebuie toate cele m [ i ] puncte
https://mail.cs.pub.ro/~mugurel.andreica/task_archive/Russia%20-%20Olympiads/CBOSS%20Cup%20(Russia)%20Contests/CBOSS%20Cup%202004-2005/CBOSS%20Cup%20-%20Volga%20Grand%20Prix%20-%20Rusia%202004/all.pdf (https://mail.cs.pub.ro/~mugurel.andreica/task_archive/Russia%20-%20Olympiads/CBOSS%20Cup%20(Russia)%20Contests/CBOSS%20Cup%202004-2005/CBOSS%20Cup%20-%20Volga%20Grand%20Prix%20-%20Rusia%202004/all.pdf) e aici problema, e a 4-a (D,road to home) Ma rog, nu imi trebuie sa afisez distanta minima intre cele mai apropiate m[ i ] puncte ci ca se salvez intr-o matrice alocata dinamic pt a afla apoi drumul optim... dar e cam acelasi lucru si cum se poate in n^2? iese pt fiecare i m[ i ] operatii? daca e asa atunci se obtine o( Mmax) unde Mmax este numarul muchiilor, si este mai mic decat 4 milioane deci e ok deci se poate face in m[ i ] pt fiecare i? |