infoarena

Runda 2 tocmai s-a încheiat. Felicitări câștigătorilor! (http://www.infoarena.ro/algoritmiada-2014/runda-2/clasament/5-8) :winner1:! AÈ™teptăm ca de obicei feedback-ul È™i părerile voastre  :).

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

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

Felicitari pentru o runda reusita si probleme foarte interesante!  :winner1:

Dragute problemele. Felicitari pentru runda ! =D>

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...

@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)

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?

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

@ 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.

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

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

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?

Foarte frumoase toate problemele de la Open, multumiri organizatorilor!

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

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

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

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

Faine problemele. Asteptam cu interes oficiala de la Ninja :)

Multumim tuturor pentru aprecieri!

A fost publicat articolul cu solutii (http://www.infoarena.ro/algoritmiada-2014/runda-2/solutii).

Frumoasa runda  =D> asteptam solutiile si problemele in arhiva !

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).

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

@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.

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.

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...

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 :o

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  =D>

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

Cand se da update la rating?  :?