Pagini: [1] 2   În jos
  Imprimă  
Ajutor Subiect: Feedback Runda 2  (Citit de 9770 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« : Februarie 09, 2014, 16:04:53 »

Runda 2 tocmai s-a încheiat. Felicitări câștigătorilor! Winner 1st place! Așteptăm ca de obicei feedback-ul și părerile voastre  Smile.
Memorat
Andrei1998
De-al casei
***

Karma: 26
Deconectat Deconectat

Mesaje: 112



Vezi Profilul
« Răspunde #1 : Februarie 09, 2014, 16:09:13 »

Destul de interesanta runda  Smile, sunt curios care era solutia oficiala la plagiat?
Memorat
PetcuIoan
Strain
*

Karma: 72
Deconectat Deconectat

Mesaje: 49



Vezi Profilul
« Răspunde #2 : Februarie 09, 2014, 16:11:15 »

Frumoase problemele, dar ca si data trecuta, ar fi fost mai bine sa avem 5 ore.
Memorat
mathboy
Moderatori infoarena
Nu mai tace
*****

Karma: 150
Deconectat Deconectat

Mesaje: 259



Vezi Profilul
« Răspunde #3 : Februarie 09, 2014, 16:11:35 »

Felicitari pentru o runda reusita si probleme foarte interesante!  Winner 1st place
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #4 : Februarie 09, 2014, 16:12:56 »

Dragute problemele. Felicitari pentru runda ! Applause

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...
Memorat
harababurel
Client obisnuit
**

Karma: 23
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #5 : Februarie 09, 2014, 16:18:23 »

@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)
Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #6 : Februarie 09, 2014, 16:29:40 »

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?
Memorat
Andrei1998
De-al casei
***

Karma: 26
Deconectat Deconectat

Mesaje: 112



Vezi Profilul
« Răspunde #7 : Februarie 09, 2014, 16:31:07 »

Eu nu inteleg cum poti determina un triunghi fara cel putin 3 elemente ale sale. Think
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #8 : Februarie 09, 2014, 16:36:39 »

@ 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.
Memorat
Kira96
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 69



Vezi Profilul
« Răspunde #9 : Februarie 09, 2014, 16:38:43 »

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).
Memorat
harababurel
Client obisnuit
**

Karma: 23
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #10 : Februarie 09, 2014, 16:41:42 »

@vladtarniceru: la mine, un log vine de la sortare, unul de la map-ul in care tin diferentele coordonatelor.
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #11 : Februarie 09, 2014, 16:42:09 »

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?
Memorat
timics
Strain


Karma: 3
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #12 : Februarie 09, 2014, 16:42:36 »

Foarte frumoase toate problemele de la Open, multumiri organizatorilor!
Memorat
visanr
Nu mai tace
*****

Karma: 168
Deconectat Deconectat

Mesaje: 213



Vezi Profilul
« Răspunde #13 : Februarie 09, 2014, 16:43:34 »

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 Smile
Memorat
harababurel
Client obisnuit
**

Karma: 23
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #14 : Februarie 09, 2014, 16:43:57 »

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

Karma: 20
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #15 : Februarie 09, 2014, 16:51:20 »

Probleme frumoase si organizare buna, felicitari! Very Happy Astept solutia oficiala de la Ninja.
Memorat
MKLOL
Strain
*

Karma: 5
Deconectat Deconectat

Mesaje: 25



Vezi Profilul
« Răspunde #16 : Februarie 09, 2014, 17:10:27 »

Foarte frumoase si interesantele problemele. Si organizare foarte buna. Era sa ma afecteze negativ faptul ca nu am putut sa trimit 2 surse  Embarassed.
Memorat
SRadu
Client obisnuit
**

Karma: 31
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #17 : Februarie 09, 2014, 17:18:13 »

Faine problemele. Asteptam cu interes oficiala de la Ninja Smile
Memorat
a_h1926
Echipa infoarena
Nu mai tace
*****

Karma: 317
Deconectat Deconectat

Mesaje: 385



Vezi Profilul
« Răspunde #18 : Februarie 09, 2014, 17:39:48 »

Multumim tuturor pentru aprecieri!

A fost publicat articolul cu solutii.
Memorat
alexalghisi
Strain
*

Karma: 18
Deconectat Deconectat

Mesaje: 47



Vezi Profilul
« Răspunde #19 : Februarie 09, 2014, 19:16:08 »

Frumoasa runda  Applause asteptam solutiile si problemele in arhiva !
Memorat
mugurelionut
De-al casei
***

Karma: 209
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« Răspunde #20 : Februarie 09, 2014, 19:41:22 »

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).
Memorat
caheman
Strain


Karma: 10
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« Răspunde #21 : Februarie 09, 2014, 20:02:34 »

triunghiurile cu punctele (0,0), (0,1), (100,0) si (0,1), (0,2), (100,1) sunt echivalente printr-o translatie
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #22 : Februarie 09, 2014, 20:05:07 »

@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.
« Ultima modificare: Februarie 09, 2014, 22:12:24 de către Mihai Calancea » Memorat
mugurelionut
De-al casei
***

Karma: 209
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« Răspunde #23 : Februarie 09, 2014, 20:30:41 »

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.
Memorat
proflaurian
Client obisnuit
**

Karma: 46
Deconectat Deconectat

Mesaje: 58



Vezi Profilul
« Răspunde #24 : Februarie 09, 2014, 20:43:16 »

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  Smile
« Ultima modificare: Februarie 09, 2014, 21:55:55 de către Panaete Adrian » Memorat
Pagini: [1] 2   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines