Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 046 Cele mai apropiate puncte din plan  (Citit de 8343 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« : Februarie 27, 2010, 19:42:15 »

Aici puteţi discuta despre problema Cele mai apropiate puncte din plan.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Bogdan_tmm
De-al casei
***

Karma: 4
Deconectat Deconectat

Mesaje: 122



Vezi Profilul
« Răspunde #1 : Martie 05, 2010, 02:26:59 »

Cred ca testele nu sunt chiar foarte bune.
Cu solutia gresita am reusit sa scot cel mai bun timp de pana acum.
Iata un exemplu:

Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #2 : Martie 05, 2010, 15:27:31 »

Cred ca testele nu sunt chiar foarte bune.
Cu solutia gresita am reusit sa scot cel mai bun timp de pana acum.
Iata un exemplu: ...

Nu am înţeles ce faci. Reformulează, te rog.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Bogdan_tmm
De-al casei
***

Karma: 4
Deconectat Deconectat

Mesaje: 122



Vezi Profilul
« Răspunde #3 : Martie 05, 2010, 15:48:02 »

Sa zicem ca punctul 9 va fi mijlocul cand se revine din apeluri.
Acum incerc sa caut distanta minima intre punctele de indici
2 3 4 ... 9...15 16, deci nu o sa gasesc minimul,acesta fiind intre punctul 1 si 17.
Distantele pe verticala intre punctele 1-2 2-3 ... 7-8 este MARE.La fel si distanta intre 10-11 11-12 ...16-17 iar mijlocul(punctul 9) se afla la o distanta destul de MARE de (sa zicem) punctul 10.
Cod:
for(i=mj;i>=st&&i>=mj-7&&a[mj].x-a[i].x<=MIN;i--);
for(j=mj;j<=dr&&j<=mj+7&&a[j].x-a[mj].x<=MIN;j++);
for(i1=i+1;i1<j;i1++)
for(j1=i1+1;j1<=j;j1++)
Min=min(Min,dst(i1,j1));
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #4 : Iulie 21, 2010, 12:04:34 »

Nu putem mai simlu sa avem doua siruri, unul sortat dupa abscisa si celalalt dupa ordonata? Il impartim in jumatati pe cel sortat dupa abscisa si cand revenim dintr-o recursivitate (dintr-o impartire), cautam in sirul sortat dupa ordonata toate punctele care sunt la distanta maxim S de locul de impartire si le punem in sirul Y. Am avea tot complexitate N * log2n. log2n submultimi care le injumatatim si pentru care vom face N pasi sa construim sirul Y si apoi inca N pasi sa parcurgem sirul Y. Deci O(2 * N * log2n) = O(N * log2n).

_____________________________________________

Am mai reparat ceva, dar tot nu suficient. Puteti pune si voi teste mai mici? Nici nu stiu de ce mai sunt publice daca pe testul 1 ai 1000 pct, pe testul 2 1000, pe 3 10000 etc... Nu poti face debug cu asa un test.

_____________________________________________

Si de ce n-ar fi inca 5 pcte de luat pt fiecare (6 in total)? Cele de pe dreapta de impartire n-ar fi comune?
« Ultima modificare: Septembrie 25, 2010, 13:16:52 de către Alexandru Caragicu » Memorat
zsee
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 6



Vezi Profilul
« Răspunde #5 : Noiembrie 17, 2010, 21:06:26 »

Imi poate spune cineva care e problema in sortarea in sursa asta?  Huh
http://infoarena.ro/job_detail/502112

Sunt sigur ca acolo e problema ca cu shellsort imi iese, dar nu intra in timp la ultimele teste... http://infoarena.ro/job_detail/502111  Very Happy si combinand cele doua tipuri de sortare iau 100 de pct... http://infoarena.ro/job_detail/502113
Memorat
BuRN
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #6 : Martie 12, 2011, 18:00:38 »

in sursa http://infoarena.ro/job_detail/552639?action=view-source cazul in care minimul este in partea stanga sau dreapta nu l-am tratat ... doar cel in care un punct este in stanga si unul in dreapta dreptei "D" .
 Am luat 100p. , inseamna ca nu sunt teste cu minimul in stanga/dreapta ?
Memorat
batista
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #7 : Aprilie 06, 2012, 21:48:22 »

Salut!
Am vazut surse care iau 100 chiar daca nu sunt corecte.
Cred ca ar trebui pus si testul:
9
0 0
0 3
0 6
0 9
0 12
0 15
0 18
0 21
0 1
Read This!
Multe surse care iau intotdeauna cele mai apropiate 8 puncte sortate dupa x iau 100 de puncte!
Memorat
moraru.c
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #8 : Mai 19, 2012, 19:50:40 »

am si eu o intrebare...acest algoritm se poate executa in paralel folosind functii din libraria OpenMP?? Very Happy
Memorat
Bogdan_tmm
De-al casei
***

Karma: 4
Deconectat Deconectat

Mesaje: 122



Vezi Profilul
« Răspunde #9 : Mai 22, 2012, 23:07:52 »

Nu stiu exact in ce consta acea librarie, insa cu siguranta poate fi paralelizat deoarece fiecare subproblema poate fi rezolvata independent...
Memorat
retrograd
Client obisnuit
**

Karma: 3
Deconectat Deconectat

Mesaje: 50



Vezi Profilul
« Răspunde #10 : Iunie 22, 2015, 17:13:46 »

Salut! Am luat 100 de puncte cu un algoritm care nu are complexitatea nici pe departe NlogN. Cred ca testele ar trebui revizuite, desi realizez ca e destul de greu sa se combata asa o solutie...

Codul este f simplu. Practic indexez punctele dupa abscisa si ordonata, si ma opresc cand diferenta de abscise/ordonate depaseste dmin:

http://www.infoarena.ro/job_detail/1453063?action=view-source

Se pare ca nu va trebui sa implementez solutia D&C pana la urma...  Whistle
Memorat
AlexandruValeanu
Vorbaret
****

Karma: 29
Deconectat Deconectat

Mesaje: 167



Vezi Profilul
« Răspunde #11 : Iunie 22, 2015, 19:32:14 »

Se pare că va trebui să implementezi "solutia D&C" dacă vrei să înveți ceva.

P.S. Poți reface chiar tu testele.
Memorat
retrograd
Client obisnuit
**

Karma: 3
Deconectat Deconectat

Mesaje: 50



Vezi Profilul
« Răspunde #12 : Iunie 22, 2015, 20:19:57 »

Se pare că va trebui să implementezi "solutia D&C" dacă vrei să înveți ceva.

P.S. Poți reface chiar tu testele.

Cred ca nu e mare lucru sa se mai adauge doua teste, unul in care toate punctele sunt pe aceeasi verticala si apoi pe aceeasi orizontala. Zic si eu Ok
Memorat
RazvanR104
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 14



Vezi Profilul
« Răspunde #13 : Noiembrie 11, 2016, 00:56:19 »

Am o dilema legata de solutiile postate pentru 100 de puncte.

Linia 39 @ http://www.infoarena.ro/job_detail/383250?action=view-source (are echivalent si in sursa cealalta, de complexitate N * log^2(N))
Cod:
for (int i = st; i < dr; ++ i) if (abs(Y[i].second - X[mid].first) <= best)

Conditia nu ar fi, de fapt:
Cod:
if (1ll * (Y[i].second - X[mid].first) * (Y[i].second - X[mid].first) <= best)

Din cate inteleg, best fiind cea mai mica distanta la patrat, ar trebui sa alegem punctele a caror distanta patrata pe orizontala fata linia verticala este mai mica sau egala cu best.
Avand conditia curenta (cea din sursele oficiale) se mai pastreaza invariantul verificarii a doar 8 puncte consecutive?

Sper sa ma ajute cineva cu o clarificare.
Multumesc mult!

LE: sursa de 100p care foloseste conditia cu distanta patrata: http://www.infoarena.ro/job_detail/1803161?action=view-source
« Ultima modificare: Noiembrie 11, 2016, 01:43:38 de către Razvan-Andrei Ciocoiu » Memorat
Bogdanisar
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 12



Vezi Profilul
« Răspunde #14 : Martie 26, 2017, 12:40:44 »


Din cate inteleg, best fiind cea mai mica distanta la patrat, ar trebui sa alegem punctele a caror distanta patrata pe orizontala fata linia verticala este mai mica sau egala cu best.
Avand conditia curenta (cea din sursele oficiale) se mai pastreaza invariantul verificarii a doar 8 puncte consecutive?


Ai dreptate. Ar trebui sa se aleaga punctele a caror distanta la patrat fata de linia verticala este mai mica sau egala cu best, insa algoritmul de 100p postat ramane corect. El doar face un numar nenecesar de pasi, considerand si unele puncte prea indepartate de linia verticala ca sa se poata obtina cu ele o noua distanta minima.
Banuiesc ca a fost doar o scapare din vedere cand s-a scris sursa.  Smile
Memorat
RazvanR104
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 14



Vezi Profilul
« Răspunde #15 : Aprilie 02, 2017, 23:20:22 »

^ Nu cred ca ramane corect. Ambele surse verifica cate 8 puncte in ordine. Avand distanta setata mai mare, ar trebui verificate mai mult de 8 puncte (nu se mai respecta supozitia din care s-a dedus numarul de 8 puncte).
Memorat
Bogdanisar
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 12



Vezi Profilul
« Răspunde #16 : Aprilie 03, 2017, 17:05:59 »

De fapt, ai dreptate. Algoritmul poate da un raspuns gresit daca se scapa din vedere detaliul cu distanta la patrat.
Am reusit sa fac un test care da gresit pentru sursa oficiala de 100 de puncte

Input:
Cod:
18
-9000 900
-8000 900
-7000 900
-6000 900
-5000 900
-4000 900
-3000 900
-2000 900
0 800
1 1000
9000 900
8000 900
7000 900
6000 900
5000 900
4000 900
3000 900
2000 900

Output corect:
Cod:
200.002500

Output-ul sursei oficiale:
Cod:
1000.000000
Memorat
andreeasin
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #17 : Noiembrie 20, 2017, 20:01:37 »

Am trimis din greseala sursa aceasta
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines