Pagini: 1 [2] 3   În jos
  Imprimă  
Ajutor Subiect: 034 Ciclu Eulerian  (Citit de 25936 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #25 : Februarie 10, 2010, 19:13:27 »

Nu inteleg ce vrei sa spui. Poti sa reformulezi intrebarea?
Memorat

Am zis Mr. Green
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #26 : Februarie 10, 2010, 20:04:58 »

Nu inteleg ce vrei sa spui. Poti sa reformulezi intrebarea?

Ok! Ma refer la ultima varianta de rezolvare, cea cu ciclurile disjuncte.
Daca o sa te uiti in sursa lui Lucian vei observa ca dupa ce determina daca graful este eulerian e face un do-while in care cauta  ciclurile disjuncte din graf.
Un ciclu il gaseste dupa ce apeleaza o singura data functia euler();
Si eu ma intrebam daca avem nevoie de mai mult de un apel doar atunci cand avem deaface cu noduri critice?(adica asta e intrebarea:) )
Acest lucru se observa si in problema de mai sus pentru ca nodul 3 e nod critic.
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #27 : Iunie 16, 2010, 19:04:27 »

Are cineva o sursa comentata fara stl? Am incercat sa implementez dar gresesc la stergere.  Fool
edit: nu am reusit sa termin deoarece greser\sc stergerile. Din lene am renuntat sa rezolv pb asta fara stl.
« Ultima modificare: Iunie 16, 2010, 19:47:33 de către Trimbitas Petru » Memorat
BitOne
Strain
*

Karma: -1
Deconectat Deconectat

Mesaje: 45



Vezi Profilul
« Răspunde #28 : Iunie 16, 2010, 19:31:49 »

Are cineva o sursa comentata fara stl? Am incercat sa implementez dar gresesc la stergere.  Fool
Mai simplu posteaza, sau trimite sursa ta si noi corectam Smile
Memorat
MciprianM
Nu mai tace
*****

Karma: 87
Deconectat Deconectat

Mesaje: 324



Vezi Profilul
« Răspunde #29 : August 09, 2010, 19:45:26 »

A implementat cineva algoritmul lui Fleury? Nu prea stiu cum sa determin daca o muchie e punte(sau critica...) dupa update in mod eficient.
L.E.: Niciun test nu contine un graf care nu este conex?
« Ultima modificare: August 10, 2010, 20:20:21 de către Marginean Ciprian » Memorat
livium
Strain


Karma: -2
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #30 : Decembrie 06, 2010, 20:26:47 »

"Pentru determinarea lantului, vom adaugata fictiv o muchie intre aceste doua noduri, dupa care vom aplica algoritmul de determinare a unui ciclu Eulerian. Eventual, acest ciclu determinat va fi 'rupt' in locul in care apare muchia adaugata si tiparit in ordinea corecta."

Eu am implementat algoritmul recursiv si totul merge perfect. Nu mai trebuie sa adaugi nicio muchie fictiva. Trebuie doar sa apelezi euler(nod de grad impar). Si merge. NU inteleg de ce ati scris chestia asta cu muchia. Va rog raspundeti-mi ca sa nu mor prost.

[email protected]
« Ultima modificare: Decembrie 06, 2010, 20:32:52 de către livica » Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #31 : Decembrie 06, 2010, 21:31:54 »

Chestia asta cu muchia a fost scrisa ca sa-ti arate intr-un mod elegant ca e practic aceeasi problema cu cea a ciclului eulerian.
Cuvantul 'fictiv' ar fi trebuit sa-ti dea un hint in sensul asta. Adopta un ton mai calm si mai cooperant, te rog.
Memorat
invatacel
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #32 : Ianuarie 15, 2011, 15:59:56 »

Solutia prezentata ca fiind optima e O(M*N), eliminarea unei muchii se face in O(N) deci nu intra in timp pe niste teste bune.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #33 : Ianuarie 15, 2011, 23:20:15 »

De ce zici ca eliminarea unei muchii se face in O(N)?
Memorat
invatacel
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #34 : Ianuarie 16, 2011, 15:54:17 »

Cod:
void sterge( int v, int w )
{
  deg[v]--, deg[w]--;
  G[v].pop_front();
  TR( G[w], it )
   if( *it == v )
   {
       G[w].erase( it );
       break;
   }
}

Mi se pare destul de O(n)  Smile. Un varf poate sa aiba N vecini si ala pe care il stergi sa fie ultimul in lista.
Memorat
invatacel
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #35 : Ianuarie 16, 2011, 16:00:36 »

Testele sunt slabe si nu diferentiaza o astfel de solutie de una optima.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #36 : Ianuarie 16, 2011, 17:35:05 »

