infoarena

infoarena - concursuri, probleme, evaluator, articole => Articole => Subiect creat de: Silviu-Ionut Ganceanu din Noiembrie 13, 2007, 11:23:34



Titlul: Heavy path decomposition
Scris de: Silviu-Ionut Ganceanu din Noiembrie 13, 2007, 11:23:34
De curiozitate, heavy path decomposition e o tehnica cunoscuta prin comunitatea informaticienilor de pe la noi ?  :)  Eu, personal, abia am "descoperit-o" acum vreo luna si un pic, pornind de la alte chestii [ conceptul de "path separator" ], dar mi se pare o idee foarte misto :)

Baga un articol cu treaba asta. Personal, nu cred ca stiu despre ce e vorba...


Titlul: Heavy path decomposition
Scris de: Marius Stroe din Noiembrie 18, 2007, 13:02:25
As putea scrie eu un articol. Insa, am nevoie de ajutor la scrierea lui pe infoarena si, datorita lipsei de timp, nu il voi termina foarte repede. De acord, Silviu ? :)


Titlul: Heavy path decomposition
Scris de: Silviu-Ionut Ganceanu din Noiembrie 19, 2007, 21:21:05
As putea scrie eu un articol. Insa, am nevoie de ajutor la scrierea lui pe infoarena si, datorita lipsei de timp, nu il voi termina foarte repede. De acord, Silviu ? :)

Baga mare. De ce fel de ajutor ai nevoie?


Titlul: Heavy path decomposition
Scris de: Cosmin Negruseri din Noiembrie 19, 2007, 21:27:15
Vroiam sa scriu pe blog problema asta si problema delay, dar daca te-ai oferit sa scrii jmenu cu path decomposition tu, baga mare :). Asa macar scap de facut desene cu exemple. Daca ai nevoie de ajutor suntem aici.


Titlul: Heavy path decomposition
Scris de: Marius Stroe din Noiembrie 19, 2007, 22:15:04
Nu stiu sa il "pun" pe infoarena. Aici as avea nevoie de ajutor.

Cum as putea desen un arbore ? Paint ? :)


Titlul: Heavy path decomposition
Scris de: Mircea Pasoi din Noiembrie 19, 2007, 22:50:23
Nu stiu sa il "pun" pe infoarena. Aici as avea nevoie de ajutor.

Cum as putea desen un arbore ? Paint ? :)

Eu folosesc Visio pentru astfel de desene, try it out.


Titlul: Heavy path decomposition
Scris de: Cosmin Negruseri din Noiembrie 19, 2007, 23:38:26
Eu le faceam cu corel, si un desen mai complicat imi lua vreo 20-30 de min.


Titlul: Heavy path decomposition
Scris de: Marius Stroe din Ianuarie 10, 2008, 22:35:30
Articolul e terminat. Sper doar sa ajute pe cineva. :)

Tree decompositions (http://infoarena.ro/tree-decompositions)


Titlul: Heavy path decomposition
Scris de: Tabara Mihai din Ianuarie 11, 2008, 00:11:32
Articolul e terminat. Sper doar sa ajute pe cineva. :)

http://infoarena.ro/Heavy-path-decomposition (http://infoarena.ro/Heavy-path-decomposition)
Misto articol Marius. =D>
@admini: Ar merge un news in Arhiva de Stiri despre articolul nou-postat.
 :thumbup:


Titlul: Heavy path decomposition
Scris de: Alina Ene din Ianuarie 11, 2008, 04:28:15
Cum as putea desen un arbore ? Paint ? :)

