Pagini: 1 [2] 3   În jos
  Imprimă  
Ajutor Subiect: 026 Arbore partial de cost minim  (Citit de 25722 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #25 : Martie 18, 2011, 15:29:33 »

Se poate face si arbore partial de cost maxim tot asa? (de ex la Kruskal sortezi descrescator in loc de crescator)

Cred ca da.
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #26 : Martie 18, 2011, 16:34:31 »

Mie-mi crapa sort-ul din stl?!? Desi i-am dat domeniul de sortare corect? Crapa in STL.
Memorat
skull
Client obisnuit
**

Karma: 17
Deconectat Deconectat

Mesaje: 75



Vezi Profilul
« Răspunde #27 : Martie 18, 2011, 17:17:32 »

Cod:
bool muchii_crescatoare(mchie m1, mchie m2)
{
return m1.cost <= m2.cost;
}

Cred ca daca lasi doar "<" merge.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #28 : Martie 19, 2011, 15:17:13 »

Da, e exact la fel implementarea, cu exceptia sortarii.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
scipianus
Nu mai tace
*****

Karma: 129
Deconectat Deconectat

Mesaje: 345



Vezi Profilul
« Răspunde #29 : Iunie 12, 2011, 19:19:48 »

Se poate lua 100pct cu Kruskal cu sort-ul din STL ? (fara vreun min-heap pentru selectarea mai eficienta a muchiei de cost minim ?) Ca eu am incercat asa si iau doar 80pct cu 2 TLE-uri http://infoarena.ro/job_detail/595463 , am parsat apoi si citirea si tot nu intra cele 2 teste in limita de timp http://infoarena.ro/job_detail/595476  Confused
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #30 : Iunie 12, 2011, 19:31:08 »

Pai se poate, dar trebuie sa unesti componentele conexe folosind paduri de multimi disjuncte, nu asa cum faci tu, in O(n) Smile. Tu ai complexitate O(N * M), cea buna e O(MlogM + M log*N)
Memorat
valentin.harsan
Strain
*

Karma: 33
Deconectat Deconectat

Mesaje: 41



Vezi Profilul
« Răspunde #31 : Octombrie 15, 2011, 09:45:30 »

imi poate zice ce mai pot optimiza la sursa asta http://infoarena.ro/job_detail/617691?action=view-source? e algoritmul lui Kruskal(cred) dar nu am folosit nici o sortare. Iau TLE pe 3 teste.
Memorat
Grimpow
Strain


Karma: -2
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #32 : Ianuarie 19, 2012, 19:10:54 »

pe infoarena iau 1 raspuns gresit si 9 SIGSEV dar eu am rulat programul meu pentru toate testele alaturi cu alt program care ia 100 si nu este nici o diferenta .....
Raspunsul meu:
-17
8
1 5
7 1
3 2
9 7
4 1
6 5
2 6
8 3

Raspunsul unei alte surse de 100 de puncte:
-17
8
1 5
7 1
3 2
9 7
1 4
6 5
2 6
3 8

« Ultima modificare: Ianuarie 24, 2012, 19:28:46 de către Radu Andrei » Memorat
paulbota
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #33 : Martie 27, 2012, 15:23:15 »

deci nu inteleg ce am gresit la sursa asta imi da bine pe orice test incerc Brick wall
http://infoarena.ro/job_detail/726851?action=view-source
Memorat
psycho21r
Client obisnuit
**

Karma: -15
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #34 : Martie 27, 2012, 20:46:40 »

Testele pentru toate problemele din arhiva educațională sunt publice.

http://infoarena.ro/problema/apm?action=attach-list
Memorat
dragosnicolae
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #35 : Martie 28, 2012, 18:43:08 »

@paulbota

In functia downheap apelezi upheap(max) in loc de downheap(max)
Memorat
adysnook
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 6



Vezi Profilul
« Răspunde #36 : Mai 01, 2012, 19:09:22 »

stie cineva care este diferenta dintre
http://infoarena.ro/job_detail/742829?action=view-source
si
http://infoarena.ro/job_detail/742836?action=view-source
?
de ce una primeste 100 si cealalta 70?
Memorat
soriyn
Vorbaret
****

Karma: 24
Deconectat Deconectat

Mesaje: 150



Vezi Profilul
« Răspunde #37 : Mai 01, 2012, 19:18:26 »

Probabil pentru ca intr-una folosesti endl si in cealalta "\n"
Memorat
adysnook
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 6



Vezi Profilul
« Răspunde #38 : Mai 02, 2012, 07:36:25 »

intr-adevar! multumesc mult! am aflat si eu acum ca endl face mai mult decat sa bage un simplu sfarsit de linie.
Memorat
dutzul
De-al casei
***

Karma: 42
Deconectat Deconectat

Mesaje: 119



Vezi Profilul
« Răspunde #39 : August 02, 2012, 12:27:38 »

nuntaleg ce problema are sursa mea din cate ma uit pe ea e la fel cu celelalte de 100 folosesc kruskal,, any1 help? thnxhttp://infoarena.ro/job_detail/773689?action=view-source
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #40 : August 02, 2012, 12:41:26 »

Problema e ca nu folosesti nicio optimizare pentru padurile de multimi disjuncte. Astfel poti sa ai O(n) pe interogarea pentru componenta conexa fiindca arborii aia devin destul de dezechilibrati daca nu-i ajustezi pe parcurs. And also, incearca sa scrii mai corect pe forum  Smile
Memorat
dutzul
De-al casei
***

Karma: 42
Deconectat Deconectat

Mesaje: 119



Vezi Profilul
« Răspunde #41 : August 02, 2012, 14:41:13 »

mia mers de 100 cu comprimarea drumului. Very Happy eu ziceam ca sursa oficiala nu foloseste nici o optimizare(sau asa mi se pare mie) si ia 100
la varianta Prim nu reusesc sa iau peste 80 de pcte zice killed by signal 11 oare dela ce o fi?
http://infoarena.ro/job_detail/773881?action=view-source  .thnx

Editat de admin:
Mi-a mers de 100 cu comprimarea drumului Very Happy. Eu ziceam ca sursa oficiala nu foloseste nicio optimizare (sau asa mi se pare mie) si ia 100. La varianta Prim nu reusesc sa iau peste 80 de puncte. Zice killed by signal 11. Oare de la ce o fi?
« Ultima modificare: August 03, 2012, 11:33:05 de către Andrei Grigorean » Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #42 : August 03, 2012, 10:59:10 »

La SIGSEGV e de obicei stack overflow sau ai iesit din limitele unui vector. La al 2-lea nu cred ca e cazul. App , tu nu ai complexitate M lg M , nu N lg M ?  Whistle
Memorat
swim406
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 9



Vezi Profilul
« Răspunde #43 : Octombrie 30, 2012, 13:46:49 »

http://infoarena.ro/job_detail/795688

Nu îmi dau seama de ce nu reuşesc să iau peste 70 de puncte nici cu Kruskal, nici cu Prim. Mă puteţi ajuta careva?
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #44 : Octombrie 30, 2012, 16:38:38 »

Nu ai complexitatea buna. Uita-te peste explicatiile si sursele de pe pagina problemei.
Memorat
steluta
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #45 : Decembrie 10, 2012, 14:26:57 »

am incercat si kruscal si prim, dar nu inteleg de ce la unele teste am "subgraf selectat nu e arbore". are cineva vreo idee? Confused
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #46 : Decembrie 10, 2012, 14:58:20 »

Tu afisezi primele n-1 muchii citite, ceea ce nu e corect.  Ok
« Ultima modificare: Decembrie 10, 2012, 15:18:38 de către Pirtoaca George Sebastian » Memorat
zvon
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #47 : Martie 28, 2013, 18:00:55 »

In exemplul nr 2 costul minim este calculat gresit.. E de fapt -7 si nu -9. Exemplele acestea au fost evaluate prin acelasi procedeu care evalueaza solutiile trimise de utilizatori? 
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #48 : Martie 28, 2013, 18:43:32 »

-9 e mai mic decat -7.  Rolling Eyes
Memorat

Am zis Mr. Green
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #49 : Martie 28, 2013, 19:11:33 »

-9 e mai mic decat -7.  Rolling Eyes

Dar ai folosit aceeasi algebra care evalueaza solutiile trimise de utilizatori?
Memorat
Pagini: 1 [2] 3   În sus
  Imprimă  
 
Schimbă forumul:  

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