infoarena

infoarena - concursuri, probleme, evaluator, articole => .com 2012 => Subiect creat de: Eugenie Daniel Posdarascu din Martie 10, 2013, 13:55:18



Titlul: Luff
Scris de: Eugenie Daniel Posdarascu din 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.


Titlul: Răspuns: Luff
Scris de: Tudor Tiplea din Martie 10, 2013, 14:22:36
Graful dat este conex?


Titlul: Răspuns: Luff
Scris de: Popa Mihai din Martie 10, 2013, 14:25:08
NU


Titlul: Răspuns: Luff
Scris de: FMI Ciprian Olariu din 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 :shock:


Titlul: Răspuns: Luff
Scris de: Radu-Andrei Szasz din 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?


Titlul: Răspuns: Luff
Scris de: Popa Mihai din 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.


Titlul: Răspuns: Luff
Scris de: Popa Mihai din Martie 10, 2013, 14:33:40
@repp4radu

DA


Titlul: Răspuns: Luff
Scris de: Buleandra Cristian din Martie 10, 2013, 14:54:18
Pot exista mai multe muchii intre doua noduri?
Poate exista muchie de la X la X?


Titlul: Răspuns: Luff
Scris de: Popa Mihai din Martie 10, 2013, 14:58:05
Pot exista mai multe muchii intre doua noduri? DA
Poate exista muchie de la X la X? NU


Titlul: Răspuns: Luff
Scris de: Popescu Silviu din Martie 10, 2013, 15:22:41
Care e cea mai mare valoare care poate fi intoarsa de un Query??


Titlul: Răspuns: Luff
Scris de: Buleandra Cristian din 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...


Titlul: Răspuns: Luff
Scris de: Popa Mihai din Martie 10, 2013, 15:36:33
1.000.000.000


Titlul: Răspuns: Luff
Scris de: FMI Ciprian Olariu din Martie 10, 2013, 16:51:06
Sunt grupate cumva ultimele teste? :roll: (am reusit sa iau ok pe testul 10,dar inca am tle pe 9 si ar fi cam naspa sa fie grupate  ](*,) )


Titlul: Răspuns: Luff
Scris de: Dan H Alexandru din Martie 10, 2013, 19:09:33
In primul rand felicitari lui Mihai Popa pentru problema.  =D> In al doilea rand , cum ati facut problema asta ?   :fool:


Titlul: Răspuns: Luff
Scris de: Popa Mihai din Martie 10, 2013, 19:29:14
Ultimele trei teste sunt grupate  :)
Solutia mea e cu cautare binara in paralel dar exista si alte solutii.


Titlul: Răspuns: Luff
Scris de: Mugurel-Ionut Andreica din 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.


Titlul: Răspuns: Luff
Scris de: Stefan Eniceicu din 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. :)


Titlul: Răspuns: Luff
Scris de: Alex Velea din 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 :)


Titlul: Răspuns: Luff
Scris de: Stefan Eniceicu din Martie 11, 2013, 21:39:53
Da, ai dreptate, mersi.