Pentru desenare de grafuri, Ipe e destul de bun (http://tclab.kaist.ac.kr/ipe/ (http://tclab.kaist.ac.kr/ipe/)). Un graf destul de complicat imi ia un minut-doua (Ipe are support pentru noduri, muchii, snap to vertices, etc.). De obicei folosesc Ipe pentru slides pentru ca pot sa scriu in latex si sa desenez tot felul de grafuri si retele.


Titlul: Heavy path decomposition
Scris de: Cosmin Negruseri din Ianuarie 11, 2008, 13:41:55
marius in general articolul imi place dar as avea cateva observatii:

  prima problema nu are treaba cu heavy path decomposition si doar incurca pe cei care vor sa citeasca articolul, avand in vedere ca ocupa o treime din articol
   rezolvarea de la problema respectiva a fost idea mea si am popularizat-o pe forum si la altii, probabil nu era greu de venit cu ea si au avut-o mai multi, dar eu nu ii stiu. De asemenea solutia autorului (Mugurel) e si ea interesanta si daca tot o pui pe cea cu + -, poti sa o pui linistit si pe cea a lui Mugurel care e cel putin la fel de frumoasa
   totusi as vrea sa separi articolul cu rezolvarea la delay de asta cu heavy path decomposition
   de asemenea poti folosi trucul cu path decomposition ca sa rezolvi problema asta si daca folosesti biased finger trees chiar poti sa o  rezolvi in O(m log n)

  alta chestie eu sau as sari cu totul peste longest path decomposition care incurca putin din claritatea solutiei si as arata doar solutia cu heavy path decomposition, sau as numy articolul Path decomposition tricks sau ceva de genu asta.

sper sa nu iei ce am zis ca si critici ci ca sugestii.


Titlul: Heavy path decomposition
Scris de: Marius Stroe din Ianuarie 11, 2008, 16:22:43
Imi pare bine ca iti place articolul Cosmin.

Eu, cand am aflat de heavy path decomposition, nu am stiut ca se numeste asa, am aflat doar despre faptul ca se descompune in pathuri alegand nodul cel mai "greu", cu numarul cel mai mare de noduri. Martor imi e Wefgef, caruia eu i-am propus Query on a tree si care mi-a explicat, insa eu tot nu am inteles in cele din urma, si am incercat in continuare sa gasesc o rezolvare cu liniarizarea arborelui. Am pierdut cateva zile tot incercand. Din acest motiv am pus rezolvarea unei cerinte care se foloseste de liniarizarea arborelui si apoi de arbori de intervale. In articol nu m-am exprimat intocmai cum ar fi trebuit, nu am spus motivul, care e personal, pentru care am prezentat solutia cu +-. Pe de alta parte, nu am spus enuntul problemei Delay, sunt o multime de alte probleme care se folosesc de aceasta liniarizare. Eu am prezentat ceea ce m-a incurcat pe mine.

Nu am stiut ca rezolvarea primei probleme a fost ideea ta. Eu pur si simplu am intalnit-o destul de des. Nici nu mai stiu de unde a inceput totul. Scopul meu nu a fost sa prezint toate solutiile, a fost sa arat ca nu are rost sa se chinuie cu liniarizarea arborelui. Repet ca nu e Delay desi are aceleasi cerinte. Mai spun ca nu am inteles niciodata cum sunt drepturile de autor: pe spoj e exact Maxq a lui Daniel Pasaila de la ONI 2007, dar cu un alt nume "Can you answers these queries II". Din nou, Maxq seamana izbitor cu o problema data la bursele agora. Autorii lor difera.

Odata ce documentez sursele de inspiratie inseamna ca nu am luat ideea nimanui. Sunt o multime de documente pe internet, unele din ele prezente si in bibliografie. Sunt multi oameni cu idei, idei care de multe ori coincid la fel ca si in rezolvarea unei probleme.

M-am gandit si eu la un alt titlu, deoarece doar partea finala prezinta ce se exprima prin el.

Se poate vedea lipsa mea de experienta in prezentarea si documentarea acestui articol. Sper sa mi se ierte acest lucru. Nu am vrut sa intru in detalii, pe care dealtfel nu le stiu prea bine, cum ar fi demonstrarea stricta ca sunt O(logN) lanturi si altele. E un articol destul de intuitiv. Eu astept cu placere critici.

Marius Stroe

LE: Am uitat sa pun la referinte linkul de unde am aflat de longest path decomposition www.cs.sunysb.edu/~bender/pub/latin02-level.ps si unde scrie foarte putin despre heavy path decomposition. Greseala mea.


Titlul: Heavy path decomposition
Scris de: Cosmin Negruseri din Ianuarie 12, 2008, 12:27:40
Am vorbit cu Marius pe privat si daca are timp sparge articolul in doua si baga si solutia lui Mugurel.

Impreuna cu articolul lui Daniel Pasaila de pe topcoder vom avea trei articole foarte misto despre arbori si operatii pe ei.


Titlul: Heavy path decomposition
Scris de: Mircea Pasoi din Ianuarie 12, 2008, 12:59:48
Poate (e legal) sa bage articolul de pe TC aici?


Titlul: Heavy path decomposition
Scris de: Marius Stroe din Ianuarie 12, 2008, 13:27:04
Voi sparge articolul in doua si voi adauga o generalizare la trucul cu heavy path decomposition pe care nu am intalnit-o nicaieri. Dar cine stie ...
Cu enuntul initial ar deveni prea stufos si nu l-ar mai citi nimeni. :)


Titlul: Heavy path decomposition
Scris de: Cosmin Negruseri din Ianuarie 13, 2008, 18:25:55
Eu ma gandeam ca in pagina de articole am putea baga cate un link la articolele misto de pe topcoder, si sa punem langa link mentiunea topcoder.

Articole interesante ar fi a lui Liviu Ciortea cu flux si a lui Daniel Pasaila despre LCA si RMQ. Dar aproape toate de la educational content de la topcoder sunt interesante.


Titlul: Heavy path decomposition
Scris de: Marius Stroe din Ianuarie 22, 2008, 14:37:38
Nu are sens sa detaliez generalizarea, deoarece nu ar ajuta pe nimeni. Pentru determinarea celei de a K-a valori si nu a maximului sau minimului e nevoie de o complexitate O(M log24N) care e cam acelasi lucru cu O(M*N) - cu statistici de ordine. In plus, heavy path decomposition + cautare binara + arbori de intervale 2D + o structura de genul AVL, ar fi mai mult decat suficient sa te convinga sa scrii un O(M*N), care s-ar comporta la fel, tinand cont de constante.


Titlul: Heavy path decomposition
Scris de: Silviu-Ionut Ganceanu din Ianuarie 23, 2008, 17:17:40
Eu ma gandeam ca in pagina de articole am putea baga cate un link la articolele misto de pe topcoder, si sa punem langa link mentiunea topcoder.

Articole interesante ar fi a lui Liviu Ciortea cu flux si a lui Daniel Pasaila despre LCA si RMQ. Dar aproape toate de la educational content de la topcoder sunt interesante.

Desi discutia a deviat clar de la scopul ei initial si probabil ar trebui mutata in alta parte -- solutia unei probeme de pe timus -- imi exprim si eu pararea :)

Stefan Istrate a revizuit training path-ul: http://infoarena.ro/training-path. Si eu sunt de acord ca nu e o problema ca din pagina asta sa bagam link-uri (marcate cumva) catre articole de pe topcoder. Daca ele exista si-s facute bine, de ce ne-am mai chinui sa "reconstruim roata"? Eventual, ne putem asigura ca treaba asta e legala intreband pe cei de la TC :P

Silviu


Titlul: Răspuns: Heavy path decomposition
Scris de: Stefan Istrate din Februarie 20, 2009, 03:05:51
Discutia poate continua in topicul destinat acestui articol: http://infoarena.ro/forum/index.php?topic=3694.0