227 Geometrie

[ditzone]

Aici puteţi discuta despre problema Geometrie.

[•gogu]

Cam care-i complexitatea oficiala?
Mie mi-au iesit niste timpi destul de mici cu o solutie destul de ciudata.
O cautare binara care nu-i cautare binara.
P.S. in exemplu geom.out e gol.

[•bogdan2412]

In geom.out ar trebui sa fie 1.000
Cred ca solutia era N^3 folosind statistici de ordine, asa cum au facut-o destui la Bursele Agora... Cu o solutie de genu asta am timpi de 1.10 maxim

Am vazut ca tu aveai 0.10 pe cel mai mare test... ciudat... Esti sigur ca rezolvarea ta e buna sau sunt teste mai proaste?

[•Cosmin]

Testele sunt cu puncte date aleator.

[•gogu]

Sper ca nu ati reevaluat din cauza mea ca am vazut ca mi s-a modificat punctajul la 55.
Metoda mea e relativ simpla si se bazeaza decat pe o groaza de rotatii facute mai cu cap dupa care aflu distanta minima intre 2 drepte paralele cu Ox care sa aiba intre ele cel putin K puncte. Nu prea vad teste pe care abordarea mea sa nu mearga.
Oricum, am mai modificat ceva pe la constante si algoritm si acum merge in 0.05 pe cel mai mare test. 
Puteti sa bagati linistiti N<=5000. 

[ditzone]

Au fost schimbate 2 teste si s-a reevaluat

[•gogu]

Dupa fiecare reevaluare numai mie mi se modifica punctajul.
Le-am rezolvat si pe alea dar am niste timpi mai mari acum.
A trebuit sa fac ceva mai multe rotatii.

[•bogdan2412]

Programu tau are niste randomuri p-acolo sau ce? Cum poate sa ia punctaje asa diferite.. cu WAuri pe aceleasi teste?

[ditzone]

Pai restul au rezolvat-o corect

[•gogu]

Nu folosesc nici un random doar ca am o variabila care cu cat e mai mare cu atat merge mai bine.
Am testat si eu cu mai multe valori, sa vad cum merge.
Daca se modifica testele din nou decat maresc variabila asta putin. 

[•greco]

Pai de ce te miri ca ti se modifica punctajele din moment ce algoritmul tau nu e corect ?

[•gogu]

De unde stiti exact ca programul meu nu e bun?
Algoritmul e unul de aproximare deci nu e 100% corect teoretic insa pe teste aleatoare merge aproape tot timpul bine, cu cat numarul de iteratii e mai mare cu atat sansa sa nu nimeresc solutia tinzand spre 0.
Am lasat sursele cu o cautare mai slaba decat ca sa am timpii mai mici. 
Oricum, algoritmul e destul de ciudat si nu cred ca altcineva l-ar implementa, preferand o abordare in O(N^3) sau chiar O(N^3 log N) deci nu cred ca era cazul sa modificati testele decat pentru sursa mea.

[•Cosmin]

Nu stiu exact ce faci tu ... presupun ca rotesti sistemul de coordonate dupa un unghi alfa si apoi sortezi punctele dupa x, pentru ca apoi sa vezi care e cea mai mica distanta intre 2 drepte verticale ce contin intre ele k puncte. Incercand multe unghiuri alfa dai si peste unul foarte apropiat de cel optim. Chestia e ca solutia oficiala e cat de cat apropiata de a ta, dar ea poate scoate rezultatul cu o precizie mult mai mare decat cea de 3 zecimale ceruta in enunt, cred ca ar merge si sa cer 9 zecimale exacte dupa virgula. Nu sunt sigur daca solutia care am explicat-o inainte poate scoate precizie foarte mare a rezultatului decat marind numarul de unghiuri alese.

[•gogu]

Varianta mea e o cautare asemanatoare cu metoda descrisa de tine dar mult mai eficienta.
Iau o constanta C destul de mare, cam O(N), si consider toate unghiurile de rotatie pi*i/C cu i=0..C. Vad pentru care se obtine minimul si reiau cautarea intre unghiurile pi*(k-1)/C si pi*(k+1)/C. Procedeul asta il continui de cateva ori, pana unghiurile ajung la precizie de vreo 10^-12.
E un fel de cautare binara doar ca in loc sa am doua intervale in care ma pot duce, am C.
Daca am ales C-ul destul de mare as putea sa gasesc rezultatul cu aproape orice precizie dorita.
Nu cred ca s-ar lua mai deloc puncte cu metoda descrisa de tine, decat poate pe testele mici.

[•Cosmin]

Ok, metoda ta poate fi pacalita, de exemplu daca sunt mai multe solutii apropiate (ma gandesc la ceva poligon regulat), dar doar una dintre ele este cea buna. Metoda ta pentru ca are la primul pas precizie mica nu stie care dintre cele n directii e buna, si asa pierde solutia optima ...

