Feedback Runda 2

[•mugurelionut]

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  

Si eu am facut in concurs ceva mai complicat, care tinea cont de ce puncte sunt extremitatile segmentelor (bineinteles, le sortam si eu dupa DX, DY). Dar nu mi-am dat seama ca e suficient sa existe 3 segmente de panta si lungime egala (altfel spus cu acelasi DX,DY), indiferent care sunt extremitatile lor, pentru ca sa existe un triunghi translatat.

Pe urma, cand am citit solutia oficiala, tot mi s-a parut ca ar putea exista cazuri in care exista 3 segmente de panta si lungime egala, dar nu exista triunghiuri translatate. Bineinteles, gresisem eu...

[•Magnvs]

in timpul concursului eu am scos la plagiat 100 de puncte cu un brut o(n^3) cu kill
faceam un hash (care sa ramana constant dupa translatie) pentru fiecare triunghi al caror tuturor muchii puteau fi obtinute prin translatia altor muchii.
si verificam daca existau 2 hashuri egale.

dar ideea din solutia oficiala mi se pare brilianta

[•Kira96]

In caz ca unii dintre noi nu stiu hash sau notiunea de panta, la problema plagiat puteti folosi si urmatoarea abordare. Translatam fiecare punct in origine, si translatam celelalte puncte fata de acesta, si memoram astfel noile puncte obtinute. Practic , avand un punct (x,y) memorat, noi stim ca avem un segment de la (0,0) la (x,y). De asemenea, memoram pentru fiecare punct translatat, fata de ce punct l-am translatat.Acum, daca avem doua puncte (x1,y1) si (x2,y2) ambele apartinand la cel putin 2 origini diferite, inseamna ca avem solutie. Asta este echivalent cu a avea o pereche de segmente ((0,0) (x1,y1)) si ((0,0),(x2,y2)) ce le regasim in cel putin 2 translatii diferite, deci avem 2 triunghiuri din 2 translatii diferite identice.Acum, pentru a face acest lucru, sortam vectorul punctelor translatate (spre ex. intai dupa x apoi dupa y, conteaza mai putin) si pentru o secventa de puncte identice memoram ca avem o pereche de segmente comune pentru punctele de translatie i si j.Putem face asta cu o matrice m(i)(j)=cate segmente translatate au in comun punctele "de origine" i si j.Aparent abordarea pare un n^3, dar daca m(i)(j) devine 2 la un moment dat inseamna ca avem solutie. Astfel avem complexitate N^2 de la crearea punctelor, N^2log(N) de la sortare, si 2*(N^2) de la aflarea solutiei. Complexitate totala (N^2log(N)) . Nu contrazic cu nimic solutia oficiala, dar pentru participantii din grupe inferioare de varsta notiunea de panta si de hash pot parea straine.

[•S7012MY]

In caz ca unii dintre noi nu stiu hash sau notiunea de panta, la problema plagiat puteti folosi si urmatoarea abordare. Translatam fiecare punct in origine, si translatam celelalte puncte fata de acesta, si memoram astfel noile puncte obtinute. Practic , avand un punct (x,y) memorat, noi stim ca avem un segment de la (0,0) la (x,y). De asemenea, memoram pentru fiecare punct translatat, fata de ce punct l-am translatat.Acum, daca avem doua puncte (x1,y1) si (x2,y2) ambele apartinand la cel putin 2 origini diferite, inseamna ca avem solutie. Asta este echivalent cu a avea o pereche de segmente ((0,0) (x1,y1)) si ((0,0),(x2,y2)) ce le regasim in cel putin 2 translatii diferite, deci avem 2 triunghiuri din 2 translatii diferite identice.Acum, pentru a face acest lucru, sortam vectorul punctelor translatate (spre ex. intai dupa x apoi dupa y, conteaza mai putin) si pentru o secventa de puncte identice memoram ca avem o pereche de segmente comune pentru punctele de translatie i si j.Putem face asta cu o matrice m(i)(j)=cate segmente translatate au in comun punctele "de origine" i si j.Aparent abordarea pare un n^3, dar daca m(i)(j) devine 2 la un moment dat inseamna ca avem solutie. Astfel avem complexitate N^2 de la crearea punctelor, N^2log(N) de la sortare, si 2*(N^2) de la aflarea solutiei. Complexitate totala (N^2log(N)) . Nu contrazic cu nimic solutia oficiala, dar pentru participantii din grupe inferioare de varsta notiunea de panta si de hash pot parea straine.

misto solutia 

[•mugurelionut]

In caz ca unii dintre noi nu stiu hash sau notiunea de panta, la problema plagiat puteti folosi si urmatoarea abordare. Translatam fiecare punct in origine, si translatam celelalte puncte fata de acesta, si memoram astfel noile puncte obtinute. Practic , avand un punct (x,y) memorat, noi stim ca avem un segment de la (0,0) la (x,y). De asemenea, memoram pentru fiecare punct translatat, fata de ce punct l-am translatat.Acum, daca avem doua puncte (x1,y1) si (x2,y2) ambele apartinand la cel putin 2 origini diferite, inseamna ca avem solutie. Asta este echivalent cu a avea o pereche de segmente ((0,0) (x1,y1)) si ((0,0),(x2,y2)) ce le regasim in cel putin 2 translatii diferite, deci avem 2 triunghiuri din 2 translatii diferite identice.Acum, pentru a face acest lucru, sortam vectorul punctelor translatate (spre ex. intai dupa x apoi dupa y, conteaza mai putin) si pentru o secventa de puncte identice memoram ca avem o pereche de segmente comune pentru punctele de translatie i si j.Putem face asta cu o matrice m(i)(j)=cate segmente translatate au in comun punctele "de origine" i si j.Aparent abordarea pare un n^3, dar daca m(i)(j) devine 2 la un moment dat inseamna ca avem solutie. Astfel avem complexitate N^2 de la crearea punctelor, N^2log(N) de la sortare, si 2*(N^2) de la aflarea solutiei. Complexitate totala (N^2log(N)) . Nu contrazic cu nimic solutia oficiala, dar pentru participantii din grupe inferioare de varsta notiunea de panta si de hash pot parea straine.

Da, exact solutia asta am implementat-o si eu in concurs

[•geniucos]

Cand se da update la rating?