infoarena

Aici puteti discuta despre problema Arbore partial de cost minim (http://infoarena.ro/problema/apm).

Cum mai pot optimiza sursa asta http://infoarena.ro/job_detail/268348?action=view-source ?
Asta e algoritmul lui Kruskal, nu?

(E in pascal.)

Salut,

In primul rand poti optimiza sortarea. Ce faci tu acolo are complexitate N^2 si poti face o sortare in N*LogN. Iti recomand sa rezolvi problema Sortare prin comparare prima data. O poti gasi aici: http://infoarena.ro/problema/algsort. Algoritmii cei mai buni (pentru implementat de mana) sunt mergeSort si heapSort. QuickSort e si el ok, dar are worst case N^2. Pentru a rezolva aceasta problema a QuickSort, in practica se foloseste un pivot random (cand alegi pivotul alegi unul aleator din sirul tau, si nu un element fix - de obicei primul).
Apoi in procedura minim, tu faci iarasi N^2. Aici se poate face N*Sigma. Sigma e foarte mic (aproximativ 5), deci poate fi aproximat la O(1). O explicatie a acestui Sigma o gasesti si pe Wiki, Sigma reprezentand inversa functiei Ackerman pentru n,n. Iti recomand sa rezolvi prima data: http://infoarena.ro/problema/disjoint

Buna seara tuturor!
As vrea sa va intreb daca algoritmul lui Kruskal e bun si pentru determinarea unui ciclu de cost minim intr-un graf (adaugand o muchie in plus), considerand ca toate costurile sunt pozitive.

Daca vrei sa gasesti ciclul de cost minim prin parcurgerea muchiilor in ordinea crescatoare a costului, selectand mereu muchiile pana cand se formeaza un ciclu, nu o sa mearga.
Imagineaza-ti un graf de genul:


Prin parcurgerea muchiilor sortate, primul ciclu care se formeaza e cel alcatuit din arcele 1-2, 2-3, 3-4, 4-1, care are costul 16, iar ciclul de cost minim e format din muchiile 5-6, 6-7, 7-5 si are costul 15.

Nu am vrut sa spun ca adaug chiar prima muchie care formeaza ciclu, ci le verific pe toate care formeaza vreun ciclu. Obtin ciclul de cost minim?

Nu poti obtine ciclul de cost minim folosind Kruskal.

Contraexemplu:

Wefgef, cred ca el de fapt se referea ca foloseste kruskalu ca sa construiasca arborele partial de cost minim si apoi lua pe rand fiecare muchie care nu e in arbore si se uita la ciclul facut de aceasta. Chiar si asa nu este corect pentru ca ciclul de cost minim ar putea folosi 2 muchii care nu fac parte din arborele partial de cost minim.

Pai asta intelesesem si eu :eyebrow:. Algoritmul explicat in detaliu de tine pica pe contraexemplu.

Da ai dreptate. Nu stiu de ce aveam impresia ca ciclu minim e 1-2-3-4-1. Nu vazusem ca ciclul 1-4-5 e mai mic :-"

Multumesc pentru ajutor! Am inteles acum.
Totusi cum se obtine ciclul (elementar, evident) de cost minim? E vreun algoritm cunoscut?

Poti calcula cu Dijkstra cele mai mici doua distante intre oricare doua noduri din graf. Apoi iei fiecare muchie in considerare si aduni distanta corespunzatoare (cea mai mica sau a doua).

De fapt se poate si mai simplu. Vei presupune pe rand fiecare nod A din graf ca face parte din ciclul de cost minim. Vei face dijkstra pornind din nodul A. Apoi iei fiecare muchie (B, C) si verifici daca dmin(A, B) + dmin(A, C) < ciclul curent.

Am rescris sursa de 3 ori si tot nu-mi dau seama unde gresesc, pic pe penultimul test. Imi puteti spune unde gresesc, va rog ?
http://infoarena.ro/job_detail/391510?action=view-source ( Prim - folosind Heap-uri )
LE: rezolvat :)

Ce era? M-am uitat pe sursa ta, dar n-am vazut nimic suspect.

