290 Gandaci Java

[ditzone]

Aici puteţi discuta despre problema Gandaci Java.

[•cristy]

un cercetator poate prinde mai multi gandaci?

[•Marius]

un cercetator poate prinde mai multi gandaci?

Nu.

[•pocaitu]

Problema mi s-a parut f simpla . Dupa mine nu e alceva decat un cuplaj maximal in graf bipartit .
 Dar cand m-am uitat la statistici  am ramas blocat 
 Care-i smenu , pana la urma ??

[•azotlichid]

Incearca sa o implementezi si vei vedea 

[•pocaitu]

 Probabil ca va iesi din timp , altceva n-ar avea ce sa aiba .
 Nu prea vad de ce sa implementez degeaba ca sa vad ca imi iese din timp. Ma gandeam ca poate imi da cineva  care  a mai facut-o ,un hint.
   

[•Marius]

Eu nu am rezolvat problema dar cred ca se rezolva cu algoritmul Hopcroft Karp care determina cuplajul maxim in cel mult in N^1/2 pasi. Daca reusesti sa imi spui si mie! 

[•devilkind]

cred ca vrei sa zici n^2/2 nu n^1  , am sa ma uit si eu dupa algoritm, eu am incercat cu flux si nu am fost asa surprins cand am vazut 0 fiind prima mea problema de cuplaj, insa am fost surprins ca nu era vorba de WA ci de TLE.

[•bogdan2412]

Ideea la baza algoritmului Hopcroft Karp e sa se augmenteze un set de lanturi alternante maximal la fiecare pas... Daca cunosti algoritmul de cuplare cu functia PairUp ( nu stiu numele oficial al algoritmului dar asa i se spune :p ) poti sa-l optimizezi si pe el sa mearga de 100 pe aceeasi idee.

set maximal de lanturi alternante = un set de lanturi alternante disjuncte care nu se mai poate mari adaugand alt lant (maximal != maxim)
Daca ai rabdarea sa cauti pe net despre hopcroft karp si lanturi alternante vei intelege mai bine

devilkind: n^(1/2)

[•sima_cotizo]

Am si eu o intrebare, se poate retine in vreun fel ce gandac cu ce cercetator sunt legati? ... Vreau sa zic ca am incercat cu liste de adiacenta, pe care dupa fiecare test le dealoc... si primesc Memory limit exceeded... 

Postez si functiile de adaugare si stergere la liste... nu stiu de ce dar cred ca acel "delete" nu face ca ce e alocat pointerului *p sa poata fi realocat mai incolo...

Cod:

void add(long x, long y) {
    lista *p = new lista;
    p -> x = y;
    p -> n = G[x];
    G[x] = p;

}
void remove() {
    lista *p;
    long i;
    for (i=1; i<=N; ++i) {
        while ( G[i] ) {
            p = G[i];
            G[i] = G[i]->n;
            delete p;
        }
    }
}

unde "lista" = struct { long x, lista* n; } ...

[•DITzoneC]

Par in regula functiile alea, esti sigur ca nu e de la altceva ... ?

[•sima_cotizo]

Pai nu stiu daca aveti "Fundamentele programarii pt clasa XI" a doamnei Lica, dar acolo exista un programel dragut cuplaj... Care nu e cu flux. Eu zic ca l-am inteles destul de bine...
Ideea in program e ca odata ce am atribuit un gandac java unui cercetator, niciodata acel gandac nu va ramane fara cercetator [eventual doar il schimba] si de aici se face un apel recursiv la o functie ca sa vedem daca nu putem reatribui gandacul altcuiva...
Ca sa fiu mai explicit:

Cod:

