Luff

[•eudanip]

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.

[•tzipleatud]

Graful dat este conex?

[•mihaipopa12]

NU

[•scipianus]

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

[•repp4radu]

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?

[•mihaipopa12]

@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.

[•mihaipopa12]

@repp4radu

DA

[•Cristy94]

Pot exista mai multe muchii intre doua noduri?
Poate exista muchie de la X la X?

[•mihaipopa12]

Pot exista mai multe muchii intre doua noduri? DA
Poate exista muchie de la X la X? NU

[•crushack]

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

[•Cristy94]

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...

[•mihaipopa12]

1.000.000.000

[•scipianus]

Sunt grupate cumva ultimele teste? (am reusit sa iau ok pe testul 10,dar inca am tle pe 9 si ar fi cam naspa sa fie grupate  )

[•danalex97]

In primul rand felicitari lui Mihai Popa pentru problema.  In al doilea rand , cum ati facut problema asta ?   

[•mihaipopa12]

Ultimele trei teste sunt grupate 
Solutia mea e cu cautare binara in paralel dar exista si alte solutii.

[•mugurelionut]

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.

[•Steve]

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.

[•veleandu]

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

[•Steve]

Da, ai dreptate, mersi.