[•greco]

De unde stiti exact ca programul meu nu e bun?

...

nu cred ca era cazul sa modificati testele decat pentru sursa mea.

Mie mi-au iesit niste timpi destul de mici cu o solutie destul de ciudata.

---

doar ca am o variabila care cu cat e mai mare cu atat merge mai bine.

Stiu ca solutia ta nu e buna din afirmatiile pe care le-ai facut. Stai calm, nu ti-am cautat sursa (nici nu am de gand sa fac lucrul asta), si nici nu are cineva ceva cu tine... In general nu vanam surse, iar testele se mai schimba pentru simplul fapt ca nu dorim sa se ia punctaje prea mari cu rezolvari care nu ar trebui sa fie bune.
Desigur, intr-un concurs nu am face asta, si e gresit dpv. moral ca cineva sa schimbe teste in functie de cat de bine au mers "plesnelile", mai ales ca uneori poti implementa surse care nu merg intotdeauna, bazandu-te pe faptul ca testele bune sunt greu de generat. Insa la arhiva de probleme, unde clasamentul nu are o miza asa de mare, e bine sa avem teste cat mai bune. Iar faptul ca punctajele concurentilor se modica (a se citi "scad") este o confirmare a faptului ca facem un lucru bun. O solutie "corecta" ar trebui sa mearga pe orice fel de test regulamentar. Nu este preferabil asa si din punctul de vedere al concurentului ?

--------------------------------------------------------------

Later edit: cu toate ca solutia ta este destul de interesanta si cred sincer ca ai fi reusit sa iei cu ea foarte multe puncte la un ONI / baraj, fii totusi constient de faptul ca s-ar fi putut cere outputul sub forma unei fractii ireductibile (de fapt, patratul rezultatului). Problema merge si in aceasta forma, iar in acest caz verificarea rezultatului s-ar face printr-o simpla comparare de fisiere (este posibil).
Asa ca ... nu renunta la asemenea abordari, chiar e util sa gandesti problemele altfel decat o face majoritatea, insa fii constient de faptul ca o comisie pusa pe treaba poate face o chestie de genul asta in concursuri. De exemplu, poti sa te uiti si la problema Mr. ans Mrs. Hamilton de la ultimul warmup UVa, unde rezultatul era afisat sub forma de fractie tocmai pt. a evita simularile si plesnelile. 

Numai bine si spor la treaba ! 

[•gcosmin]

de ce nu se pun acolo niste limite la coordonatele punctelor?
sa se stea omu se ghiceasca : oare o ridicare la patrat intra in int, sau sa bag long long??

[•pauldb]

Care este diferenta dintre solutia oficiala si rezultatul dat, astfel incat acesta sa fie considerat corect?

P.S.: Si eu sunt de parere ca nu strica sa se specifice limitele coordonatelor.

[•Cosmin]

Limitele sunt 0, 2000000000. Cand am propus problema am scris pe forum la ginfo si se pare ca am uitat cand am adus-o aici sa modific enuntul.

[•CezarMocan]

Iau 80 de puncte cu TLE pe testele 16,17,19,20. Fac in N^3 cu statistici de ordine din STL. O idee de optimizare? 

L.E. Solved. Pentru cei care patesc aceeasi chestie: incercati pe cat posibil sa scapati de variabilele de tip double (cu sir de double luam 80 si 90, iar  cand am facut o modificare l-am transformat in long long am luat 100 cu timpi de 2 ori mai buni)

[•Robytzza]

Pentru testul din problema,daca luam dreapta ce trece prin punctele (0,1),(1000,0) si mai ducem o paralela la dreapta prin (0,0) , o sa avem 5 puncte intre paralele si o distanta minima de 0.999. De ce raspusnsul este 1.000 .. ce e gresit in ce am zis?

[•tvlad]

Si mie mi-a dat ca intre dreapta care trece prin (0,1) si (1000,0) si paralela prin (0,0) sunt 4 puncte si distanta dintre ele e 0.999 

[•tudalex]

subscriu la asta si se poate demonstra si matematic (cred), iar noua ni se cer 3 zecimale exacte, nu aproximat la 3 zecimale!!!

[•dutzul]

am o intrebare care nu e legata de problema asta. am postat aici fiindca nam stiut unde.
in spatiul 2d daca inmultesc i*i (ca vectori) ,am gasit pe net ca e egal cu 1;
totusi eu nu intaleg dece adica ma gandesc ca daca inmultesc doi vectori de acelasi tip rezulta tot un vector de acel tip.(adica vectorul 1i )
mersi anticipat.

[•darkseeker]

Ceea ce spui tu se cheama produsul scalar al 2 vectori . Gasesti la acest link http://en.wikipedia.org/wiki/Dot_product detalii despre el .