Feedback Runda 2

[•klamathix]

Runda 2 tocmai s-a încheiat. Felicitări câștigătorilor! ! AÈ™teptăm ca de obicei feedback-ul È™i părerile voastre  .

[•Andrei1998]

Destul de interesanta runda  , sunt curios care era solutia oficiala la plagiat?

[•PetcuIoan]

Frumoase problemele, dar ca si data trecuta, ar fi fost mai bine sa avem 5 ore.

[•mathboy]

Felicitari pentru o runda reusita si probleme foarte interesante!  

[•danalex97]

Dragute problemele. Felicitari pentru runda !

Cum ati facut ninja ? Eu am incercat o abordare N sqrt N , insa nu am reusit sa finalizez.

@ Andrei Costin: Eu am avut O(N^2 log N). Cred ca ceva de genul e optim...

[•harababurel]

@Alex: La Ninja, poti folosi 2 arbori de intervale + lazy propagation ca sa afli in timp logaritmic, pentru orice interval [a, b], cate lingouri incep undeva in interiorul intervalului, si cate se termina in interval.
Nu stiu sigur cum se pot numara lingourile aflate in intregime intr-un interval dat, pe baza informatiilor furnizate de aint.

La Plagiat am si eu tot O(N*N*logN + N*logN)

[•vladtarniceru]

Eu am N^2 * (hash) la Plagiat.
Sunt curios, i-a intrat cuiva N^3? Eu asa am avut in prima idee si a luat 90 sursa.

PS: De la ce e log-ul vostru din complexitate, sortare?

[•Andrei1998]

Eu nu inteleg cum poti determina un triunghi fara cel putin 3 elemente ale sale.

[•danalex97]

@ Tarniceru: Dap , sortare.

@ Andrei: Eu am pornit de la observatia ca daca am 2 triunghiuri si daca pot sa trasez 3 segmente de la varfurile unui triunghi la altul astfel incat cele 3 segmente sa aiba aceeasi lungime si aceeasi panta atunci triunghiurile respective se pot suprapune.

[•Kira96]

Problemele au fost toate OK pentru 11-12 ca si dificultate, intrucat s-au luat si punctaje maxime  .(felicitari lui Alex Velea si Rares Buhai).

[•harababurel]

@vladtarniceru: la mine, un log vine de la sortare, unul de la map-ul in care tin diferentele coordonatelor.

[•SebiSebi]

La problema Collar am avut complexitatea O(N * nr_divizori), dar nu am reușit sa scap de TLE. Folosesc deque implementat de mana ca sa aflu minimul si maximul pe intervale. A luat cineva 100 cu deque?

[•timics]

Foarte frumoase toate problemele de la Open, multumiri organizatorilor!

[•visanr]

La problema Collar am avut complexitatea O(N * nr_divizori), dar nu am reușit sa scap de TLE. Folosesc deque implementat de mana. A luat cineva 100 cu deque?

Si eu am facut cu deque, aceeasi complexitate, 764 ms maxim

[•harababurel]

@SebiSebi: da, cu dequeul din STL. Cu RMQ se puteau obtine timpi de 3-4 ori mai mici.

[•Mihai22e]

Probleme frumoase si organizare buna, felicitari! Astept solutia oficiala de la Ninja.

[•MKLOL]

Foarte frumoase si interesantele problemele. Si organizare foarte buna. Era sa ma afecteze negativ faptul ca nu am putut sa trimit 2 surse  .

[•SRadu]

Faine problemele. Asteptam cu interes oficiala de la Ninja

[•a_h1926]

Multumim tuturor pentru aprecieri!

A fost publicat articolul cu solutii.

[•alexalghisi]

Frumoasa runda   asteptam solutiile si problemele in arhiva !

[•mugurelionut]

Deci sa inteleg ca solutia oficiala la Plagiat consta in a verifica daca exista cel putin 3 segmente cu aceeasi lungime si aceeasi panta printre cele N*(N-1)/2 segmente avand capetele in cate 2 din cele N puncte?

Daca da, atunci nu cred ca este corecta. Sa consideram urmatorul caz: N=5. Avem 3 puncte cu x=0: (0,0), (0,1) si (0,2), si inca 2 puncte, sa zicem, la x=100: (100,0), (100,1). E clar ca nu exista 2 triunghiuri care sa fie unul translatia celuilalt. Dar exista 3 segmente avand aceeasi lungime si aceeasi panta: segmentele (0,0)-(0,1) , (0,1)-(0,2) si (100,0)-(100,1) (toate segmentele sunt verticale si au lungime 1).

[•caheman]

triunghiurile cu punctele (0,0), (0,1), (100,0) si (0,1), (0,2), (100,1) sunt echivalente printr-o translatie

[•klamathix]

@Mugurel N-am zis că trebuie să fie formate din puncte distincte. Mi se pare că unul din exemple e exact dupa modelul dat de tine.

[•mugurelionut]

triunghiurile cu punctele (0,0), (0,1), (100,0) si (0,1), (0,2), (100,1) sunt echivalente printr-o translatie

Da, asa e. Scuze, nu mi-am dat seama. Am crezut ca pot sa creez un test cu 3 segmente egale ca panta si lungime, dar fara 2 triunghiuri translatate, dar am gresit.

[•proflaurian]

Eu cred ca Mugurel are un pic dreptate in sensul ca solutia e putin exprimata neclar. Sunt sigur ca problema nu e cu solutia in sine ci cu descrierea acesteia. Pe de alta parte eu nu prea inteleg de ce e necesar sa se verifice 3 laturi.

Practic eu pot sa generez toti vectorii cu extremitati in punctele date si sa le stabilesc originea, directia, sensul si lungimea fara sa tin cont de extremitate ( daca am doua puncte A si B vectorul AB e definit de origine - punctul A si coordonate X = XB-XA si Y=YB-YA ) Dupa ce sortez acesti vectori dupa X si apoi dupa Y ei se grupeaza pe vectori egali in sensul geometriei vectoriale ( aceeasi directie lungime si sens i.e. aceleasi coordonate )
Daca doi vectori sunt pe o aceeasi grupa de vectori egali insemana ca din originile lor pleaca doi vectori egali spre alte puncte din configuratie  (un vector e translatatul celuilalt) . Memorez aparitia unei astfel de situatii folosind seturi pentru fiecare punct si punand originile una in setul celeilalte. Daca la un moment dat folosind o alta grupa de vectori egali ar urma sa inserez a doua oara un elemet intr-un set asta ar spune ca apare pentru acea pereche de puncte ( ca origine) o a doua pereche de vectori egali care impreuna cu prima imi determina perechea de triunghiuri care confirma plagiatul. In consecinta pentru determinarea triunghiului nu folosesc deloc a treia latura ci de fapt (in mod indirect ) unghiul dintre primele doua (sau altfel spus directiile primelor doua)

L.E. Am citit eu neatent solutia oficiala. Descrierea este super OK iar ceea ce am scris eu mai sus e cu totul altceva. ( E corect dar nu are nicio legatura cu solutia oficiala)

Pana una alta problema asta are un vot de la mine pe sondajul cu problema preferata la runda 2