infoarena

Aici se pot pune întrebări legate de problema Kgon de la Runda 3 a concursului Algoritmiada 2013.

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.

Cercul are centrul in (0, 0)?

Distantele pot fi mai mari decat circumferinta cercului?

Daca sunt 2 puncte la aceeasi distanta de (0,R), care il consideram?

Punctele sunt sortate?

LE: Pot exista 2 pct cu aceleasi coordonate?

@darren DA
@tibi9874 NU
@dariusdarius Nu pot fi 2 puncte la aceeasi distanta
@repp4radu NU

Distanta de la punctul (0, R) la punctul (-R, 0) se considera aceeasi cu cea de la (0, R) la (R, 0)?

prin subset intelegem submultime?

DA.

@darre NU. Distantele sunt date plecand din punctul (0, R) si mergand in jurul acelor de ceasornic.

Citeste enuntul si raspunsul de mai sus pentru @darren

Pot exista doua puncte intre care sa existe o distanta mai mica de 2 * 10^-5?

Distantele sunt sortate in fisierul de intrare?

Pot exista doua subseturi in solutie care sa difere prin mai putin de K elemente, din cauza preciziei? (daca nu ar exista probleme de precizie asta n-ar trebui sa se intample)

@Gavrila Vlad
Nu pot exista astfel de 2 puncte. Asteapta sa ti se raspunda la o intrebare, nu o pune din nou in speranta ca o sa ti se raspunda mai repede
@Cosmin Rusu
Citeste raspunsurile de mai sus.

Se poate afla un punct in interiorul cercului ?
Punctele se afla doar pe cercul de raza R(nu e specificat clar cine e R)?

R e un numar pe care il citesti din fisierul de intrare. Intrucat tie ti se dau distante pe circumefrinta cercului C((0, 0), R) nu ai cum sa  ai puncte in interior.

Am reformulat intrebarea ca sa se vada din ce cauza o pun, ca sa nu se poata interpreta ca cer informatii despre particularitati ale testelor.

repp4radu a pus mai sus 2 intrebari si i-ai raspuns cu NU

Punctele sunt sortate?
LE: Pot exista 2 pct cu aceleasi coordonate?

nu pentru amandoua?

I-am raspunsul lui @dariusdarius ca nu pot exista 2 puncte in acelasi loc deci nu i-as fi raspuns si lui @repp4radu acelasi lucru.
NU se garanteaza ca punctele sunt date sortate.

Daca raza cercului e 10 si distanta de la (0,10) e 41 inseamna ca punctele ar trebui sa fie: (http://www.quickmath.com/webMathematica3/quickmath/equations/solve/advanced.jsp#c=solve_advancedsolveequations&v1=x%5E2+%2B+y%5E2+%2B+100+-+20y%3D1681&v2=x%0Ay&v3=1)
x = t1
y = sqrt(1681 - t1^2) + 10

sau

x = t1
y = -sqrt(1681 - t1^2) + 10

Daca luam t1 sa zicem 10(ca as nu depaseasca cercul) x = 10 si y = 49, punct ce nu se afla in cerc.

E formulate un pic dubios problema, Dragos.
Citeste cu atentie ce i-a raspuns Budau Adrian lui Rares Buhai ... ( @freak93 -> @darren )

Intrebare:
Numerele sunt date cu mai mult de 5 zecimale in teste?

"Distantele sunt date plecand din punctul (0, R) si mergand in jurul acelor de ceasornic."

@Alex Velea
DA.

Datorita inputului de forma distante, n-ar putea sa existe 2 posibilitati de asezare a primului punct (sub axa si deasupra axei, simetric) in partea stanga? Daca da, pe care il luam?

Citeste toate intrebarile si raspunsurile si enuntul.

Di este intotdeauna mai mic decat 2*Pi*R?

Pentru precizie, ce valoare sugerati sa-i dam lui pi ? (Nu stiu daca puteti sa raspundeti la asta, dar cred ca ar ajuta ) .

2 numere se considera egale daca abs( a-b ) < 10^-5?

@Mihai Ionut Enache DA
@Vlad Costin In biblioteca cmath(sau math.h) se gaseste predefinit pi. Este "M_PI"(ghilimelele sunt doar pentru claritate)
@Alex Velea DA

Mersi mult. Asta a rezolvat tot.

Se putea mai bine de N lg N ?  :?

Cum ati reusit sa scapati de TLE? Eu am rezolvat-o in O(n) cu hashuri?  :)

