|
Titlul: 289 Arbore de cicluri Scris de: ditzone din Octombrie 15, 2006, 21:34:05 Aici puteţi discuta despre problema Arbore de cicluri (http://infoarena.ro/problema/arbciclu).
Titlul: Răspuns: 289 Arbore de cicluri Scris de: Mihai Leonte din Septembrie 05, 2009, 02:00:10 Totusi, am o nelamurire in legatura cu solutia oficiala. Fie urmatorul set de date de intrare:
1 5 6 1 2 1 3 1 4 2 5 3 5 4 5 Conform ideii de rezolvare descrisa acolo... acest graf ar trebui sa fie un arbore de cicluri, dar din enuntul problemei eu inteleg ca nu este (pentru ca doua cicluri trebuie sa aiba in comun o singura muchie si doua noduri, iar in cazul de fata e vorba de 2 muchii si 3 noduri). ??? I'm confused, solutia ar trebui sa dea YES sau NO? :-k Titlul: Răspuns: 289 Arbore de cicluri Scris de: Petru Trimbitas din Iulie 07, 2011, 10:22:17 Cred ca ar putea fi marita limita de timp putin :D Titlul: Răspuns: 289 Arbore de cicluri Scris de: Mihai-Alexandru Dusmanu din Octombrie 08, 2011, 16:48:06 Rog pe cineva care are o sursa de 100 mai veche sa o trimita din nou. Eu iau 60 de puncte cu solutia buna si ma gandesc sa nu fie de la noile limite :).
Titlul: Răspuns: 289 Arbore de cicluri Scris de: Adrian Budau din Octombrie 09, 2011, 11:53:58 Am testat sursa lui Gavrila Vlad. Se pare ca el inca ia 100. Deocamdata pare buna limita incercati sa mai optimizati.
Titlul: Răspuns: 289 Arbore de cicluri Scris de: Gavrila Vlad din Octombrie 09, 2011, 12:04:17 Eu am luat 100 abia dupa ce am parsat citirea. (e drept, am trecut de la 90 la 100, de la 60 s-ar putea sa trebuiasca sa mai optimizezi).
Titlul: Răspuns: 289 Arbore de cicluri Scris de: Mihai-Alexandru Dusmanu din Octombrie 09, 2011, 18:12:20 Merci pentru raspunsuri. Ati avut dreptate :) Limita de timp este ok :thumbup:
Titlul: Răspuns: 289 Arbore de cicluri Scris de: Visan Radu din Decembrie 21, 2012, 21:45:16 Cred ca e prea mica limita de timp. Am o solutie in O(T * N * log M) care ia 60. :-k
Titlul: Răspuns: 289 Arbore de cicluri Scris de: Vasilut Lucian din Decembrie 22, 2012, 19:30:58 Salut . La problema aceasta iau doar 0 pct ](*,) cu 5 incorrect si restul TLE.
Procedez astfel: 1.Pt fiecare nod de gradul 2 il bag intr-o coada. 2.Pt fiecare element din coada,ii iau cei doi vecini (i,j) si le scad gradul cu o unitate,elimin vf curent din coada din graf,iar apoi adaug muchiile(i,j),(j,i) . 3.Daca la finalul algoritmului am doar 2 noduri ramase inseamna ca am solutie ... Este buna ideea de rezolvare ,sau am uitat eu ceva :D ? Mentionez ca pt retinerea grafului neorientat folosesc un set. Multumesc Anticipat !!! :) Later Edit.Am mai modificat cate ceva prin program si am reusit sa iau 20 pct,cu 3 incorect si restul tle ](*,) Cat va da pt urmatorul test ? Cod:
mie imi da : Cod: YES Multumesc anticipat!!! :) Later Edit 2 .Am reusit sa iau 50 pct,pe restul testelor am TLE. Cred ca e prea mica limita de timp. Am o solutie in O(T * N * log M) care ia 60. :-k Am reusit sa scot si eu aceeasi complexitate ...Cred ca ar trebui marita putin limita de timp 8) Titlul: Răspuns: 289 Arbore de cicluri Scris de: Adrian Budau din Noiembrie 30, 2013, 11:49:14 Voi mari limita de timp. Scuze ca a durat atat.
Titlul: Răspuns: 289 Arbore de cicluri Scris de: Vlad Rochian din Octombrie 11, 2014, 10:27:50 Testul acesta este valid?
Cod: 1 Cu doua surse diferite de 100 de puncte primesc raspunsuri diferite :-k |