266 Plimbare

[•bogdan2412]

Aici puteţi discuta despre problema Plimbare.

[•cristy]

cum se face desc in comp tare conexe in O(N+M)?

[•Cosmin]

http://zhuzeyuan.hp.infoseek.co.jp/ita/chap23.htm

CLR sectiunea 23.5

Cam neintuitive demonstratiile de pe acolo, gasesti explicatii putin mai bune daca vei  cauta pe google strongly connected components algorithm.

[•pocaitu]

 Nu vrea cineva sa-mi de-a un test , sa vad daca e gresit algoritmul meu? Mie imi merge la toate testele si pare foarte logic

[•devilkind]

pai zi cum faci ca sa stim ce test sa iti dam

[•pocaitu]

       Pai retin toate conectiile in liste de adiacenta. Apoi iau fiecare punct in parte si consider toate posibilitatile de parcurgere a grafului incepand din acel punct(folosind un vector viz si un vector max si un vector st). daca dau de un punctul de la care am pornit vad daca k>max si tot asa . (k= nr el din st[] unde in st retin elementele vizitate). Acuma mie mi se pare algoritmu fara nici o greseala si iau 0 la toate testele.(poate e din cauza la memcpy-uri sau memset-uri care tot timpu fac figuri).
Uite tot algoritmu
"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""'

Cod:

#include<fstream.h>
int long st[105],b,d,c,a[105][105],i,d1,v[102],j,k,n,viz[105],u,max[105],max1,gasit;
int main()
{ifstream f("plimbare.in");
 f>>n;
 for(i=1,j=(n*(n-1))/2;i<=j;i++)
  {f>>b>>c;
   a[b][++a[b][0]]=c;
   }
  for(i=1;i<=n;i++)
  {memset(viz,0,sizeof(viz));
   memset(max,0,sizeof(max));
   st[1]=i;
   k=1;
   while(k>0)
    {for(j=1,gasit=0,u=a[st[k]][0];j<=u;j++)
       if(max[st[k]]<a[st[k]][j]&&!viz[a[st[k]][j]])
	  {max[st[k]]=a[st[k]][j];
	   viz[a[st[k]][j]]=1;
	   st[++k]=a[st[k-1]][j];
	   gasit=1;
	   break;
	   }

     if(!gasit)
       {max[st[k]]=0;
	viz[st[k]]=0;
	k--;
	}
     if(st[k]==i&&k>1)
       {d=k;
       d1=n;
	if(k>max1)
	  {max1=k;
	   memcpy(v,st,sizeof(st));
	   }
	n=d1;
	k=d;
	viz[st[k]]=0;
	k--;
	}
    }
    }
ofstream g("plimbare.out");
g<<max1-1<<'\n';
for(i=1;i<=max1-1;i++)
 g<<v[i]<<" ";
g<<'\n';
g.close();
return 0;
}

"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""'

[•devilkind]

si ti-a intrat asha ceva in timp??? 

[•pocaitu]

 Fara nici o problema.mi se pare ca mi-a dat un test doua TLE.

[•Cosmin]

Si cate puncte ai luat?

[•pocaitu]

   Deci nici io nu credeam ca o sa imi intre in timp, da daca a intrat , unde e problema ? Ca am luat zero puncte pt WA . Asa ca imi da cineva un test sau nu ?
  Tinand cont de faptu ca n-ul e mai mic sau egal cu 100 si ca nu exista conectii decat pe un singur sens , nu pot sa zic ca ia kiar asa mult timp

[•Cosmin]

Pai cateodata algoritmii implementati gresit merg instantaneu , daca luai vre-un test inseamna ca era ceva bun pe acolo. Ca sa faci toate ciclurile posibile iti trebuie un algoritm exponential, si eu nu prea am vazut un backtraking pe acolo. Primul test are vreo 10 noduri si ciclul optim e de lungime 4, deci daca era ceva corect ar fi trebuit sa iei cam cu orice algoritm macar 5 puncte.

[•pocaitu]

 Am lucrat algoritmul meu pas cu pas si merge excelent,exact asa cum vream eu sa mearga . De aceea am rugat pe cineva sa-mi dea un test . Deci nu merge instantaneu. Eu ma gandesc ca poate se opreste undeva pe parcurs din cauza unei erori , sau poate am uitat un lucru banal. Na, dar daca nu vrea nimeni sa-mi dea unu asta e;  Si mor de curiozitate unde o fi greseala

[•Cosmin]

Pai tu nu iti poti genera sute de cazuri aleatoare? Si ai vazut in articolul cu solutii cum stii care e lungime maxima a unui ciclu. Deci iti ramane de facut o metoda care genereaza teste si alta care iti valideaza solutia.

[•Marius]

Noi gandim, masinile muncesc!

[•pocaitu]

 Muncim si noi knd implementam trei programe pt unu . Stiu backtracking . Kiar programu asta e un backtracking. Dar mi se pare ca am mai zis ca programu merge pe toate testele mele, deci nu aicea e problema
  NU poate fi gresita afisarea  ?
 Inca o intrebare: Ce da pt
10
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 3
4 2
2 5
2 6
7 2
8 2
2 9
2 10
4 3
3 5
3 6
7 3
8 3
3 9
3 10
4 5
6 4
4 7
8 4
4 9
4 10
5 6
7 5
8 5
5 9
5 10
6 7
6 8
6 9
6 10
8 7
7 9
7 10
8 9
8 10
9 10
mie imi da
7
2 3 5 6 8 4 7

[vladut.forum]

pai din cate vad io inccepi cu nodu 2...

si tot timpu tre sa incepi de la nodu 1 ..

vezi poate il omiti de la afisare

[•Cosmin]

Unde scrie in problema ca trebuie sa incepi cu nodul 1?

[•pocaitu]

Nu incep cu nodul unu daca el nu face parte din ciclul optim.

[•lucian666]

Salutare  . Am facut la problema aceasta un algoritm ( plus-minus ) pt determinarea componentelor conexe + un back pt a gasi ciclul corect.Iau doar 70 pct ,restul TLE.Exista ceva mai optim decat atat  ?
Multumesc Anticipat!!!!

[•CosminRusu]

Da. Lasa plus minus si incearca algoritmul lui Tarjan pentru componentele conexe .

[•AlexandruValeanu]

Am luat 70p folosind si algoritmul lui Tarjan si cel al lui Kosaraju pentru componente + backtracking. Se poate lua 100p cu backtracking ?

[•japjappedulap]

Spuneti-mi si mie, ce au testele 9, 11, 13, 15, 17, 19 asa special??
Cu tarjan + back iau 70. Pe testele mentionate iau TLE, iar pe restu' OK, 0ms.