infoarena

infoarena - concursuri, probleme, evaluator, articole => Probleme externe => Subiect creat de: abcd efgh din Aprilie 11, 2012, 19:30:57



Titlul: F12 competition
Scris de: abcd efgh din Aprilie 11, 2012, 19:30:57
Buna,
Participa cineva la F12 anul asta ?

http://www.fiicompetition.ro/f2012

Cum vi se par problemele?

aaa da, a inteles careva ce se cere la problema strung?


Titlul: Răspuns: F12 competition
Scris de: Dumitru Andrei Georgian din Aprilie 11, 2012, 19:47:57
Iti cere timpul minim pentru a procesa toate piesele, avand un anumit numar de strunguri la dispozitie si stiind cat de cat timp e nevoie pentru fiecare piesa.


Titlul: Răspuns: F12 competition
Scris de: Sorin Rita din Aprilie 11, 2012, 20:56:49
Nu e cam mare totusi timpu de executie ? O secunda mi se pare destul de mult.


Titlul: Răspuns: F12 competition
Scris de: Simoiu Robert din Aprilie 11, 2012, 20:59:03
Si mie mi se pare ciudat ...


Titlul: Răspuns: F12 competition
Scris de: abcd efgh din Aprilie 11, 2012, 21:00:05
Pana la urma a explicat cineva intr-un sfarsit la FAQ.
Limita de timp e destul de mare, dar oricum problemele de la runda asta is mai usoare decat la precedenta...cred ca au ramas fara idei.


Titlul: Răspuns: F12 competition
Scris de: Sorin Rita din Aprilie 11, 2012, 21:14:03
Pai atunci puteau sa puna limita mai mica sa incurajeze o solutie mai desteapta. In schimb la insule mi se pare cam stransa limita de timp.


Titlul: Răspuns: F12 competition
Scris de: Mihai Calancea din Aprilie 12, 2012, 21:39:05
Am sa va rog sa nu discutati despre probleme in timpul rundei  :). Nu e fair-play.


Titlul: Răspuns: F12 competition
Scris de: abcd efgh din Aprilie 24, 2012, 18:45:13
A rezolvat cineva problema insule cu Algoritmul lui Prim?

Pentru ca mie nu imi intra in timp pe 3 teste. Am facut mai intai o verificare cu un DF sa vad daca graful format e conex.
O(M) + O(MlogN)  < O(MlogM) - solutia comisiei  :-k

De cand bate Kruskal, algoritmul lui Prim?..ma rog pe calculatorul meu imi intra in timp pe toate testele.

A mai patit cineva asa?


Titlul: Răspuns: F12 competition
Scris de: Visan Radu din Aprilie 24, 2012, 19:30:49
Ai pus la socoteala si formarea grafului?


Titlul: Răspuns: F12 competition
Scris de: abcd efgh din Aprilie 24, 2012, 20:47:12
Ai pus la socoteala si formarea grafului?

Formarea grafului e la fel ca in solutia oficiala, de asta nu l-am luat in considerare.

Probabil DF-ul ma trage in jos, dar totusi...e un amarat de O(M)


Titlul: Răspuns: F12 competition
Scris de: Petru Trimbitas din Aprilie 24, 2012, 20:47:52
vezi ca e log*N nu log n pt ca folosesti multimi disjuncte deci kruskal merge mult mai bine decat prim din cate stiu eu :)


Titlul: Răspuns: F12 competition
Scris de: abcd efgh din Aprilie 24, 2012, 20:49:13
vezi ca e log*N nu log n pt ca folosesti multimi disjuncte deci kruskal merge mult mai bine decat prim din cate stiu eu :)
Da, dar sortarea muchiilor folosind quicksort se face in MlogM.


Titlul: Răspuns: F12 competition
Scris de: Petru Trimbitas din Aprilie 24, 2012, 21:05:32
E sort din stl, merge mai bine, cred


Titlul: Răspuns: F12 competition
Scris de: Dragos Oprica din Aprilie 24, 2012, 21:29:34
Orice sortare bazata pe comparatii merge cel mai bine in O (N log N). Asta e limita infeioara, deci si sort-ul din STL merge tot in O (N log N).


Titlul: Răspuns: F12 competition
Scris de: Petru Trimbitas din Aprilie 24, 2012, 21:32:43
Ma refeream in practica


Titlul: Răspuns: F12 competition
Scris de: abcd efgh din Aprilie 24, 2012, 21:45:46
Oricum Prim bate Kruskal, de ex problema APM din arhiva.
Sursele cu Prim sunt mai rapide.
Pe mine m-a tras in jos DF-ul care l-am folosit pentru verificarea conexitatii.
Desi asimptotic solutia cu Prim + DF e mai rapida, in practica , de aceasta data pe anumite teste, s-a dovedit mai lenta.


Titlul: Răspuns: F12 competition
Scris de: Heidelbacher Andrei din Mai 19, 2012, 13:15:22
Salut! Stie cineva cand vom putea uploada problemele la ultima runda de la FII Competition? La upload tot problemele de runda trecuta apar, si maine e ultima zi in care putem trimite sursele. Va multumesc anticipat.


Titlul: Răspuns: F12 competition
Scris de: MciprianM din Mai 20, 2012, 08:16:39
Astia de la FII sunt in vacanta rau de tot...  :yahoo:

Nu-i cunoaste nimeni pe cei de la FII sa le dea un buzz?  :-k

S-au trezit somnorosii...