Imprimă pagina - 139 Taramul Nicaieri

Titlul: 139 Taramul Nicaieri
Scris de: ditzone din Noiembrie 23, 2005, 22:22:42

Aici puteÅ£i discuta despre problema Taramul Nicaieri (http://infoarena.ro/problema/harta).

Titlul: 139 Taramul Nicaieri
Scris de: Rus Cristian din Noiembrie 24, 2005, 16:47:26

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

Titlul: 139 Taramul Nicaieri
Scris de: Rus Cristian din Noiembrie 24, 2005, 17:39:43

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?

Titlul: 139 Taramul Nicaieri
Scris de: andreit1 din Noiembrie 24, 2005, 17:47:29

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

Titlul: 139 Taramul Nicaieri
Scris de: ditzone din Noiembrie 24, 2005, 19:16:24

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

Titlul: Re: 139 Taramul Nicaieri
Scris de: Sima Mihai Cotizo -vechi din Iulie 12, 2006, 22:04:14

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

Titlul: Raspuns: 139 Taramul Nicaieri
Scris de: Toma Radu din Iulie 12, 2006, 23:22:11

Ce raspuns ai gasit?

Titlul: Raspuns: 139 Taramul Nicaieri
Scris de: ditzone din Iulie 12, 2006, 23:40:01

Nu zice nicaieri ca e solutie unica

Titlul: Re: 139 Taramul Nicaieri
Scris de: Sima Mihai Cotizo -vechi din Iulie 13, 2006, 07:39:06

Citat din mesajul lui: tm_radu

Ce raspuns ai gasit?

nu e mare lucru:

Cod:

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

Titlul: RÄƒspuns: 139 Taramul Nicaieri
Scris de: Ionescu Robert Marius din Iunie 22, 2007, 10:05:24

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

Titlul: RÄƒspuns: 139 Taramul Nicaieri
Scris de: chelaru traian andrei din Aprilie 14, 2008, 15:38:13

In harta.out conteaza ordinea scrieri drumurilor?

Titlul: RÄƒspuns: 139 Taramul Nicaieri
Scris de: Airinei Adrian din Aprilie 14, 2008, 15:47:45

Nu. Se accepta orice solutie corecta.

Titlul: RÄƒspuns: 139 Taramul Nicaieri
Scris de: Mari n din August 25, 2008, 16:35:40

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 ?

Titlul: RÄƒspuns: 139 Taramul Nicaieri
Scris de: Andrei Grigorean din August 25, 2008, 18:50:39

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

Titlul: RÄƒspuns: 139 Taramul Nicaieri
Scris de: Mari n din August 25, 2008, 19:49:32

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

Titlul: RÄƒspuns: 139 Taramul Nicaieri
Scris de: Andrei Grigorean din August 26, 2008, 00:07:38

Hint: Se face cu flux.

Titlul: RÄƒspuns: 139 Taramul Nicaieri
Scris de: gigi f din Decembrie 15, 2008, 21:12:22

destul de ascunse ideile de flux... :oops:

Titlul: RÄƒspuns: 139 Taramul Nicaieri
Scris de: Aurelian Namascu din Decembrie 27, 2010, 13:17:34

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?

Titlul: Răspuns: 139 Taramul Nicaieri
Scris de: Paul-Dan Baltescu din Decembrie 27, 2010, 13:29:44

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.

Titlul: RÄƒspuns: 139 Taramul Nicaieri
Scris de: Aurelian Namascu din Decembrie 27, 2010, 17:19:20

:?
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;
}

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: ditzone din Noiembrie 23, 2005, 22:22:42