Nu sunt testele slabe. Presupunand ca muchiile sunt distribuite relativ uniform, pe testele maxime marimea listelor de adiacenta e mult mai mica decat n.  Ai nevoie de un graf cu densitate mult mai mare ca sa busesti stergerea aia, ori e cam imposibil sa dai ca input un graf dens cu 100 000 de noduri.

Stergerea o poti face mai bine. Stergi muchia doar din v si o marchezi pentru eliminare intr-un vector. Astfel o vei sterge din lista lui w de-abia cand treci pe-acolo si o intalnesti, nefiind nevoie sa o mai cauti pe loc.

Deci e O(n + m).
Memorat
invatacel
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #37 : Ianuarie 16, 2011, 19:26:06 »

Ce te face sa presupui ca muchiile sunt distribuite uniform? Vorbim de analiza in cazul cel mai defavorabil nu in cazul mediu. Considera graful urmator: N noduri (N par) 1 si 2 noduri speciale 1 are muchie catre toate cele N-2 noduri ramase, 2 la fel (in total 2*(N-2) muchii deci graf deloc dens) cati vecini are 1 si cat dureaza sa elimini un element din lista lui de vecini?
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #38 : Ianuarie 16, 2011, 19:36:04 »

Poti sa tii un hash in care sa bagi muchiile sterse => stergere muchie O(1). Si probabil ca mai sunt si alte solutii. Dar nu pe stergerea muchiei se pune accentul la problema aceasta. E arhiva educationala, deci nu e nevoie de teste super puternice.
Memorat
invatacel
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #39 : Ianuarie 16, 2011, 20:10:31 »

Stiu ca se poate, si cum se poate. Problema e ca fiind arhiva educationala omu vine si invata problema se uita si peste sursa oficiala, face stergerea in O(N) ia 100 la problema si zice "da dom'le stiu sa rezolv problema". Apoi se duce la concurs implementeaza aceeasi solutie si ia 50 de puncte pe teste mai bune si se intreaba "de ce?". Asta e singurul lucru pe care vroiam sa-l punctez.
Memorat
ucc_5
Client obisnuit
**

Karma: -11
Deconectat Deconectat

Mesaje: 82



Vezi Profilul
« Răspunde #40 : Ianuarie 28, 2011, 23:15:31 »

Pana la urma cum e, trebuie ca toate nodurile sa aibe gradul par, sau pot exista fix 2 care au gradul impar :
A connected undirected graph is Eulerian if and only if every graph vertex has an even degree, or exactly two vertices have an odd degree.
Vad ca cele afirmatii se bat cap in cap ....
Memorat
toni2007
Nu mai tace
*****

Karma: 160
Deconectat Deconectat

Mesaje: 663



Vezi Profilul
« Răspunde #41 : Ianuarie 29, 2011, 02:42:11 »

Toate nodurile au grad par <=> exista ciclu eulerian
Toate nodurile au grad par cu exceptia a fix 2 <=> exista lant eulerian
Memorat
adelinac
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #42 : Februarie 19, 2011, 16:56:40 »

pentru prima figura (patratul cu doua diagonale ) care este solutia prin care nu treci de 2 ori printr-o latura si nu ridici creionul de pe foaie? Huh
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #43 : Februarie 19, 2011, 20:55:54 »

Nu exista nici o solutie. Tocmai pentru ca graful respectiv nu e eulerian.
Memorat

Am zis Mr. Green
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #44 : Ianuarie 07, 2012, 19:09:23 »

Graful e orientat sau neorientat?
Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #45 : Ianuarie 07, 2012, 19:15:33 »

Eu am rezolvat-o presupunand ca e neorientat.
Memorat
Bit_Master
Vorbaret
****

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #46 : Ianuarie 07, 2012, 19:33:44 »

Eu am rezolvat-o presupunand ca e neorientat.

Da, se vede ca e neorientat din exemplu. Ar trebui specificat.

LE: Se pot mari restrictiile problemei un pic sa nu fie nevoie sa faci parsare si alte lucruri de genul asta?
« Ultima modificare: Ianuarie 30, 2012, 18:04:20 de către Alexandru-Iancu Caragicu » Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #47 : Iulie 10, 2012, 09:06:55 »

Sursa oficiala ia 60 de puncte cu TLE pe ultimul test. Cred ca ar trebui marita putin limita de timp (pentru 100 de puncte trebuie parsata citirea).
« Ultima modificare: Iulie 10, 2012, 10:01:37 de către Pirtoaca George Sebastian » Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #48 : Iulie 10, 2012, 12:00:31 »

Fixed.
Memorat
ctlin04
Nu mai tace
*****

Karma: 23
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #49 : Iulie 30, 2012, 13:46:37 »

Nu pot sa inteleg de ce evaluatorul imi spune "Fisier de iesire corupt", numele la fisier este corect si la urma inchid fisierul , pls help  Brick wall
Memorat
Pagini: 1 [2] 3   În sus
  Imprimă  
 
Schimbă forumul:  

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