infoarena

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?

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.

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

Si mie mi se pare ciudat ...

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.

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.

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

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?

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)

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.

E sort din stl, merge mai bine, cred

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

Ma refeream in practica

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.

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.

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