F12 competition

[•balakraz94]

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?

[•Schumi]

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.

[•soriyn]

Nu e cam mare totusi timpu de executie ? O secunda mi se pare destul de mult.

[•SpiderMan]

Si mie mi se pare ciudat ...

[•balakraz94]

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.

[•soriyn]

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.

[•klamathix]

Am sa va rog sa nu discutati despre probleme in timpul rundei  . Nu e fair-play.

[•balakraz94]

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 

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

A mai patit cineva asa?

[•visanr]

Ai pus la socoteala si formarea grafului?

[•balakraz94]

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)

[•S7012MY]

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

[•balakraz94]

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.

[•S7012MY]

E sort din stl, merge mai bine, cred

[•DraStiK]

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

[•S7012MY]

Ma refeream in practica

[•balakraz94]

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.

[•a_h1926]

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.

[•MciprianM]

Astia de la FII sunt in vacanta rau de tot...  

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

S-au trezit somnorosii...