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

Karma: 307
Deconectat Deconectat

Mesaje: 695



Vezi Profilul
« : Martie 10, 2013, 13:55:18 »

Aici se pot pune întrebări legate de problema Luff de la Runda 3 a concursului .com 2012

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.
Memorat
tzipleatud
De-al casei
***

Karma: 104
Deconectat Deconectat

Mesaje: 117



Vezi Profilul
« Răspunde #1 : Martie 10, 2013, 14:22:36 »

Graful dat este conex?
Memorat
mihaipopa12
Client obisnuit
**

Karma: 74
Deconectat Deconectat

Mesaje: 64



Vezi Profilul
« Răspunde #2 : Martie 10, 2013, 14:25:08 »

NU
Memorat
scipianus
Nu mai tace
*****

Karma: 129
Deconectat Deconectat

Mesaje: 345



Vezi Profilul
« Răspunde #3 : Martie 10, 2013, 14:28:55 »

Prin arbore se intelege ca daca pornim dintr-un nod anume (sa-i zicem radacina) atunci putem ajunge in restul nodurilor din el?

LE : am crezut initial gresit ca ar fi graf orientat Shocked
« Ultima modificare: Martie 10, 2013, 16:27:51 de către Olariu Ciprian » Memorat
repp4radu
Nu mai tace
*****

Karma: 118
Deconectat Deconectat

Mesaje: 204



Vezi Profilul
« Răspunde #4 : Martie 10, 2013, 14:29:15 »

Presupunand ca subgraful format pentru o valoare val, candidata la solutie nu e arbore, ci prezinta un ciclu, pot considera ca daca exista un graf partial al subgrafului ales care este arbore, atunci val poate fi solutie?
Memorat
mihaipopa12
Client obisnuit
**

Karma: 74
Deconectat Deconectat

Mesaje: 64



Vezi Profilul
« Răspunde #5 : Martie 10, 2013, 14:32:52 »

@scipianus

Daca pornim dintr-un nod anume (radacina) atunci putem ajunge din el in k noduri, printre care si nodul nod.
Adica nodul nod din query trebuie sa se afle intr-o componenta conexa de cel putin k noduri.
Memorat
mihaipopa12
Client obisnuit
**

Karma: 74
Deconectat Deconectat

Mesaje: 64



Vezi Profilul
« Răspunde #6 : Martie 10, 2013, 14:33:40 »

@repp4radu

DA
Memorat
Cristy94
De-al casei
***

Karma: 37
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #7 : Martie 10, 2013, 14:54:18 »

Pot exista mai multe muchii intre doua noduri?
Poate exista muchie de la X la X?
Memorat
mihaipopa12
Client obisnuit
**

Karma: 74
Deconectat Deconectat

Mesaje: 64



Vezi Profilul
« Răspunde #8 : Martie 10, 2013, 14:58:05 »

Pot exista mai multe muchii intre doua noduri? DA
Poate exista muchie de la X la X? NU
Memorat
crushack
De-al casei
***

Karma: 23
Deconectat Deconectat

Mesaje: 108



Vezi Profilul
« Răspunde #9 : Martie 10, 2013, 15:22:41 »

Care e cea mai mare valoare care poate fi intoarsa de un Query??
Memorat
Cristy94
De-al casei
***

Karma: 37
Deconectat Deconectat

Mesaje: 128



Vezi Profilul
« Răspunde #10 : Martie 10, 2013, 15:27:53 »

Care e cea mai mare valoare care poate fi intoarsa de un Query??

Cred ca 1.000.000.000, cat e val maxima pe muchii...
Memorat
mihaipopa12
Client obisnuit
**

Karma: 74
Deconectat Deconectat

Mesaje: 64



Vezi Profilul
« Răspunde #11 : Martie 10, 2013, 15:36:33 »

1.000.000.000
Memorat
scipianus
Nu mai tace
*****

Karma: 129
Deconectat Deconectat

Mesaje: 345



Vezi Profilul
« Răspunde #12 : Martie 10, 2013, 16:51:06 »

Sunt grupate cumva ultimele teste? Rolling Eyes (am reusit sa iau ok pe testul 10,dar inca am tle pe 9 si ar fi cam naspa sa fie grupate  Brick wall )
Memorat
danalex97
Vorbaret
****

Karma: 54
Deconectat Deconectat

Mesaje: 192



