Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Heavy path decomposition  (Citit de 5476 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
silviug
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« : Noiembrie 13, 2007, 11:23:34 »

De curiozitate, heavy path decomposition e o tehnica cunoscuta prin comunitatea informaticienilor de pe la noi ?  Smile  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 Smile

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

"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #1 : 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 ? Smile
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
silviug
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« Răspunde #2 : 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 ? Smile

Baga mare. De ce fel de ajutor ai nevoie?
Memorat

"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #3 : 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 Smile. Asa macar scap de facut desene cu exemple. Daca ai nevoie de ajutor suntem aici.
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #4 : 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 ? Smile
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #5 : 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 ? Smile

Eu folosesc Visio pentru astfel de desene, try it out.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #6 : Noiembrie 19, 2007, 23:38:26 »

Eu le faceam cu corel, si un desen mai complicat imi lua vreo 20-30 de min.
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #7 : Ianuarie 10, 2008, 22:35:30 »

Articolul e terminat. Sper doar sa ajute pe cineva. Smile

Tree decompositions
« Ultima modificare: Ianuarie 22, 2009, 17:23:15 de către Marius Stroe » Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Tabara
Nu mai tace
*****

Karma: 20
Deconectat Deconectat

Mesaje: 216



Vezi Profilul
« Răspunde #8 : Ianuarie 11, 2008, 00:11:32 »

Articolul e terminat. Sper doar sa ajute pe cineva. Smile

http://infoarena.ro/Heavy-path-decomposition
Misto articol Marius. Applause
@admini: Ar merge un news in Arhiva de Stiri despre articolul nou-postat.
 Thumb up
Memorat
byndrsn
Client obisnuit
**

Karma: 19
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #9 : Ianuarie 11, 2008, 04:28:15 »

Cum as putea desen un arbore ? Paint ? Smile

Pentru desenare de grafuri, Ipe e destul de bun (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.
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #10 : 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.
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #11 : 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.
« Ultima modificare: Ianuarie 11, 2008, 21:13:50 de către Marius Stroe » Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #12 : 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.
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #13 : Ianuarie 12, 2008, 12:59:48 »

Poate (e legal) sa bage articolul de pe TC aici?
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #14 : 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. Smile
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #15 : 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.
Memorat
Marius
Nu mai tace
*****

Karma: 154
Deconectat Deconectat

Mesaje: 572



Vezi Profilul
« Răspunde #16 : 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.
Memorat

Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
silviug
Echipa infoarena
Nu mai tace
*****

Karma: 193
Deconectat Deconectat

Mesaje: 485



Vezi Profilul
« Răspunde #17 : 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 Smile

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 Tongue

Silviu
Memorat

"Don't gain the world and lose your soul, wisdom is better than silver or gold." [Bob Marley - Jamaican reggae musician & singer (1945 - 1981)]
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« Răspunde #18 : Februarie 20, 2009, 03:05:51 »

Discutia poate continua in topicul destinat acestui articol: http://infoarena.ro/forum/index.php?topic=3694.0
Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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