139 Taramul Nicaieri

[ditzone]

Aici puteţi discuta despre problema Taramul Nicaieri.

[•cristy]

care e complexitatea oficiala a problemei?...ca eu iau 80 de pct...si cel mai mult imi da pe un test 0.02 sec, gresala e ca pe 4 teste...imi da ca apare o muchie de 2 ori...si inca ceva...exista intotdeauna solutie?...

[•cristy]

si ziceti va rog un test...asemanator cu 3,4,6 sau 10, sa vad ce gresesc...ca nu ma prind...si tot incerc...tot kestia aia imi spune...cum ca apare o muchie de 2 ori...dar...nu vad cum s-ar putea asa ceva...avand in vedere algoritmul meu...dar...s-ar putea sa nu afiseze pe 2 randuri nimic...si evaluatorul sa considere ca am scris 0?...si sa le ia ca fiind identice?

[andreit1]

Nu vad cu ce te-ar ajuta pe tine complexitatea oficiala. Ca puteti sa implementati aceeasi idee cu complexitati diferite. Deci poti avea idee buna si cu alta complexitate.
Si nu inteleg de ce ceri un test daca oricum sti ca nu se dau... Si problema a aparut de cateva zile, deci nu te-ai chinuit prea mult la ea...

[ditzone]

Intotdeauna va exista solutie. Cat despre mesajul primit  de tine inseamna fie ca afisezi o muchie de doua ori fie ca ai spus ca afisezi M muchii si ai afisat mai putine... acest lucru mi-a scapat din vedere la evaluator...

[•Coty]

e solutie unica? (scuza-ma daca nu am citit enuntul bine, dar mi-am aruncat ochii pe ea si am scos repede un alt raspuns pe exemplu, l-am verificat de 2 ori...)

[•tm_radu]

Ce raspuns ai gasit?

[ditzone]

Nu zice nicaieri ca e solutie unica

[•Coty]

Ce raspuns ai gasit?

nu e mare lucru:

Cod:

 1 2
 1 4
 4 3
 3 1 
 3 2

mi s-a parut la inceput ca daca solutia nu e unica, problema e simpla... dar nu e mi-am dat seama ce probleme apar... sorry de intrebare...

[•Robytzza]

nu inteleg unde am gresit am facut sa nu apara de mai multe ori o muchie si imi zice ca imi apare de mai multe ori o muchie  imi da cineva care a facut-o de 100 nishte teste pls:D

[•chelaru_t_a]

In harta.out conteaza ordinea scrieri drumurilor?

[•astronomy]

Nu. Se accepta orice solutie corecta.

[•marin]

Eu fac asa:
Intai sortez dupa gradele exterioare, apoi, parcurg descrescator si distribui fiecare grad exterior la gradele interioare, si acestea sortate descrescator (sortarea descrescator a gradelor interioare o fac repetat, dupa fiecare distribuire a unui grad esterior).
Timpii de executie sunt foarte buni insa iau doar 55 puncte. Este gresita ideea ?

[•wefgef]

Solutia oficiala este pe alta idee. Cred ca daca te chinui putin poti sa iti gasesti singur un test pe care pica ideea ta.

[•marin]

Eu am plecat de la ideea prin care se verifica daca o secventa poate reprezenta gradele unui graf neorientat.
Unde gasesc solutia oficiala?

[•wefgef]

Hint: Se face cu flux.

[•gigiq]

destul de ascunse ideile de flux...

[•gorgovan]

Eu am facut problema cu flux mai demult, dar acum am gasit-o ca fiind rezolvabila cu cuplaj maxim la problema omonima din arhiva educationala.
Se poate rezolva si asa ca eu nu reusesc sa-mi dau seama cum?

[•pauldb]

Da. Considerand constructia grafului pentru flux, un nod de acolo este inlocuit cu x noduri unde x este capacitatea dinspre nodul respectiv si sursa/destinatie.

[•gorgovan]

 
Cu Hopcroft Karp se poate lua 100?
Eu am incercat ideea ta si am mai folosit un tabel  care-mi spune daca am folosit o muchie sau nu.

Cod:

bool dfs(int x)
{
    if(viz[x]) return 0;
    viz[x]=1;
    vector<int>::iterator it;

    for(it=G[x].begin();it<G[x].end();it++)
    {
        if((!l[*it])&&!map[adev1[x]][adev[*it]])
        {   map[adev1[x]][adev[*it]]=1;
            l[*it]=x;
            map[adev1[x]][r[x]]=0;
            r[x]=*it;
            return 1;
        }
    }

    for(it=G[x].begin();it<G[x].end();it++)
    {
        if(dfs(l[*it])&&!map[adev1[x]][adev[*it]])
        {   map[adev1[x]][adev[*it]]=1;
            l[*it]=x;
            map[adev1[x]][r[x]]=0;
            r[x]=*it;
            return 1;
        }
    }
    return 0;
}