Poti sa imi detaliezi putin aici sau pe privat ? Am impresia ca puntele trebuiau sortate. Multumesc anticipat.  :)

Eu am luat OK pe testul 7 cu 104 ms, complexitate O(N log N + N). Am sortat si m-am plimbat cu 2 pointeri :)

Am gasit L = PI * R * 2 / k, apoi bagam toate punctele intr-un hash. Adaugam L la punctul de start, pana cand gaseam k puncte sau pana gaseam un punct care nu exista. Daca depaseam circumferinta cercului, o scadeam din distanta curenta.
Aveam 132 ms daca faceam doar citirea.  :)

Eu am scos o(n log n) cu o sortare si cautare binara a termenilor ce fac parte din progresii aritmetice cu ratia (2*pi*r / k). Pe testul 7 am 148ms. Se poate demonstra corectitudinea solutiei in o(n)?

Idem , doar ca am TLE :)).

@ SebiSebi : Ce functie de hashing ai folosit ?

LE : Ma refer la faptul ca aveai de retinut double-uri.

Puteai inmulti numerele double cu 10^7, astfel ti le tineai long long-uri

Am incercat 3 modalitati , insa fara succes. Am pastrat hashing-ul pentru numere reale (cel cu partea fractionala), folsind constanta propusa de Knuth si modulo 10007.

Eu tot nu prea vad cum cu hash.. tot trebuiau sortate numerele pana la urma :|
Daca ai ceva de genul:


(astea sunt distantele, "sa presupunem" ca se poate),
atunci ce faci?

@ Vlad: Poi de la un punct se poate ajunge adugand la unul din set sau se poate iesi din set. Marchezi punctele cand mergi , si nu mai ai de la parcurs din nou. Cred ca ar merge.  ???

Cum ati facut sa intre precizia? Am incercat mai multe modalitati (toate cu cautare binara) pe int si pe reale, cu precizia -5, -6, dar nu mi-a intrat...

Sper ca am inteles ce vrei sa spui. Daca aveam exemplul din enunt , dar in alta ordine :
l = 20.943951
L = 62.83185
Plecam din primul punct, deoarece pe el nu l-am mai "vizitat" pana acum.
Caut punctul 41.887902 + l=62.83185 , care este egal cu circumferinta cercului, deci scad L - > punctul devine 0.
Caut punctul 0 + l = 20.943951, il gasesc -> am gasit trei puncte care formeaza un triunghi echilateral.
Eu am considerat ca nu conteaza ordinea punctelor.

Steve: Eu am facut cu eps 0.000001 si mi-a mers....
Dan Alex: Stai putin, tu la ce te referi cu set? Ala din "#include <set>" ? Daca da, ala e logn (mai mult de fapt).. si nu mai iese o(n) solutia :-?

@ Vlad: Nu set din STL. La puntele din hash. Graba...

LE: Sebi , cred ca e bun rationamentul.

Da, este bun, am luat 40 de puncte cu complexitatea O(n). O sa inlociuesc hash-ul cu o sortare + cautare binara, sa vad cat iau.  :) 

Se poate lua 100 cu sortare + cautare binara, dar si cu sortare + O(N)  :)

OK. Nu ma asteptam sa mearga asa de prost hash-ul, dar se mai intampla.

E buna ideea intr-adevar ... bravo :)
Oricum, cred ca modulo-urile alea mananca o droaie de-a timp (cred ca de la asta ai atatea TLE-uri) :-?