int cauta_gandacel( long x ) {
    lista *p;
...
   for (p = G[x]; p; p=p->n) {
        if ( dr[p->x] == 0 || cauta_gandacel(dr[p->x]) ) {
            dr[p->x] = x; 
            return 1;
        }
...    return 0;
}

In mare cam asta e, exista acolo un apel recursiv la cauta_gandacel ... dar mie imi da Memory limit exceeded nu Seg fault => iese din cei 64MB pt memorie

Cod:

    while (T--) {
        nr = 0;
       scanf("%ld %ld %ld", &N, &M, &E);
        for (i=0; i<E; ++i) {
            scanf("%ld %ld", &x, &y);
            add(y,x);
        }
        cuplaj();
        printf("%ld\n", nr);
        remove();
    }

in afara de niste memseturi in while, cam asta e citirea mea ... remove si add sunt procedurile de mai sus... nu vad ce are ... doar le dealoc dupa fiecare subtest... inseamna ca intr-un subtest fol mai multa memorie decat pot tine, si nu vad cum pot rezolva asta ... sau ca "delete" in c++ nu prea face ce trebuie !

[•DITzoneC]

Cred ca poti sa ai Memory limit exceeded si de la apelul recursiv. Daca procedura care se apeleaza iti intra intr-un ciclu infinit ea va tot pune chestii pe stiva deci la un moment data va depasi limita de memorie. Verifica conditia de oprire a apelului recursiv...

[•sima_cotizo]

Ciudat, era de la depasirea stivei cred ...
Aveam cateva erori cum ar fi un vector de char in loc de long si o codificare pe biti tocmai ca sa ocup mai putina memorie, dar care era putin gresita [o conditie]... Acum am doar Incorect...  mai e de munca!

Multumesc mult de ajutor!

[Later edit] Am dat mai multe teste, inclusiv cele de pe la alte probleme de cuplaj de prin arhiva... si imi da corect Daca are cineva un test mai "tricky" il rog sa il posteze... nu ma prind ce ar putea fi gresit...

[•DITzoneC]

Cod:

for (i=0; i<E; ++i) {
            scanf("%ld %ld", &x, &y);
            add(y,x);

Nu trebuie sa ai

Cod:

            add(x,y);

?

[•sima_cotizo]

Mmm... nu adica nu cred ca e vreo diferenta...
In problema zice ca ordinea din fisier e "cercetator - gandac"; eu incerc sa unesc fiecare gandac cu cate un cercetator, deci lista mea de adiacenta este pentru fiecare gandac ce cercetatori poate alege... deci am pus add(y,x). Nu cred ca este vreo diferenta daca incerc sa cuplez maximal gandacii cu cercetatorii sau invers, nu m-am gandit..

Anyway, acum am gasit si alte mici greseli si imi da TLE pana la urma... se pare ca algoritmul asta are complexitate O(N*E)... si cu flux nu cred ca gasesc ceva mai bun.

[•DITzoneC]

Este o diferenta ( daca M <> N ) din momentu ce ai M gandaci si N cercetatori tu zici ca vrei sa cuplezi cei M gandaci, dar in procedura de eliberare faci forul pana la N...

[•sima_cotizo]

Da, ai perfecta dreptate... Citisem prost enuntul, la mine N era numarul de gandaci.
Totusi, acum nu primesc WA ci TLE pe linie . Cred ca oricum nu e potrivit algoritmul. Ma straduiesc in continuare!

[•wefgef]

Limita de timp e foarte stransa. Ai grija ce algoritm iti alegi, pentru ca nu toate intra in timp.

[•vanila0406]

mie imi iese din memorie cu Ford-Fulkerson 

[•Dastas]

Ar putea cineva explica ceva mai pe larg ideea care sta la baza algoritmului Hopcroft Karp? In cormen e tratat foarte sumar algoritmul, iar pe net nu am gasit ceva mai bun...

Nu prea inteleg cum determin lanturile alea alternante maximal...

[•fireatmyself]

Gasesti un articol pe aceasta tema in sectiunea downloads. Acesta a fost scris de Mugurel Ionut Andreica si prezentat pe 13 mai 2006, la Ploiesti, in cadrul taberei de pregatire a lotului national de informatica.

[•Dastas]

Am descarcat arhiva cu lotul din 2006 de la Ploiesti si nici macar nu exista un 13 mai... exista un articol 'Hopcroft' in folderul 14 mai dar nu prea are legatura cu cuplajul maximal in graf bipartit...

Sigur e acolo?

[•devilkind]

varule vezi ca linku tau e prost. Ai pus de 2 ori http://

[•fireatmyself]

pentru Tibi: s-a rezolvat linkul 

pentru Vlad: imi cer scuze, era lotul de la Suceava din 2007. eu nu am articolul in fata, dar stiu de la Mugurel ca are prezentat si un algoritm destept pentru cuplaj. daca, insa, imi aduc eu aminte prost , si nu este acolo, poate te ajuta informatiile de aici.