Initial eu nu introduceam in heap nodul de start ci toate nodurile adiacente cu acesta si se pare ca de aici se tragea greseala.

Salut ! Am incercat sa rezolv problema insa nu imi dau seama ce gresesc . Folosesc o coada cu prioritati in loc de Heap.Daca ma puteti ajuta : http://infoarena.ro/job_detail/482809?action=view-source

E ok ideea, insa cred ca gresesti ceva pe la coada de prioritati. Am implementat aceeasi sursa, dar in loc de coada am folosit multiset (pe post de heap) si imi dadea ok.

Oricum, am luat 100 cu sursa ta facind mici modificari (si pastrind priority_queue`ul). Uite aici: http://infoarena.ro/job_detail/482815?action=view-source ! Poate te ajuta cu ceva.
Nu stiu insa ce greseai tu in sursa ta (probabil ca la functia cmp, insa nu stiu sa rezolv).

Bafta!
Vlad.

Este ciudat pt la algoritmul lui Dijkstra am implementat coada in acelasi fel si am luat 100.

Am implementat algoritmul lui Prim dupa solutia oficiala. Diferenta dintre 90 de puncte si 100 a fost o mica modificare in procedura downheap (push parca era in cea oficiala). Mai exact, daca cel mai mic dintre fii era egal cu nodul curent nu le mai interschimba pentru ca (dupa parerea mea) nu avea rost. ( if(D[H[son]]>=D[H[k]]) , acum e doar >). Am gasit aceasta "corectura" doar din noroc. Puteti sa-mi dati un exemplu pentru care ar face vreo diferenta?

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

Nu mi se evalueaza sursa! :-W

salut! Care am puteti ajuta si pe mine? La implementare am folosit heapuri si multimi disjuncte. Nu stiu care ar fi problema dar nu iau decat 10p si din cate am citit, problema astfel implementata ar trebui sa ia un punctaj bun. Va sunt recunoscator celor care ma ajutati, mai ales ca am ajuns sa-mi smulg firele albe din cap ](*,)...nu gasesc "buba".

Am atasat la mesaj si sursa mea in format txt.

Accesul la testele problemei este liber. Testele 1 si 2 sunt destul de mici ca sa faci debug pe ele.
Testul 1 il treci, vezi ce are testul 2 - poate aia e "buba" cautata.

merci gabitzish1! am descoperit asa numita "buba". eu cand uneam arborii din neatentie nu uneam radacinile ci un element dintr-un arbore cu un element din celalalt si evident se "rupeau". merci inca o data:D(ps: chiar uitasem de faptul ca testele sunt vizibile la arhiva educationala....what a bummer)

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

Cred ca da.

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

Cred ca daca lasi doar "<" merge.

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

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 (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 (http://infoarena.ro/job_detail/595476)  :?

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

imi poate zice ce mai pot optimiza la sursa asta http://infoarena.ro/job_detail/617691?action=view-source (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.

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

deci nu inteleg ce am gresit la sursa asta imi da bine pe orice test incerc ](*,)
http://infoarena.ro/job_detail/726851?action=view-source

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

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

@paulbota

In functia downheap apelezi upheap(max) in loc de downheap(max)

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?

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

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

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

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

mia mers de 100 cu comprimarea drumului. :D 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 :D. 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?

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 ?  :-'

http://infoarena.ro/job_detail/795688 (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?

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

am incercat si kruscal si prim, dar nu inteleg de ce la unele teste am "subgraf selectat nu e arbore". are cineva vreo idee? :?

Tu afisezi primele n-1 muchii citite, ceea ce nu e corect.  :ok:

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? 

-9 e mai mic decat -7.  :roll:

Dar ai folosit aceeasi algebra care evalueaza solutiile trimise de utilizatori?

Mda, asa se intimpla cind prima data lucrezi cu grafuri ce pot avea muchii de lungime < 0.  :oops:

http://www.infoarena.ro/job_detail/1643327

Putin ajutor, va rog?

http://www.infoarena.ro/job_detail/1643510 Mai actuala

Ma poate ajuta si pe mine cineva cu implementarea algoritmului lui Kruskal in matlab?