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.

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.

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)

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?

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.

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?

Sincer au fost destul de ciudate problemele, a doua cel putin...

Prima se rezolva prin dinamica, intr-o complexitate de O(N*K*logN) cred sau ceva de genu. Am vrut sa caut valoarea minima printr-un AIB pe doua dimensiuni, dar nu intra in memoria...asa ca am ramas cu O(N^2*K^2).
A doua problema e un mister.

Daca a rezolvat cineva una din probleme sa ma lumineze si pe mine.

Imi poate da cineva un test mai complex, pentru ca iau 0p si imi ies toate exemplele pe care le dau.

Construiesc APM-ul cu Kruskal si apoi determin maximul de pe drum pana la LCA cu al 2^j - lea stramos.

Sursa : http://infoarena.ro/job_detail/696015?action=view-source

Furnica pleaca de la punctul 1 si face un pas la stanga cu o probabilitate de 1/3 si la dreapta cu 2/3.

P(x) - probabilitatea de a ajunge la punctul 0 (prapastia), daca ne aflam in punctul x

P(x) = (1/3)^x + (2/3) * P(x+1), unde x -> INF

Explicatie : Probabilitatea de a te intoarce la 0 din punctul x este probabilitatea de face x pasi la stanga (cu o probabilitate de (1/3)^x) + probabilitatea de a te intoarce la 0 daca ai ajuns in punctul x+1 ((2/3) * P(x+1));

Inca nu mi-am dat seama cum sa aflu limita, dar implementand aceasta functie se pare ca probabilitatea tinde la 0.42857...

Sper ca am gandit bine si am sa incerc sa aflu cum se calculeaza limita. (Proful meu de mate nu a reusit sa o calculeze  )

Muchiile date pe cele M linii reprezinta (strict) muchiile din APM, sau mai bine zis APM-ul in sine?

Cum as putea lua si eu 100p la problema asta, deoarece primesc doar WA .

 P.S. Am rezolvat-o in O(3^m) si pe campion iau 100p.

 L.E. S-a rezolvat, nu am mers decat atunci cand am folosit afisarea din C++ cu setprecision fixed.

   Am si eu o intrebare. Cum se rezolva problemele de dinamica in 3^n? Trebuie sa imi implementez eu operatiile pentru baza 3  sau le pot folosi cumva pe cele deja existente in C++ pentru baza 2.

   Pana acum nu am gasit nici o rezolvare care sa implementeze un algoritm in 3^n, asa ca nu prea stiu cum sa fac.

   Daca cineva stie vreun tutorial sau are vreo sursa cu o rezolvare de dinamica in 3^n, il rog sa posteze.

Multumesc,
Razvan

Pana la urma a terminat cineva cursul? Cum vi s-a parut, cum v-ati descurcat?

Se mai pot lua 100p la problema asta cu noua limita de timp ?
Pentru ca am parsat citirea, am luat precizia minima si iau 90p.

Imi poate da cineva un test mai mare, ca sa ma verific pana isi revine evaluatorul ?

Evaluatorul e setat bine?
Pentru ca iau 40p cu O(n^2*logn) si cu functia de comparare facuta cum trebuie.

Mie imi da 100p pe infoareana si 0p pe arhiva  (cam ciudat).

Naspa rau codul .