Vezi Profilul
« Răspunde #13 : Martie 10, 2013, 19:09:33 »

In primul rand felicitari lui Mihai Popa pentru problema.  Applause In al doilea rand , cum ati facut problema asta ?   Fool
Memorat
mihaipopa12
Client obisnuit
**

Karma: 74
Deconectat Deconectat

Mesaje: 64



Vezi Profilul
« Răspunde #14 : Martie 10, 2013, 19:29:14 »

Ultimele trei teste sunt grupate  Smile
Solutia mea e cu cautare binara in paralel dar exista si alte solutii.
Memorat
mugurelionut
De-al casei
***

Karma: 209
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« Răspunde #15 : Martie 10, 2013, 23:20:02 »

Eu am facut Kruskal (considerand muchiile in sens descrescator al costurilor). Am folosit disjoint sets cu "union-by-size". Dupa fiecare Union tineam minte pt nodul "parinte" ca la timpul T (T = muchia ce face unirea) dimensiunea componentei sale a devenit egala cu valoarea V (V=nr de noduri din cele 2 componente tocmai unite). Pt nodul care devenea fiu al "parintelui" tineam minte ca trece in parinte la timpul T.

Practic, apoi, pt fiecare nod X, aveam un sir de perechi (T,V) sortate (dimensiunea V creste pe masura cu timpul creste -- sau, echivalent, costul muchiei de unire scade). Dupa acest sir de cresteri ale dimensiunii componentei lui X (in care X ramane radacina), X devine fiul al lui P(X) (la momentul TP(X) = muchia ce realizeaza unirea lui X cu P(X)).

Pt un query trebue sa pleci din nodul X dat si sa urci in sus pe parintii lui de multimi disjuncte pana dai de un nod Y a carui dimensiune a componentei (la ultimul moment cand mai era radacina a componentei sale) este >= K. Raspunsul e apoi maximul dintre muchiile parinte prin care s-a trecut si muchia la care nodul Y ajunge sa aiba dimensiune >= K.

Partea de preprocesare (Kruskal) e O(M*(log(M) + log(N))) si apoi avem O(log(N)) pe query.

Eu as fi interesat sa stiu cum e solutia cu cautare binara in paralel (sau alte solutii la problema asta). Mie problema asta mi-a placut cel mai mult din concursul de azi.
Memorat
Steve
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #16 : Martie 11, 2013, 00:33:13 »

Am incercat sa abordez problema in modul urmator si sunt curios daca ar fi intrat pentru limite:

Consider initial N multimi disjuncte (fiecare multime asociata unui nod). In fiecare multime tin in "radacina" ei toate Query-urile aferente, ex: daca in multimea X aveam nodurile 6, 4 si 1, atunci tineam in X toate query-urile referitoare la 1, 4 si 6 sortate crescator dupa K (nr de elemente necesar in multime).

Sortez muchiile dupa valoare descrescator si le parcurg, una cate una, facand join de cele 2 multimi legate de muchia respectiva. De fiecare data cand fac join de 2 multimi, scot din fiecare Query-urile la care pot sa raspund si updatez in vectorul de Answer cu valoarea ultimei muchii luate, acum ca am K' = K1 + K2. Apoi fac merge pe cei 2 vectori de Query-uri, bagand vectorul rezultat in multimea rezultata. Mi s-a parut ok rezolvarea dar am crapat memoria si eram curios daca ar fi intrat o sursa pe ideea asta. Smile
Memorat
veleandu
De-al casei
***

Karma: 155
Deconectat Deconectat

Mesaje: 132



Vezi Profilul
« Răspunde #17 : Martie 11, 2013, 17:08:18 »

Steve, cred ca ar trebui sa iti dea TLE nu MLE.
Problema e ca atunci cand faci join, faci in O(m+n) nu in min(n,m).

Daca ai fi facut in min(n,m) overall ar fi fost maxim logN.
Asa, daca ai ceva de genu.
join(1,2);
join(1,3);
..
etc
ai join la q*n chestii.

^^



La cautare binara in paralel, pt un query iti cauti binar valoarea muchiei care ar fi cea care iti da rezultatul.
Astfel, faci Kruskal de nogN ori si pt fiecare query verifici doar o data, nu de M ori .. ca la brut Smile
Memorat
Steve
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #18 : Martie 11, 2013, 21:39:53 »

Da, ai dreptate, mersi.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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